// ********** InterpreterDemo.cpp **********
#include <iostream>
#include <time.h>
using namespace std;

class Stack;
class AbstractExpression { public: virtual void interpret(Stack* context) = 0;; };
 
const int INIT_TOP = -1;
const int MAX_STACK = 1000;
const int ERROR = -99999;
class Stack {
  private:
    int top;
    int stack[MAX_STACK];
  public:
    Stack() { top = INIT_TOP; }
    void push(int i) {
      if (top < MAX_STACK - 1) 
        stack[++top] = i;
    }
    int pop() {
      if (top != INIT_TOP)
        return stack[top--];
      return ERROR;
    }
};
const int MAX_ARRAY = 1000;
class Array {
  private:
    AbstractExpression* array[MAX_ARRAY];
    int size;
  public:
    Array() { size = 0; }
    void add(AbstractExpression* ae) {
      if (size < MAX_ARRAY - 1) 
        array[size++] = ae;
    }
    int getSize() { return size; }
    AbstractExpression* getExpression(int i) { return array[i]; }
};
class NonTerminalExpression : public AbstractExpression {
  private:
    Array* expressions;   
  public:
    NonTerminalExpression() { expressions = new Array(); } 
    void interpret(Stack* context) {
      for (int i=0; i<expressions->getSize(); i++)
        expressions->getExpression(i)->interpret(context);
    }
    void add(AbstractExpression* ae) { expressions->add(ae); }
};
class IntegerTerminalExpression : public AbstractExpression {
  private:
    int i;
  public:
    IntegerTerminalExpression(int i) { this->i = i; }
    void interpret(Stack* context) {
      context->push(i);
   }
};
class OperatorTerminalExpression : public AbstractExpression {
  private:
    char op;
  public:
    OperatorTerminalExpression(char op) { this->op = op; }
    void interpret(Stack* context) {
    int i = context->pop(); 
    int j = context->pop(); 
    if (op == '+')
      context->push(i+j); 
    else
      context->push(i*j);
  }
};
const int MAX=1000;
const int MAX_INT = 500;
int main() {
  hrtime_t t1 = gethrtime();
  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();
    // cout << "result: " << result <<endl;
  }
  hrtime_t t2 = gethrtime();
  cout << (t2-t1)/1000000 << " ";
  return 1;
}