#include "stdstuff.h"

#include "Iterator.h"
#include "Parser.h"

// globally accessible _iterator object.
Iterator _iterator;


// works even if tree incomplete (i.e. an operator node woth no children)
// as long as pointers are null when children don't exist.  this is
// guaranteed by the node constructor.
void deleteExpTree (ExpTreeNode *root) {

  if (root -> left != NULL) {
    deleteExpTree (root -> left);
  }
  if (root -> right != NULL) {
    deleteExpTree (root -> right);
  }
  delete root;

}


int evaluateExpTree  (ExpTreeNode *root) {

  switch (root -> type) {
  case ExpTreeNode::PLUS:
    return evaluateExpTree(root -> left) +
           evaluateExpTree(root -> right);
  case ExpTreeNode::MINUS:
    return evaluateExpTree(root -> left) -
           evaluateExpTree(root -> right);
  case ExpTreeNode::MULTIPLY:
    return evaluateExpTree(root -> left) *
           evaluateExpTree(root -> right);
  case ExpTreeNode::DIVIDE:
    // we could usefully check for division by zero here
    return evaluateExpTree(root -> left) /
           evaluateExpTree(root -> right);
  case ExpTreeNode::NUMBER:
    return  root -> value;
  case ExpTreeNode::UNDEFINED:
  default:
    // should really throw an exception
    return -1;
  }

}


void outputInfixExpression (ExpTreeNode *root) {

  switch (root -> type) {
  case ExpTreeNode::PLUS:
    cout << '(';
    outputInfixExpression(root -> left);
    cout << " + ";
    outputInfixExpression(root -> right);
    cout << ')';
    break;
  case ExpTreeNode::MINUS:
    cout << '(';
    outputInfixExpression(root -> left);
    cout << " - ";
    outputInfixExpression(root -> right);
    cout << ')';
    break;
  case ExpTreeNode::MULTIPLY:
    cout << '(';
    outputInfixExpression(root -> left);
    cout << " * ";
    outputInfixExpression(root -> right);
    cout << ')';
    break;
  case ExpTreeNode::DIVIDE:
    cout << '(';
    outputInfixExpression(root -> left);
    cout << " / ";
    outputInfixExpression(root -> right);
    cout << ')';
    break;
  case ExpTreeNode::NUMBER:
    cout << root -> value;
    break;
  case ExpTreeNode::UNDEFINED:
  default:
    // should really throw an exception
    break;
  }

}


void outputPostfixExpression (ExpTreeNode *root) {

  switch (root -> type) {
  case ExpTreeNode::PLUS:
    outputPostfixExpression(root -> left);
    outputPostfixExpression(root -> right);
    cout << " +";
    break;
  case ExpTreeNode::MINUS:
    outputPostfixExpression(root -> left);
    outputPostfixExpression(root -> right);
    cout << " -";
    break;
  case ExpTreeNode::MULTIPLY:
    outputPostfixExpression(root -> left);
    outputPostfixExpression(root -> right);
    cout << " *";
    break;
  case ExpTreeNode::DIVIDE:
    outputPostfixExpression(root -> left);
    outputPostfixExpression(root -> right);
    cout << " /";
    break;
  case ExpTreeNode::NUMBER:
    cout << ' ' << root -> value;
    break;
  case ExpTreeNode::UNDEFINED:
  default:
    // should really throw an exception
    break;
  }

}


static void produceExpectedButFoundMessage (String2002 str) {

  char ch = _iterator.lastLook();
  int index = _iterator.lastLookIndex();

  cout << "** Error Detected **\n" << _iterator.getString2002() << endl;
  for (int i = 0; i < index; i++) {
    cout << ' ';
  }
  cout << "I\n";

  if (ch == Iterator::EOS) {
     cout << "Expected " << str << " but found end of expression.\n";
  } else {
     cout << "Expected " << str << " but found " << ch  << ".\n";
  }
}


static ExpTreeNode *recognizeNumber () {

  int value;

  if (!isdigit(_iterator.look())) {
    produceExpectedButFoundMessage ("digit");
    return NULL;
  }
  value = _iterator.get() - '0';
  // consume as many digits as possible
  while (isdigit(_iterator.look())) {
    value = (value * 10) + (_iterator.get() - '0');
  }
  return new ExpTreeNode (ExpTreeNode::NUMBER, value);

}


static ExpTreeNode *recognizeOperator () {

  switch (_iterator.get()) {
  case '+':
    return new ExpTreeNode (ExpTreeNode::PLUS);
  case '-':
    return new ExpTreeNode (ExpTreeNode::MINUS);
  case '*':
    return new ExpTreeNode (ExpTreeNode::MULTIPLY);
  case '/':
    return new ExpTreeNode (ExpTreeNode::DIVIDE);
  default:
    produceExpectedButFoundMessage ("operator");
    return NULL;
  }

}


// need prototype do that this function can be used by recognizeFactor
static ExpTreeNode *recognizeExpression ();


// implements rule for <factor>
// <factor> ::= <number> |
//              (<expression>)
static ExpTreeNode *recognizeFactor () {

  ExpTreeNode *exp;

  if (_iterator.look() == '(') {
    // apply rule <factor> := ( <expression> )
    _iterator.get(); // cross off the opening bracket
    if ((exp = recognizeExpression()) == NULL) return NULL;
    if (_iterator.get() != ')') {
      produceExpectedButFoundMessage (")");
      return NULL;
    }
    return exp;
  } else {
    // apply rule <factor> := <number>
    return recognizeNumber ();
  }

}


// implements rule for <expression>
// <expression> ::= <factor> |
//                  <factor><operator><expression>
static ExpTreeNode *recognizeExpression () {

  ExpTreeNode *factor, *operNode, *exp;
  char nextChar;

  if ((factor = recognizeFactor()) == NULL) return NULL;
  nextChar = _iterator.look(); // for convenience
  if ((nextChar != '+') && (nextChar != '-') &&
      (nextChar != '*') && (nextChar != '/')) {
    // apply rule <expression> := factor
    return factor;
  } else {
    // apply rule <expression> := <factor> <operator> <expression>
    // note: at this point calling recognizeOperator is a bit of
    // a waste of time as we've already determined that the
    // current character is a valid operator and could easily just
    // create the required node ourselves.
    if ((operNode = recognizeOperator()) == NULL) {
      // ?? it should be impossible to get here
      delete factor;
      return NULL;
    }
    if ((exp = recognizeExpression()) == NULL) {
      delete factor;
      delete operNode;
      return NULL;
    }
    operNode -> left = factor; operNode -> right = exp;
    return operNode;
  }

}


// on success, returns reference to root node of the parse tree.
// otherwise returns NULL after outputting an appropriate error message.
ExpTreeNode *createExpTree (String2002 str) {

  ExpTreeNode *exp;

  _iterator.setup (str);
  if ((exp = recognizeExpression ()) == NULL) return NULL;
  if (_iterator.look() != Iterator::EOS) {
    produceExpectedButFoundMessage ("end of expression");
    deleteExpTree(exp);
    return NULL;
  }
  return exp;

}