60-逆波兰表达式求值

逆波兰表达式就是后缀表达式的洋气叫法。

自己的做法

算法思想

这题的做法，已经写在上面逆波兰表达式的优点里了。

使用栈，碰到运算符，则从栈中取两个数，将运算得到的数再入栈。

要注意的是：数的运算顺序，先弹栈的数放后面，再弹栈的数放前面。

算法实现

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> s;
        for(string str : tokens) {
            if(str == "+" || str == "-" || str == "*" || str == "/") {
                int num1 = s.top();
                s.pop();
                int num2 = s.top();
                s.pop();
                if(str == "+") {
                    s.push(num2 + num1);
                } else if(str == "-") {
                    s.push(num2 - num1);
                } else if(str == "*") {
                    s.push(num2 * num1);
                } else {
                    s.push(num1 / num1);
                }
            } else {
                //使用stoi函数，将字符串转为数字
                s.push(stoi(str));
            }
        }
        return s.top();
    }
};

性能分析

时间复杂度：$O(n)$。

空间复杂度：$O(n)$。