#include <iostream>
#include <string>
#include <ctype.h>
#include <iomanip>
#include <vector>

struct inputsystem
{ string line;
  int pos, linenum, linelength;

  inputsystem()
  { line="";
    pos=1;
    linelength=0;
    linenum=0; }

  char getchar()
  { if (pos>linelength)
    { getline(cin, line);
      if (cin.fail())
        line="#";       // denotes end of input
      pos=0;
      linelength=line.length();
      linenum+=1; }
    if (pos==linelength || pos<0)
    { pos+=1;
      return ' '; }
    pos+=1;
    return line[pos-1]; }

  void putbackchar()
  { pos-=1; }

  void error(string s)
  { cerr << "ERROR on line " << linenum << ": " << s << "\n";
    for (int i=0; i<pos && i<linelength; i+=1)
      cout << line[i];
    cout << " <- HERE\n";
    for (int i=0; i<pos && i<linelength; i+=1)
      cout << " ";
    for (int i=pos; i<linelength; i+=1)
      cout << line[i];
    cout << "\n"; }
 };

const int _binop=1, _assignment=2, _semicolon=3, _print=4, _number=5, _variable=6, _end=7;
const string tokennames[] = { "0", "binop", "assignment", "semicolon", "print", "number", "variable", "end" };

struct token
{ int kind;
  string detail;

  token (int k, string d="")
  { kind=k;
    detail=d; } 

  void print()
  { cout << tokennames[kind] << "(" << detail << ")"; }
 };

struct tokeniser
{ inputsystem in;
  token thetoken;
  bool reuse_the_token;

  tokeniser(): thetoken(0)
  { reuse_the_token = false; }

  void error(string s)
  { in.error(s); }    

  token gettoken()
  { if (reuse_the_token)
    { reuse_the_token = false;
      return thetoken; }
    char c = ' ';
    while (c<=' ')
      c = in.getchar();
    thetoken.kind = 0;
    thetoken.detail = "";
    if (c=='+' || c=='-' || c=='*' || c=='/')
    { thetoken.kind = _binop;
      thetoken.detail += c; }
    else if (c==';')
      thetoken.kind = _semicolon;
    else if (c=='=')
      thetoken.kind = _assignment;
    else if (c=='#')
      thetoken.kind = _end;
    else if (isdigit(c))
    { thetoken.kind = _number;
      while (isdigit(c))
      { thetoken.detail += c;
        c=in.getchar(); }
      in.putbackchar(); }
    else if (isalpha(c))
    { thetoken.kind = _variable;
      while (isalpha(c))
      { thetoken.detail += tolower(c);
        c=in.getchar(); }
      in.putbackchar();
      if (thetoken.detail=="print")
        thetoken.kind = _print; }
    else
      error("bad character in program");
    return thetoken; }

  void putbacktoken()
  { reuse_the_token = true; }
 };

vector<string> var_names;
vector<int> var_values;

int findvar(string name)
{ for (int i=0; i<var_names.size(); i+=1)
    if (var_names[i]==name)
      return i;
  return -1; }

int getvar(string name)
{ int pos=findvar(name);
  if (pos<0)
    return 0;
  return var_values[pos]; }

int getvar(int i)
{ if (i<0 || i>=var_values.size())
    return 0;
  return var_values[i]; }

void setvar(string name, int val)
{ int pos=findvar(name);
  if (pos<0)
  { var_names.push_back(name);
    var_values.push_back(val); }
  else
    var_values[pos]=val; }

void printvars()
{ for (int i=0; i<var_names.size(); i+=1)
    cout << "  " << setw(6) << var_names[i] << " = " << var_values[i] << "\n"; }

struct node
{ int kind;
  int value;
  string name;
  vector <node *> sub;

  node(int k, int v=0, string n="")
  { kind=k;
    value=v;
    name=n; }

  node * add(node * p)
  { sub.push_back(p);
    return this; }
};

node * num(int v)
{ return new node(_number, v); }

node * print()
{ return new node(_print); }

node * var(string n)
{ return new node(_variable, 0, n); }

node * binop(string o)
{ return new node(_binop, 0, o); }

node * assign(string var)
{ return new node(_assignment, 0, var); }

node * seq()
{ return new node(_semicolon); }

int evaluate(node * n)
{ if (n==NULL)
  { cout << "NULL!!!";
    return 0; }

  else if (n->kind == _number)
    return n->value;

  else if (n->kind == _variable)
  { int p = findvar(n->name);
    if (p<0)
    { cout << "undefined variable '" << n->name << "'\n";
      return 0; }
    return getvar(p); }

  else if (n->kind == _assignment)
  { int v = evaluate(n->sub[0]);
    setvar(n->name, v);
    return v; }

  else if (n->kind == _print)
  { int v = evaluate(n->sub[0]);
    cout << v << " ";
    return v; }

  else if (n->kind == _semicolon)
  { int val=0;
    for (int i=0; i<n->sub.size(); i+=1)
      val=evaluate(n->sub[i]);
    return val; }

  else if (n->kind == _binop)
  { if (n->sub.size() != 2)
    { cout << "ERROR IN +!!!";
      return 0; }
    else
    { int a=evaluate(n->sub[0]);
      int b=evaluate(n->sub[1]);
      if (n->name=="+")
        return a+b;
      else if (n->name=="-")
        return a-b;
      else if (n->name=="*")
        return a*b;
      else if (n->name=="/")
      { if (b==0)
        { cout << "division by zero";
          return 0; }
        return a/b; }
      else
      { cout << "bad operator";
        return 0; } } }

  else
  { cout << "ERROR BAD KIND";
    return 0; } }

void print(node *n)
{ if (n==NULL)
    cout << "NULL!!!";

  else if (n->kind == _number)
    cout << n->value;

  else if (n->kind == _variable)
    cout << n->name;

  else if (n->kind == _assignment)
  { if (n->sub.size() != 1)
      cout << "ERROR IN assign!!!";
    else
    { cout << n->name << " = ";
      print(n->sub[0]); } }  

  else if (n->kind == _print)
  { if (n->sub.size() != 1)
      cout << "ERROR IN print!!!";
    else
    { cout << "print (";
      print(n->sub[0]);
      cout << ")"; } }  

  else if (n->kind == _semicolon)
  { for (int i=0; i<n->sub.size(); i+=1)
    { print(n->sub[i]);
      cout << ";\n  "; } }

  else if (n->kind == _binop)
  { if (n->sub.size() != 2)
      cout << "ERROR IN binop!!!";
    else
    { cout << "(";
      print(n->sub[0]);
      cout << n->name;
      print(n->sub[1]);
      cout << ")"; } }

  else
    cout << "ERROR BAD KIND"; }

node * parse_simp_expr(tokeniser & inp)
{ token T = inp.gettoken();
  if (T.kind == _variable)
    return var(T.detail);
  else if (T.kind == _number)
    return num(atol(T.detail.c_str()));
  else
  { inp.error("simple expression expected here");
    return NULL; } }

node * parse_mult_expr(tokeniser & inp)
{ node * L = parse_simp_expr(inp);
  while (true)
  { token T = inp.gettoken();
    if (T.kind!=_binop || T.detail!="*")
      break;
    node * R = parse_simp_expr(inp);
    L = binop("*")->add(L)->add(R); }
  inp.putbacktoken();
  return L; }

void main()
{ tokeniser toker;
  node * root = parse_mult_expr(toker);
  cout << "Input accepted as:\n\n  ";
  print(root);
  cout << "\nThe following token is ";
  token T = toker.gettoken();
  T.print();
  cout << "\n"; }