150 - Evaluate Reverse Polish Notation

Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Hide Tags

Stack

Hide Similar Problems

(M) Basic Calculator

非常 straight forward 的一道题，遇数字压栈，遇符号出栈算完了再压栈。
注意出栈的时候，两个数字的顺序是相反的，要倒过来计算。
另外除数不能为0。

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        int rst=0;
        int sz=tokens.size();
        if(sz)
        {
            stack<int> stk;
            int a=0, b=0;
            for(int ii=0; ii<sz; ++ii)
            {
                if("+" == tokens[ii])
                {
                    a=stk.top(), stk.pop();
                    b=stk.top(), stk.pop();
                    stk.push(b+a);
                }
                else if("-" == tokens[ii])
                {
                    a=stk.top(), stk.pop();
                    b=stk.top(), stk.pop();
                    stk.push(b-a);
                }
                else if("*" == tokens[ii])
                {
                    a=stk.top(), stk.pop();
                    b=stk.top(), stk.pop();
                    stk.push(b*a);
                }
                else if("/" == tokens[ii])
                {
                    a=stk.top(), stk.pop();
                    b=stk.top(), stk.pop();
                    a ? stk.push(b/a) : stk.push(0);
                }
                else
                    stk.push(atoi(tokens[ii].data()));
            }
            rst=stk.top();
        }
        return rst;
    }
};
16 ms.