Basic Calculator

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-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

Note: Do not use the eval built-in library function.

//(5), () valid?
//Step 1. convert to reverse polish notation
//Step 2. cal the reverse polish notation expression
//Can the operand overflow 32btis?
class Solution {
public:
    int calculate(string s) {
        vector<string> rpn;
        long ans = 0;
        stack<char> st;
        stack<long> ist;
        size_t i = 0;
        while(i < s.size()){
            char c = s[i];
            if(c == ' ' || c == '\t'){
                i++;
                continue;
            }
            if(isOperator(c)){
                // + - * /
                //If stack is empty, push it
                //If the priority of c is higher than the element on the top, or element on the top is '('', push it
                //While the priority of c is lower or equal to the element on the top, pop stack to ans
                if(st.empty()){
                    st.push(c);
                    i++;
                }
                else if(getPriority(c) > getPriority(st.top())){
                    st.push(c);
                    i++;
                }
                else{
                    rpn.push_back(string(1, st.top()));//BUG HERE, not to_string()
                    st.pop();
                }
            }
            else if(isLeftParenthese(c)){
                st.push(c);
                i++;
            }
            else if(isRightParenthese(c)){
                if(isLeftParenthese(st.top())){
                    st.pop();
                    i++;
                }
                else{
                    rpn.push_back(string(1, st.top()));//BUG HERE
                    st.pop();
                }
            }
            else{
                //operand, may be multiple digits "23" 
                int j = i;
                while(isDigit(s[j]) && j < s.size()){
                    j++;
                }
                rpn.push_back(s.substr(i, j - i));
                i = j;
            }
        }
        //push the last operator in rpn string
        while(st.empty() == false){
            rpn.push_back(string(1, st.top()));//BUG HERE
            st.pop();
        }
        
        //cal reverse polish notation
        for(auto it = rpn.begin(); it != rpn.end(); it++){
            string s = *it;
            if(isDigit(s[0])){
                long num = 0;
                for(size_t i = 0; i < s.size(); i++){
                    num = num * 10 + s[i] - '0';
                    //i++; BUG HERE
                }
                ist.push(num);
            }
            else{
                //operator
                char c = (*it)[0];
                long operand1 = ist.top();
                ist.pop();
                long operand2 = ist.top();
                ist.pop();
                long ans = 0;
                switch(c){
                    case '+':
                        ans = operand2 + operand1;
                        break;
                    case '-':
                        ans = operand2 - operand1;
                        break;
                    case '*':
                        ans = operand2 * operand1;
                        break;
                    case '/':
                        ans = operand2 / operand1;
                        break;
                }
                ist.push(ans);
            }
        }
        return ist.top();
    }
    bool isOperator(char c){
        if(c == '-' || c == '+' || c == '*' || c == '/')
            return true;
        else{
            return false;
        }
    }
    bool isLeftParenthese(char c){
        return c == '(';
    }
    bool isRightParenthese(char c){
        return c == ')';
    }
    int getPriority(char c){
        if(c == '*' || c == '/'){
            return 2;
        }
        else if(c == '+' || c == '-'){
            return 1;
        }
        else {
            return 0;//left parenthese
        }
    }
    bool isDigit(char c){
        return c <= '9' && c >= '0';
    }
};