LeetCode Q224 Basic Calculator

Question:

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.

Solution: 

class Solution {
public:
    void infixToPostfix(string s, vector<string> &output){
        vector<char> stack;
        for (int i = 0; i < s.size(); ++i) {
            string res;
            while (i <s.size()&& s[i] >= '0' && s[i] <= '9')
                res += s[i++];
            if (res.size() != 0)
                output.push_back(res);
        
            if (s[i] == '(') 
                stack.push_back(s[i]);
        
            else if (s[i] == ')') {
                while (!stack.empty() && stack.back() != '(') {
                    string t(1,stack.back());
                    output.push_back(t);
                    stack.pop_back();
                }
                stack.pop_back();
            }
            else if (s[i]=='+' || s[i]=='-') {//"+", "-"
                while (!stack.empty()&& stack.back() != '(') {
                    string t (1,stack.back());
                    output.push_back (t);
                    stack.pop_back ();
                }
                stack.push_back(s[i]);
            }
        }
        while(!stack.empty()){
            string t(1,stack.back());
            output.push_back(t);
            stack.pop_back();
        }
    }

    int evalRPN(vector<string> &tokens) {
        vector<int> stack;
        for(int i = 0; i < tokens.size(); ++i){
            if ( tokens[i].size() > 1 || ( tokens[i][0] >= '0' && tokens[i][0] <= '9' ) ){
                stack.push_back(stoi(tokens[i]));
                continue;
            }
            int number1 = stack.back();
            stack.pop_back();
            int number2 = stack.back();
            stack.pop_back();
            switch(tokens[i][0])
            {
                case '+':
                    number2 += number1;
                    break;
                case '-':
                    number2 -= number1;
                    break;
                default:
                    break;
            }
            stack.push_back(number2);
        }
        return stack.back();
    }
    
    int calculate(string s) {
        vector<string> postfixExpression;
        infixToPostfix (s, postfixExpression);
        return evalRPN (postfixExpression);
    }
};

New Version

class Solution {
public:
    void getAnswer(vector<char> &operators, vector<int> &numbers){
            int number1 = numbers.back();
            numbers.pop_back();
            int number2 = numbers.back();
            numbers.pop_back();
            int res = operators.back() == '+' ? number2 + number1 : number2 - number1;
            numbers.push_back(res);
            operators.pop_back();
        
    }
    
    int calculate(string s){
        vector<char> operators;
        vector<int> numbers;
        for (int i = 0; i < s.size(); ++i) {
            string res;
            while (i <s.size()&& s[i] >= '0' && s[i] <= '9')
                res += s[i++];
            if (res.size())
                numbers.push_back(stoi(res));
                
            if (s[i] == '('  ) 
                operators.push_back(s[i]);
        
            else if (s[i] == ')'|| s[i]=='+' || s[i]=='-') {
                if (!operators.empty() && operators.back()!='(')
                    getAnswer(operators, numbers);
                (s[i] == ')') ? operators.pop_back() :  operators.push_back(s[i]);
            }
        }
        if (!operators.empty()){
           getAnswer(operators, numbers);
        }
        return numbers.back();
    }
           
};

Java

public class Solution {
    public int calculate(String s) {
        Stack<Integer> numbers = new Stack<Integer>();
        int num = 0, res = 0, sign = 1;
        for (int i = 0; i < s.length(); i++){
            if (Character.isDigit(s.charAt(i))){
                num = num * 10 + s.charAt(i) - '0';
            }else if (s.charAt(i) == '+' || s.charAt(i) == '-'){
                res += num * sign;
                sign = (s.charAt(i) == '+') ? 1 : -1;
                num = 0;//reset
            }else if (s.charAt(i) == '('){ //push the result to the stack
                numbers.push(res);
                numbers.push(sign);
                res = 0;//reset
                sign = 1;//reset
            }else if (s.charAt(i) == ')') { //remove () and pop the pre-result from the stack
                res += num * sign;
                res *= numbers.pop();
                res += numbers.pop();
                num = 0;//reset
            }
        }
        if (num != 0) res += num * sign;
        return res;
    }
}