#include "InfixEvaluator.h"

const std::string InfixEvaluator::operators = "-+/*";
const std::string InfixEvaluator::operands = "0123456789";

int InfixEvaluator::getPrecedence(char op) {
  if(op == '+' || op == '-')
    return 1;
  
  if(op == '*' || op == '/')
    return 2;

  return 0;
}

std::string InfixEvaluator::toPostfix(std::string expr) {
  std::stack<char> myStack;
  std::string result;
  size_t i = 0;
  char c;
  while(i < expr.length()) {
    c = expr.at(i);
    if(isOperand(c)) {
      result.append(1,c);
      if(i+1 < expr.length() && isOperand(expr.at(i+1))) {
        std::cout << "Numbers with multiple digits not allowed";
        exit(1);
      }
    } else if(isOperator(c)) {
      result.append(1,' ');
      while(!myStack.empty() && myStack.top() != '(') {
        if(getPrecedence(myStack.top()) >= getPrecedence(c)) {
          result.append(1,myStack.top());
          myStack.pop();
        } else
          break;
      }
      myStack.push(c);
    } else if (c == '(') {
      myStack.push(c);
    } else if (c == ')') {
      while(!myStack.empty() && myStack.top() != '(') {
        result.append(1,myStack.top());
        myStack.pop();
      }
      if(!myStack.empty()) {
        myStack.pop();
      }
    }
    i++;
  }
  while(!myStack.empty()) {
    result.append(1,myStack.top());
    myStack.pop();
  }
  return result;
}

TreeNode *InfixEvaluator::postfixToTree(std::string expr) {
  std::stack<TreeNode*> myStack;
  TreeNode *newNode;
  TreeNode *op1; TreeNode *op2;
  size_t i = 0;
  char c;

  while(i < expr.length()) {
    c = expr.at(i);
    newNode = new TreeNode;
    if(isOperand(c)) {
      newNode->element = c;
      if(i+1 < expr.length() && isOperand(expr.at(i+1))) {
        std::cout << "Numbers with multiple digits not allowed";
        exit(1);
      }
      newNode->left = NULL; newNode->right = NULL;
      myStack.push(newNode);
    } else if(isOperator(c)){
      op1 = myStack.top(); myStack.pop();
      op2 = myStack.top(); myStack.pop();
      newNode = new TreeNode;
      newNode->element = c;
      newNode->left = op2;
      newNode->right = op1;
      myStack.push(newNode);
    }
    i++;
  }
  return myStack.top();
}

int InfixEvaluator::maxLevel(TreeNode &node) {
  if (&node == NULL)
    return 0;

  return std::max(maxLevel(*node.left), maxLevel(*node.right)) + 1;
}

bool InfixEvaluator::allNull(std::vector<TreeNode*> nodes) {
  for(size_t i = 0; i < nodes.size(); i++) {
    if(nodes[i] != NULL)
      return false;
  }
  return true;
}

void InfixEvaluator::outputSpaces(int number) {
  if(number >= 0)
    std::cout << std::string(number, ' ');
}

void InfixEvaluator::outputNode(std::vector<TreeNode*> nodes, int level, int maxlev) {

  if(nodes.empty() || allNull(nodes))
    return;

  int floor  = maxlev - level;
  int edges = std::pow(2.0f, (std::max(floor - 1,0)));
  int firstSpaces = std::pow(2.0f, floor) - 1;
  int betweenSpaces = std::pow(2.0f, (floor + 1)) - 1;

  std::cout << std::string(firstSpaces, ' ');

  std::vector<TreeNode*> newNodes;

  for(size_t i = 0; i < nodes.size(); i++) {
    if(nodes[i] != NULL) {
      std::cout << nodes[i]->element;
      newNodes.insert(newNodes.end(),nodes[i]->left);
      newNodes.insert(newNodes.end(),nodes[i]->right);
    } else {
      newNodes.insert(newNodes.end(),(TreeNode*)NULL);
      newNodes.insert(newNodes.end(),(TreeNode*)NULL);
      std::cout << ' ';
    }
    outputSpaces(betweenSpaces);
  }

  std::cout << std::endl;

  for(int i = 1; i <= edges; i++) {
    for(size_t j = 0; j < nodes.size(); j++) {
      outputSpaces(firstSpaces-i);
      if(nodes[j] == NULL) {
        outputSpaces(2*edges+i+1);
        continue;
      }
      if(nodes[j]->left != NULL)
        std::cout << '/';
      else
        std::cout << ' ';

      outputSpaces(2*i-1);

      if(nodes[j]->right != NULL)
        std::cout << '\\';
      else
        std::cout << ' ';

      outputSpaces(2*edges-i);
    }
    std::cout << std::endl;
  }

  outputNode(newNodes, level+1, maxlev);

}

void InfixEvaluator::outputTree(TreeNode &root) {
  int maxlev = maxLevel(root);
  std::vector<TreeNode*> nodes;
  nodes.insert(nodes.begin(),&root);
  outputNode(nodes, 1, maxlev);
}

void InfixEvaluator::outputTreeExpr(std::string expr) {
  outputTree(*postfixToTree(toPostfix(expr)));
}