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

题目的主要信息：

• 给定一个逆波兰表达式，求表达式的值
• 给定的表达式以字符串数组给出，字符串只含有数组和加减乘除四个符号
• 除法进行整型运算

方法一：栈

具体做法：

逆波兰表达式可以看成一种后序表达式，只需要在遇到符号的时候计算它前面两个数字即可，因此可以使用栈的先进后出原理。

遍历整个字符串数组，遇到数字就将其从字符串转变成int数字，然后加入栈中等待计算。遇到符号先取出栈中最后一位，然后与取出后的最后一位计算，结果存入最后一位，如下图所示：

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for(int i = 0; i < tokens.size(); i++){
            string s = tokens[i];
            if(s != "+" && s != "-" && s != "*" && s != "/")
                st.push(stoi(s)); //遇到数字加入栈中
            else{ //遇到符号，拿出栈中最近的两个元素计算
                int num = st.top();
                st.pop();
                switch(s[0]){ //根据符号运算
                    case '+': st.top() += num; break; //结果存入前一个数
                    case '-': st.top() -= num; break;
                    case '*': st.top() *= num; break;
                    case '/': st.top() /= num; break;
                }
            }
        }
        return st.top(); //栈中最终留下的就是答案
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，遍历整个字符串数组
• 空间复杂度：$O(n)O(n)$，栈空间最大为数组长度，即全是数字

方法二：数组模拟栈

具体做法：

既然方法一每次遇到符号前运算的都是其前两个数字，因此我们可以使用数组来模拟栈，只需要一个指针指向数字结尾即可。每次遇到数字字符串，将其转换成int数字后加入数组，同时指针后移，遇到运算符号就指针前移两位获取最近的两个数字，然后将其运算后的结果再存入数组。运算结束后，根据指针所指的第一个数字就是结果，与上述栈原理一致，甚至也可以参考方法一的图示。

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        int n = tokens.size();
        vector<int> stack(n, 0);
        int top = 0;
        for(int i = 0; i < n; i++){
            string s = tokens[i];
            if(s != "+" && s != "-" && s != "*" && s != "/")
                stack[top++] = stoi(s);
            else{
                int num2 = stack[--top];
                int num1 = stack[--top];
                switch(s[0]){
                    case '+': stack[top++] = num1 + num2; break;
                    case '-': stack[top++] = num1 - num2; break;
                    case '*': stack[top++] = num1 * num2; break;
                    case '/': stack[top++] = num1 / num2; break;
                }
            }
        }
        return stack[top - 1];
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，遍历整个字符串数组
• 空间复杂度：$O(n)O(n)$，设置了长度为n的辅助数组