yxc题解
其他题解1：LeetCode 150. 逆波兰表达式求值（携程笔试题 新鲜出炉）

算法

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

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

class Solution {
public:
    stack<int> stk;
    void eval(string s) {
        int b = stk.top(); stk.pop();
        int a = stk.top(); stk.pop();

        if (s == "+") stk.push(a + b);
        else if (s == "-") stk.push(a - b);
        else if (s == "*") stk.push(a * b);
        else stk.push(a / b);  //C++中整除就是直接取整，不是下取整  -1.2取整就是-1
    }

    int evalRPN(vector<string>& tokens) {
        unordered_set<string> S{"+", "-", "*", "/"}; // 把所有的操作符先存下来
        for (auto& s : tokens) { // 枚举表达式中的所有字符   不加&也是可以ac，因为后面不需要s了，所以不用存它变后的值
            if (S.count(s)) eval(s); // 如果当前字符是运算符，则eval(s)
            else stk.push(stoi(s)); // 否则说明是数字，则数字进栈
        }
        return stk.top(); // 最终栈顶元素（根节点）就是结果
    }
};