#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include <cstdlib>
#include <vector>

using namespace std;

struct inputter
{
  ifstream in;
  string fname;
  string line;
  int pos, linenum;

  inputter(string fn)
  { fname = fn;
    in.open(fname);
    if (in.fail())
    { cerr << "Can't open file \"" << fname << "\"\n";
      exit(1); }
    line = "";
    pos = 1;
    linenum = 0; }

  void refill()
  { getline(in, line);
    pos = 0;
    linenum += 1; }

  char get()
  { int len = line.length();
    if (in.fail())
      return 'D'-64;    // control D
    if (pos > len)
    { refill();
      len = line.length(); }
    if (pos == len)
    { pos += 1;
      return '\n'; }
    char r = line[pos];
    pos += 1;
    return r; }

  void unget()
  { if (pos > 0)
      pos -= 1; }

  void error(string msg)
  { cerr << "Error on line " << linenum << ", before character " << pos << "\n";
    cerr << msg << "\n";
    cerr << line << "\n";
    cerr << setw(pos-1) << "" << "^\n"; }
};

const int unknown = 1, constint = 2, punctuation = 3, opr = 4, variable = 5,
          keyword = 6, endoffile = 7; 

string kinds[] = { "zero", "unknown", "constint", "punctuation", "opr",
                   "variable", "keyword", "endoffile" };

struct token
{ int kind;
  string form;
  int value; };

struct LexAn
{ inputter & in;
  token t;
  bool reuse;

  LexAn(inputter & i): in(i)
  { t.kind = unknown;
    reuse = false; }

  void unget()
  { reuse = true; }

  void get()
  { if (reuse)
    { reuse = false;
      return; }
    t.kind = unknown;
    t.form = "";
    t.value = 0;
    char c = in.get();
    while (c == ' ' || c == '\n')
      c = in.get();

    if (isdigit(c))
    { t.form = "";
      t.value = 0;
      while (isdigit(c))
      { t.form += c;
        t.value = t.value * 10 + c - '0';
        c = in.get(); }
      in.unget();
      t.kind = constint;
      return; }

    else if (c == '{')
    { t.form = "{";
      t.kind = punctuation;
      return; }
    else if (c == '}')
    { t.form = "}";
      t.kind = punctuation;
      return; }
    else if (c == '(')
    { t.form = "(";
      t.kind = punctuation;
      return; }
    else if (c == ')')
    { t.form = ")";
      t.kind = punctuation;
      return; }
    else if (c == '=')
    { t.form = "=";
      t.kind = punctuation;
      return; }
    else if (c == ';')
    { t.form = ";";
      t.kind = punctuation;
      return; }

    else if (c == '+')
    { t.form = "+";
      t.kind = opr;
      return; }
    else if (c == '-')
    { t.form = "-";
      t.kind = opr;
      return; }
    else if (c == '*')
    { t.form = "*";
      t.kind = opr;
      return; }
    else if (c == '/')
    { t.form = "/";
      t.kind = opr;
      return; }
    else if (c == '^')
    { t.form = "^";
      t.kind = opr;
      return; }
    else if (c == '>')
    { t.form = ">";
      t.kind = opr;
      return; }

    else if (isalpha(c))
    { t.form = "";
      while (isalpha(c) || isdigit(c))
      { t.form += c;
        c = in.get(); }
      in.unget();
      if (t.form == "print" || t.form == "while" || t.form == "do" ||
          t.form == "if" || t.form == "then" || t.form == "else")
        t.kind = keyword;
      else
        t.kind = variable;
      return; }

    else if (c == 'D'-64)
    { t.kind = endoffile;
      return; }

    else
    { in.error("invalid character");
      t.kind = unknown;
      return; } }
};

void print_token(token t)
{ cout << "Token, kind=" << kinds[t.kind] << ", form=\"" << t.form << "\", value=" << t.value << "\n"; }


const int Nvariable = 1, Nconstint = 2, Noperator = 3;

string nodekinds[] = { "(zero)", "variable", "constint", "operator" };

struct node
{ int kind;
  string form;
  int value;
  vector <node *> parts;

  node(int k)
  { kind = k;
    value = 0; } };

inputter in("testfile2.txt");
LexAn lex(in);

node * parse_variable()
{ lex.get();
  if (lex.t.kind != variable)
  { in.error("Variable expected");
    exit(1); }
  node * n = new node(Nvariable);
  n->form = lex.t.form;
  return n; }

node * parse_constint()
{ lex.get();
  if (lex.t.kind != constint)
  { in.error("constant integer expected");
    exit(1); }
  node * n = new node(Nconstint);
  n->form = lex.t.form;
  n->value = lex.t.value;
  return n; }

node * parse_expression()
{ lex.get();
  if (lex.t.kind == variable)
  { lex.unget();
    return parse_variable(); }
  if (lex.t.kind == constint)
  { lex.unget();
    return parse_constint(); }
  if (lex.t.form != "(")
  { in.error("Open parenthesis expected");
    exit(1); }
  node * n = new node(Noperator);
  n->parts.push_back(parse_expression());
  lex.get();
  if (lex.t.kind != opr)
  { in.error("Operator expected");
    exit(1); }
  n->form = lex.t.form;
  n->parts.push_back(parse_expression());
  lex.get();
  if (lex.t.form != ")")
  { in.error("Close parenthesis expected");
    exit(1); }
  return n; }

void print_node(node * n, int depth = 0)
{ cout << setw(depth*3) << "" << nodekinds[n->kind]
       << ", form=\"" << n->form << "\""
       << ", value=" << n->value << "\n";
  for (int i = 0; i < n->parts.size(); i += 1)
    print_node(n->parts[i], depth + 1); }

int main()
{ for (int i = 0; true; i += 1)
  { cout << "-------------------------Expression " << i << "\n";
    node * n = parse_expression();
    print_node(n); } }