题意

求逆波兰表达式的值

限制：

表达式长度不大于$10^{4}10^4$

值绝对值不大于200

方法

栈+遇到符号求值

逆波兰表达式和日常书写的表达式区别是符号会后置。

注意到逆波兰式没有括号，每次符号相当于对最后两个数值进行计算，所以我们可以用栈来记录还未被计算的值。

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param tokens string字符串vector 
     * @return int整型
     */
    int evalRPN(vector<string>& tokens) {
        stack<int>value;
        for(int i = 0;i<tokens.size();i++){
            if(isdigit(tokens[i][tokens[i].size()-1])){ // 有负数
                value.push(stoi(tokens[i])); // 压栈
            }else{ // 运算符
                int v1 = value.top(); // 取出后一个数
                value.pop();
                int v0 = value.top(); // 取出前一个数
                value.pop();
                // 计算
                if(tokens[i][0] == '+')value.push(v0+v1);
                if(tokens[i][0] == '-')value.push(v0-v1);
                if(tokens[i][0] == '*')value.push(v0*v1);
                if(tokens[i][0] == '/')value.push(v0/v1);
            }
        }
        return value.top(); // 返回结果
    }
};

复杂度分析

时间复杂度: 对于每个操作符会发生一次运算，对于每个值一次进栈一次出栈，所以时间复杂度为$O(n)O(n)$

空间复杂度: 最大坏情况先全是数字，后是运算符，所以空间复杂度为$O(n)O(n)$

构树+树上计算

以题目样例为例["2","1","+","4","*"]，它的运算结构如图

相当于计算$((2+1)\ast 4)((2+1)*4)$

考虑先把表达式变成树，再在树上进行运算。

代码

class Solution {
public:
    enum NODETYPE {NUMBER,OP};
    struct Node{ // 树上节点
        int type; // 节点类型
        int val; // 当是数时，表示值
        char op; // 当是运算符时，记录运算符
        struct Node * l; // 运算符时，左节点
        struct Node * r; // 运算符时，右节点
    };
    int calc(Node * n){
        if(n->type == NUMBER){ // 数字
            return n->val;
        }else if(n -> type == OP){ // 运算符
            if(n->op == '+')return calc(n->l)+calc(n->r);
            if(n->op == '-')return calc(n->l)-calc(n->r);
            if(n->op == '*')return calc(n->l)*calc(n->r);
            if(n->op == '/')return calc(n->l)/calc(n->r);
        }
        assert(false);
        return 0;
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param tokens string字符串vector 
     * @return int整型
     */
    int evalRPN(vector<string>& tokens) {
        // write code here
        stack<Node *>n;
        for(int i = 0;i<tokens.size();i++){
            if(isdigit(tokens[i][tokens[i].size()-1])){ // 有负数
                n.push(new Node{NUMBER,stoi(tokens[i]),0,nullptr,nullptr}); // 压栈
            }else{ // 建立运算符的根
                auto r = n.top();
                n.pop();
                auto l = n.top();
                n.pop();
                n.push(new Node{OP,0,tokens[i][0],l,r});
            }
        }
        return calc(n.top());
    }
};

复杂度分析

时间复杂度: 对于构建数，和树上运算都是$O(n)O(n)$

空间复杂度: 需要保存整个树的结构，所以空间复杂度为$O(n)O(n)$