// ********** InterpreterDemo.java **********
class Stack {
  private static final int MAX_STACK = 1000;
  private static final int INIT_TOP = -1;
  private static final int ERROR = -99999;
  private int top = INIT_TOP;
  private int stack[] = new int[MAX_STACK];
  public void push(int i) {
    if (top < MAX_STACK - 1) stack[++top] = i;
  }
  public int pop() {
    if (top != INIT_TOP) return stack[top--];
    return ERROR;
  }
}
class Array {
  public static final int MAX_ARRAY = 1000;
  private AbstractExpression array[] = new AbstractExpression[MAX_ARRAY];
  private int size = 0;
  public void add(AbstractExpression ae) {
    if (size < MAX_ARRAY - 1) array[size++] = ae;
  }
  public int getSize() { return size; }
  public AbstractExpression getExpression(int i) { return array[i]; }
}

interface AbstractExpression { public void interpret(Stack context); }
 
class NonTerminalExpression implements AbstractExpression {
  private Array expressions = new Array();   
  public void interpret(Stack context) {
    for (int i=0; i<expressions.getSize(); i++)
      expressions.getExpression(i).interpret(context);
  }
  public void add(AbstractExpression ae) { expressions.add(ae); }
}
class IntegerTerminalExpression implements AbstractExpression {
  private int i;
  public IntegerTerminalExpression(int i) { this.i = i; }
  public void interpret(Stack context) {
    context.push(i);
  }
}
class OperatorTerminalExpression implements AbstractExpression {
  private char op;
  public OperatorTerminalExpression(char op) { this.op = op; }
  public void interpret(Stack context) {
    int i = context.pop(); 
    int j = context.pop(); 
    if (op == '+')
      context.push(i+j); 
    else
      context.push(i*j);
  }
}
public class InterpreterDemo{
  private static final int MAX=1000;
  private static final int MAX_INT = 500;
  public static void main(String[] args) {
    long t1 = System.currentTimeMillis();
    Stack context = new Stack();
    for (int i=0; i<MAX; i++) {
      NonTerminalExpression nte = new NonTerminalExpression();
      for (int j=0; j<MAX_INT; j++)
        nte.add(new IntegerTerminalExpression(j));
      for (int j=0; j<MAX_INT-1; j++)
        nte.add(new OperatorTerminalExpression('+'));
      nte.interpret(context);
      int result = context.pop();
      //System.out.println("result: "+ result); 
    }
    long t2 = System.currentTimeMillis();
    System.out.print((t2-t1)+" ");
    System.out.flush();
  }
}