32ms C++ code with two stacks, one pass


  • 0
    J

    One stack for operators another for operands. Basic idea is pushing when '(' shows up, popping when ')' shows up. Set default 'op' and 'operand' value to reduce code lines.

    class Solution {
    public:
        int calculate(string s) {
            if(s.size()==0) return 0;
            int size = (int) s.size();
            int i = 0;
            char op = '+'; stack<char> operators;
            int operand = 0; stack<int> num;
            while (i<size) {
                if (s[i]>='0' && s[i]<='9') {
                    int begin = i;
                    while(i<size && s[i]>='0' && s[i]<='9') i++;
                    i--;
                    int thisNum = stoi(s.substr(begin,i+1-begin));
                    operand = operate(operand, thisNum, op);
                }
                else if(s[i]=='+' || s[i]=='-') {
                    op = s[i];
                }
                else if(s[i]=='(') {
                    num.push(operand); operators.push(op);
                    operand = 0; op = '+';
                }
                else if(s[i]==')') {
                    op = operators.top(); operators.pop();
                    operand = operate(num.top(), operand, op); num.pop();
                }
                i++;
            }
            return operand;
        }
        
        
        int operate(int& op1, int& op2, char& op) {
            if(op=='+') op1 = op1 + op2;
            if(op=='-') op1 = op1 - op2;
            return op1;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.