#include <stdio.h>         /* Standard Libraries */
#include <stdlib.h>
#include <stdarg.h>
#include <iostream>

using namespace std;

// ----------------- Lexical Scanner -----------------

class error {
public:
   error(string m, string l, int i):mess(m),pos(i),line(l){}
   void print();
private:
   string line;
   string mess;
   int pos;
};

enum SymbolType {
   nullsym,                  // null symbol
   eoisym,                   // end of input
   lbrak,rbrak,              // left/right brackets
   number,                   // number
   plus, minus, mult, divide // operator
};

class Symbol{
public:
   Symbol():type(nullsym),value(0){}
   Symbol(SymbolType t, int v):type(t),value(v){}
   SymbolType GetType(){return type;}
   int GetValue(){return value;}
private:
   SymbolType type;
   int value;
};

class Scanner {
public:
   Scanner(string input);
   Symbol CurSym(){return cursym;}
   void GetNextSym();
   void Check(SymbolType t, string errmess);
private:
   Symbol cursym;
   string inputline;
   int curpos;
   int inputlen;
};

Scanner::Scanner(string input)
{
   inputline = input;
   curpos = 0;
   inputlen = input.size();
}

void Scanner::GetNextSym()
{
   char buf[20];
   // skip any blank space
   while (curpos < inputlen && isspace(inputline[curpos])) ++curpos;
   // deal with end of input case first
   if (curpos>=inputlen){
      cursym = Symbol(eoisym,0);
      return;
   }
   int i = curpos;
   char c = inputline[i];
   // decode numbers
   if (isdigit(c)){
      while (curpos < inputlen && isdigit(inputline[curpos])) ++curpos;
      strcpy(buf,inputline.substr(i,curpos-i).c_str());  
      cursym = Symbol(number,atoi(buf));
      return;
   }
   // remaining symbols
   ++curpos;
   switch(c) {
      case '(': cursym = Symbol(lbrak,0); return;
      case ')': cursym = Symbol(rbrak,0); return;
      case '+': cursym = Symbol(plus,0); return;
      case '-': cursym = Symbol(minus,0); return;
      case '*': cursym = Symbol(mult,0); return;
      case '/': cursym = Symbol(divide,0); return;
      default: throw error("Unknown symbol",inputline,curpos);
   }
   return;
}

void Scanner::Check(SymbolType t, string errmess)
{
   if (cursym.GetType()!=t) throw error(errmess,inputline,curpos);
}

void error::print()
{
   printf("\n%s\n",line.c_str());
   for (int i=0; i<pos; i++) printf(" ");
   printf("^\n");
   printf("**** %s\n",mess.c_str());
}

// -------------- Expression Tree Structure ----------

class Node {
public:
   virtual int GetValue()=0;
};

class Numb : public Node {
public:
   Numb(Scanner *s);
   int GetValue();
private:
   int num;
};

class Expr : public Node {
public:
   Expr(Scanner *s);
   int GetValue();
private:
   SymbolType op;
   Node * lTree;
   Node * rTree;
};

class Term : public Node {
public:
   Term(Scanner *s);
   int GetValue();
private:
   bool neg;
   Node * tree;
};

// ----------------- Implementation ------------------

Numb::Numb(Scanner * s)
{
   num = s->CurSym().GetValue();
   s->GetNextSym();
}

int Numb::GetValue()
{
   return num;
}

// Term => number | "(" expr ")" | "-" term
Term::Term(Scanner * s)
{
   neg = false; tree = NULL;
   if (s->CurSym().GetType()==lbrak) {
      s->GetNextSym();
      tree = new Expr(s);
      s->Check(rbrak,"right bracket expected");
      s->GetNextSym();
   }else if (s->CurSym().GetType()==minus) {
      s->GetNextSym(); neg = true;
      tree = new Term(s);
   }else {
      s->Check(number,"number expected");
      tree = new Numb(s);
   }
}

int Term::GetValue()
{
   int x = tree->GetValue();
   if (neg) return -x;
   return x;
}

// Expr => term [ op expr ]
Expr::Expr(Scanner * s)
{
   lTree = new Term(s);
   rTree = NULL;
   op = nullsym;
   if (s->CurSym().GetType() >= plus) {
      op = s->CurSym().GetType();
      s->GetNextSym();
      rTree = new Expr(s);
   }
}

int Expr::GetValue()
{
   int x = lTree->GetValue();
   if (op != nullsym) {
      int y = rTree->GetValue();
      switch (op) {
         case plus:   x += y; break;
         case minus:  x -= y; break;
         case mult:   x *= y; break;
         case divide: x /= y; break;
      }
   }
   return x;
}

// ---------------- Main Program ---------------------

void main(int argc, char *argv[])
{
   printf("Expression evaluator:\n");
   for (int i=1; i<argc; i++) {
      Scanner * s = new Scanner(argv[i]);
      try {
         s->GetNextSym();
         Expr * e = new Expr(s);
         printf("%d. %s = %d\n",i,argv[i],e->GetValue());
      }
      catch (error& e) {
         e.print();
      }
   }
}