题目

链接：150. 逆波兰表达式求值
难度：Medium

题解

分析

逆波兰式也是一个经典问题了。在逆波兰式中总是先遇到操作数再遇到操作符，而且遇到操作符时最近遇到的数字就是其操作数。所以，可以用一个栈来保存操作数，当遇到操作符时从栈顶取出操作符需要的操作数，进行运算后再入栈；当一个有效的逆波兰式遍历结束之后，栈中有且只有一个数字，这个数字就是计算结果。

时间复杂度

每个元素至少访问一次，$O(n)$

实现

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> num;
        int top;
        for(int i = 0; i < tokens.size(); ++i) {
            if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
                top = num.top();
                num.pop();
                if(tokens[i] == "+") {
                    top = num.top() + top;
                } else if(tokens[i] == "-") {
                    top = num.top() - top;
                } else if(tokens[i] == "*") {
                    top = num.top() * top;
                } else {
                    top = num.top() / top;
                }
                num.pop();
                num.push(top);
            } else {
                num.push(stoi(tokens[i]));
            }
        }
        return num.top();
    }
};