#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
    cout << '?' << root -> type << '?';
    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 *recognizeAddOp () {

  switch (_iterator.get()) {
  case '+':
    return new ExpTreeNode (ExpTreeNode::PLUS);
  case '-':
    return new ExpTreeNode (ExpTreeNode::MINUS);
  default:
    produceExpectedButFoundMessage ("+ or -");
    return NULL;
  }

}


static ExpTreeNode *recognizeMultOp () {

  switch (_iterator.get()) {
  case '*':
    return new ExpTreeNode (ExpTreeNode::MULTIPLY);
  case '/':
    return new ExpTreeNode (ExpTreeNode::DIVIDE);
  default:
    produceExpectedButFoundMessage ("* or /");
    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 <term>
// <term> :=  <factor> { <mult op> <factor> }*
ExpTreeNode *recognizeTerm () {

  ExpTreeNode *term, *operNode, *factor;

  // recognize the first <factor>
  if ((term = recognizeFactor()) == NULL) return NULL;
  while  ((_iterator.look() == '*') ||
          (_iterator.look() == '/')) {
    // pick up another <multiplicative op><factor>
    if ((operNode = recognizeMultOp()) == NULL) {
      // we should never get here
      delete term;
      return NULL;
    }
    if ((factor = recognizeFactor()) == NULL) {
      delete term;
      delete operNode;
      return NULL;
    }
    // ---- the following gives left associativity ----
    // with a bit of ingenuity (and a stack), right
    // assiciativity can be obtained if desired
    operNode -> left = term; operNode -> right = factor;
    term = operNode;
  }
  return term;

}

// implements rule for <expression>
// <expression> ::=  <term> { <add op> <term> }*
static ExpTreeNode *recognizeExpression () {

  ExpTreeNode *exp, *operNode, *term;

  // recognize the first <term>
  if ((exp = recognizeTerm()) == NULL) return NULL;
  while  ((_iterator.look() == '+') ||
          (_iterator.look() == '-')) {
    // pick up another <additive op><term>
    if ((operNode = recognizeAddOp()) == NULL) {
      // we should never get here
      delete exp;
      return NULL;
    }
    if ((term = recognizeTerm()) == NULL) {
      delete exp;
      delete operNode;
      return NULL;
    }
    // ---- the following gives left associativity ----
    // with a bit of ingenuity (and a stack), right
    // assiciativity can be obtained if desired
    operNode -> left = exp; operNode -> right = term;
    exp = operNode;
  }
  return exp;

}


// 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;

}