题目描述

计算逆波兰表达式的值。

表达式中的运算符仅包含 +,-,*,/。

注意：

• /表示整除运算；
• 给定的逆波兰表达式一定合法。即不会导致除零运算。

样例1

输入：["2", "1", "+", "3", "*"]
输出：9
解释：((2 + 1) * 3) = 9

样例2

输入：["4", "13", "5", "/", "+"]
输出：6
解释：(4 + (13 / 5)) = 6

样例3

输入：["10", "6", "9", "3", "+", "-11", "*",
            "/", "*", "17", "+", "5", "+"]
输出：22
解释：
  ((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

算法

(栈操作) $O(n)$

遍历所有元素。如果当前元素是整数，则压入栈；如果是运算符，则将栈顶两个元素弹出做相应运算，再将结果入栈。
最终表达式扫描完后，栈里的数就是结果。

时间复杂度分析：每个元素仅被遍历一次，且每次遍历时仅涉及常数次操作，所以时间复杂度是 $O(n)$。

C++ 代码

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> sta;
        for (auto &t : tokens)
            if (t == "+" || t == "-" || t == "*" || t == "/")
            {
                int a = sta.top();
                sta.pop();
                int b = sta.top();
                sta.pop();
                if (t == "+") sta.push(a + b);
                else if (t == "-") sta.push(b - a);
                else if (t == "*") sta.push(a * b);
                else sta.push(b / a);
            }
            else sta.push(atoi(t.c_str()));
        return sta.top();
    }
};