题解 | #逆波兰表达式求值#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param tokens string字符串vector 
     * @return int整型
     */
    int evalRPN(vector<string>& tokens) {
        // write code here
        stack<int> s;
        for(int i =0; i<tokens.size(); i++) {
            if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
                int n = s.top();
                s.pop();
                int m = s.top();
                s.pop();
                if(tokens[i] == "+") s.push(n + m);
                if(tokens[i] == "-") s.push(m - n);
                if(tokens[i] == "*") s.push(m * n);
                if(tokens[i] == "/") s.push(m / n);

            }
            else {
                s.push(stoi(tokens[i]));
            }
        }
        return s.top();
    }
};

使用stack，所求为逆波兰表达式，运算符在运算数的后面，可以使用辅助栈，因为每个运算符的运算都和前一个运算的结果相关，相当于递归，所以将前面的运算结果保存到栈中，每次运算时，取两次栈顶元素，即可得到运算数，算出实际运算结果，后，将他们也压入栈，备用，直到下一次运算再拿出来。