// Source: http://www.daniweb.com/software-development/cpp/code/427500/calculator-using-shunting-yard-algorithm#
// Author: Jesse Brown
// Modifications: Brandon Amos

#include <cstdlib>
#include <iostream>
#include <sstream>
#include <stdexcept>

#include "shunting_yard.h"

using namespace std;

#define isvariablechar(c) (isalpha(c) || c == '_')
TokenQueue_t calculator::toRPN(const char* expr,
    map<string, string>* vars,
    map<string, int> opPrecedence) {
    TokenQueue_t rpnQueue; stack<string> operatorStack;
    bool lastTokenWasOp = true;

    // In one pass, ignore whitespace and parse the expression into RPN
    // using Dijkstra's Shunting-yard algorithm.
    while (*expr && isspace(*expr)) ++expr;
    while (*expr) {
        if (isdigit(*expr)) {
            // If the token is a number, add it to the output queue.
            char* nextChar = 0;
            double digit = strtod(expr, &nextChar);
#     ifdef DEBUG
            cout << digit << endl;
#     endif
            rpnQueue.push(new Token<double>(digit));
            expr = nextChar;
            lastTokenWasOp = false;
        }
        else if (isvariablechar(*expr)) {
            // If the function is a variable, resolve it and
            // add the parsed number to the output queue.
            if (!vars) {
                //throw domain_error(
                    //"Detected variable, but the variable map is null.");
            }

            stringstream ss;
            ss << *expr;
            ++expr;
            while (isvariablechar(*expr)) {
                ss << *expr;
                ++expr;
            }
            string key = ss.str();
            map<string, string>::iterator it = vars->find(key);
            if (it == vars->end()) {
                //throw domain_error(
                    //"Unable to find the variable '" + key + "'.");
            }
            string val = vars->find(key)->second;
#     ifdef DEBUG
            cout << val << endl;
#     endif
            rpnQueue.push(new Token<string>(val));;
            lastTokenWasOp = false;
        }
        else {
            // Otherwise, the variable is an operator or paranthesis.
            switch (*expr) {
            case '(':
                operatorStack.push("(");
                ++expr;
                break;
            case ')':
                while (operatorStack.top().compare("(")) {
                    rpnQueue.push(new Token<string>(operatorStack.top()));
                    operatorStack.pop();
                }
                operatorStack.pop();
                ++expr;
                break;
            default:
            {
                // The token is an operator.
                //
                // Let p(o) denote the precedence of an operator o.
                //
                // If the token is an operator, o1, then
                //   While there is an operator token, o2, at the top
                //       and p(o1) <= p(o2), then
                //     pop o2 off the stack onto the output queue.
                //   Push o1 on the stack.
                stringstream ss;
                ss << *expr;
                ++expr;
                while (*expr && !isspace(*expr) && !isdigit(*expr)
                    && !isvariablechar(*expr) && *expr != '(' && *expr != ')') {
                    ss << *expr;
                    ++expr;
                }
                ss.clear();
                string str;
                ss >> str;
#           ifdef DEBUG
                cout << str << endl;
#           endif

                if (lastTokenWasOp) {
                    // Convert unary operators to binary in the RPN.
                    if (!str.compare("-") || !str.compare("+")) {
                        rpnQueue.push(new Token<double>(0));
                    }
                    else {
                        //throw domain_error(
                            //"Unrecognized unary operator: '" + str + "'.");
                    }
                }

                while (!operatorStack.empty() &&
                    opPrecedence[str] <= opPrecedence[operatorStack.top()]) {
                    rpnQueue.push(new Token<string>(operatorStack.top()));
                    operatorStack.pop();
                }
                operatorStack.push(str);
                lastTokenWasOp = true;
            }
            }
        }
        while (*expr && isspace(*expr)) ++expr;
    }
    while (!operatorStack.empty()) {
        rpnQueue.push(new Token<string>(operatorStack.top()));
        operatorStack.pop();
    }
    return rpnQueue;
}

double calculator::calculate(const char* expr,
    map<string, string>* vars) {
    // 1. Create the operator precedence map.
    map<string, int> opPrecedence;
    opPrecedence["("] = -1;
    opPrecedence["<<"] = 1; opPrecedence[">>"] = 1;
    opPrecedence["+"] = 2; opPrecedence["-"] = 2;
    opPrecedence["*"] = 3; opPrecedence["/"] = 3;

    // 2. Convert to RPN with Dijkstra's Shunting-yard algorithm.
    TokenQueue_t rpn = toRPN(expr, vars, opPrecedence);

    // 3. Evaluate the expression in RPN form.
    stack<double> evaluation;
    while (!rpn.empty()) {
        TokenBase* base = rpn.front();
        rpn.pop();

        Token<string>* strTok = dynamic_cast<Token<string>*>(base);
        Token<double>* doubleTok = dynamic_cast<Token<double>*>(base);
        if (strTok) {
            string str = strTok->val;
            /*if (evaluation.size() < 2) {
                throw domain_error("Invalid equation.");
            }*/

            if (str.compare("pi")){
                cout << "its pi!" << endl;
            }

            double right = evaluation.top(); evaluation.pop();
            double left = evaluation.top(); evaluation.pop();
            if (!str.compare("+")) {
                evaluation.push(left + right);
            }
            else if (!str.compare("*")) {
                evaluation.push(left * right);
            }
            else if (!str.compare("-")) {
                evaluation.push(left - right);
            }
            else if (!str.compare("/")) {
                evaluation.push(left / right);
            }
            else if (!str.compare("<<")) {
                evaluation.push((int)left << (int)right);
            }
            else if (!str.compare(">>")) {
                evaluation.push((int)left >> (int)right);
            }
            else {
                cout << "Unknown Operator" << endl;
                //throw domain_error("Unknown operator: '" + str + "'.");
            }
        }
        else if (doubleTok) {
            evaluation.push(doubleTok->val);
        }
        else {
            //throw domain_error("Invalid token.");
        }
        delete base;
    }
    return evaluation.top();
}