Two ways to evalute rpn


  • 0
    1. From left to right.
        int evalRPN(vector<string>& tokens) {
            stack<int> stk;
            for(auto &s:tokens) {
                int op1,op2;
                if(s=="+"||s=="-"||s=="*"||s=="/") {
                    op1 = stk.top();
                    stk.pop();
                    op2 = stk.top();
                    stk.pop();
                } else stk.push(stoi(s));    
                if(s=="+") stk.push(op1+op2);
                if(s=="-") stk.push(op2-op1);
                if(s=="*") stk.push(op2*op1);
                if(s=="/") stk.push(op2/op1);
            }
            return stk.top();
        }
    
    1. From right to left, the great idea is from @yakov-sum
        int evalRPN(vector<string>& tokens) {
            string s=tokens.back();
            tokens.pop_back();
            if(s=="+"||s=="-"||s=="*"||s=="/") {
                int op1 = evalRPN(tokens), op2 = evalRPN(tokens);
                if(s=="+") return op2+op1;
                if(s=="-") return op2-op1;
                if(s=="*") return op2*op1;
                if(s=="/") return op2/op1;
            }
            return stoi(s);
        }
    

Log in to reply
 

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