题目描述

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

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

Note:

Division between two integers should truncate toward zero.
The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation.

样例

Example 1:

Input: ["2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9
Example 2:

Input: ["4", "13", "5", "/", "+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6
Example 3:

Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
Output: 22
Explanation: 
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

算法1

(Stack) $O(n)$

遍历数组，将数字存放到栈中，遇到运算符弹出两个数字进行运算，然后将结果放回到栈中。
总结：表达式计算用栈实现容易扩展，一个栈存数字，一个栈存运算符

时间复杂度

遍历一次，O（n）
需要栈存放数字，O（n）

参考文献

C++ 代码

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for(auto token:tokens)
        {
            if(isdigit(token.back()))
            {
                int sign=1;
                string str;
                if(token[0]=='-' ||token[0]=='+')
                {
                    str=token.substr(1);
                    if(token[0]=='-') sign=-1;
                }
                else
                    str=token;

                int number=stoi(str)*sign;
                st.push(number);

            }
            else
            {
                if(st.size()>=2)
                {
                    auto a=st.top(); st.pop();
                    auto b=st.top(); st.pop();
                    int res=0;
                    if(token=="+") res=b+a;
                    else if(token=="-") res=b-a;
                    else if(token=="*") res=b*a;
                    else res=b/a;
                    st.push(res);
                }
            }
        }
        return st.top();
    }
};