Basic Calculator III

Description

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negativeintegers and empty spaces .

The expression string contains only non-negative integers, +, -, *, / operators , open ( and closing parentheses ) and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-2147483648, 2147483647].

Solution

enum Type {
    NUM,
    MUL,
    DIV,
    SUB,
    ADD,
    LEFT,
    RIGHT
};

class Solution {
public:
    int calculate(string s) {
        int index = 0;
        
        stack<string> operatorStack;
        queue<string> retQueue;
        
        while (index < s.size()) {
            while(index < s.size() && s[index] == ' ') ++index;
            if (index >= s.size()) break;
            string cur = string(1, s[index]);
            switch(judge(cur)) {
                case NUM:
                    cur = parse(index, s);
                    retQueue.push(cur);
                    break;
                case MUL:
                    while (!operatorStack.empty() && 
                        (operatorStack.top() == "*" || 
                            operatorStack.top() == "/")) {
                        retQueue.push(operatorStack.top());
                        operatorStack.pop();
                    }
                    operatorStack.push(cur);
                    ++index;
                    break;
                case DIV:
                    while (!operatorStack.empty() && 
                        (operatorStack.top() == "*" || 
                            operatorStack.top() == "/")) {
                        retQueue.push(operatorStack.top());
                        operatorStack.pop();
                    }
                    operatorStack.push(cur);
                    ++index;
                    break;
                case SUB:
                    while (!operatorStack.empty() && operatorStack.top() != "(") {
                        retQueue.push(operatorStack.top());
                        operatorStack.pop();
                    }
                    operatorStack.push(cur);
                    ++index;
                    break;
                case ADD:
                    while (!operatorStack.empty() && operatorStack.top() != "(") {
                        retQueue.push(operatorStack.top());
                        operatorStack.pop();
                    }
                    operatorStack.push(cur);
                    ++index;
                    break;
                case LEFT:
                    operatorStack.push(cur);
                    ++index;
                    break;
                case RIGHT:
                    while(!operatorStack.empty() && operatorStack.top() != "(") {
                        retQueue.push(operatorStack.top());
                        operatorStack.pop();
                    }
                    operatorStack.pop(); //pop the '('
                    ++index;
                    break;
            }
        }
        while (!operatorStack.empty()) {
            retQueue.push(operatorStack.top());
            operatorStack.pop();
        }
        
        stack<long> helper;
        while (!retQueue.empty()) {
            string& s = retQueue.front();
            retQueue.pop();
            if (judge(s) != NUM) {
                long r = helper.top();
                helper.pop();
                long l = helper.top();
                helper.pop();
                helper.push(function(s, l, r) );
            }else{
                helper.push(stol(s));
            }
        }
        
        return helper.top();
    }
    
    string parse(int& index, string& s) {
        string ret = "";
        while (index < s.size() && s[index] <= '9' && s[index] >= '0') {
            ret += s[index];
            ++index;
        }
        
        return ret;
    }
    
    long function(string& op, long leftNumber, long rightNumber) {
        switch (op[0]) {
            case '-':
                return leftNumber - rightNumber;
            case '+':
                return leftNumber + rightNumber;
            case '/':
                return leftNumber / rightNumber;
            case '*':
                return leftNumber * rightNumber;
        }
        return -1; //Wrong
    }
    
    Type judge(string& c) {
        if (c == "(") return LEFT;
        if (c == ")") return RIGHT;
        if (c == "+") return ADD;
        if (c == "-") return SUB;
        if (c == "*") return MUL;
        if (c == "/") return DIV;
        return NUM;
    }
};