题解 | #牛的表达式计算器# 后缀表达式求值

知识点

后缀表达式 栈

思路

后缀表达式求值，可以一个栈来记录数字，每当遇到预算符号，取出栈顶的两个数字进行运算，把结果重新入栈。

最后的栈顶即为全部的计算结果。

时间复杂度

只遍历了一遍数组，每次出入栈的次数是常数次，时间复杂度为

AC code（C++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param tokens string字符串vector 
     * @return int整型
     */
    int calculatePostfix(vector<string>& tokens) {
        stack<int> nums;
        for (auto& s : tokens) {
            if (s == "+") {
                auto a = nums.top();
                nums.pop();
                auto b = nums.top();
                nums.pop();
                nums.push(b + a);
            }
            else if (s == "-") {
                auto a = nums.top();
                nums.pop();
                auto b = nums.top();
                nums.pop();
                nums.push(b - a);
            }
            else if (s == "*") {
                auto a = nums.top();
                nums.pop();
                auto b = nums.top();
                nums.pop();
                nums.push(b * a);
            }
            else if (s == "/") {
                auto a = nums.top();
                nums.pop();
                auto b = nums.top();
                nums.pop();
                nums.push(b / a);
            }
            else {
                auto a = stoi(s);
                nums.push(a);
            }
        }
        return nums.top();
    }
};