C++ code, stack, O(n)


  • 0
    Y
    class Solution {
    public:
        bool isDigits(char c) {
            return c-'0' >=0 && c-'0' <=9;
        }
        void compute(stack<int>& operands, stack<char>& operators) {
            int o2=operands.top();
            operands.pop();
            int o1=operands.top();
            operands.pop();
            if(operators.top()=='+')
                operands.push(o1+o2);
            else if(operators.top()=='-')
                operands.push(o2-o1);
            operators.pop();
        }
        int calculate(string s) {
            stack<int> operands;
            stack<char> operators;
            s='('+s+')';
            for(int i=s.size()-1;i>=0;) {
                if(s[i]==')'||s[i]=='+'||s[i]=='-')
                    operators.push(s[i--]);
                else if(isDigits(s[i])) {
                    int j=i;
                    for(;j>=0&&isDigits(s[j]);j--);
                    operands.push(atoi(s.substr(j+1,i-j+1).c_str()));
                    i=j;
                }
                else if(s[i]=='(') {
                    while(operators.top()!=')') {
                        compute(operands,operators);
                    }
                    operators.pop();
                    i--;
                }
                else i--;
            }
            return operands.top();
        }
    };

Log in to reply
 

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