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

#include <string>
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        // write code here
        stack <int> str;
		//老辅助栈了
        for(int i = 0; i < tokens.size(); i++){
            if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/"){
                int n1 = str.top();
                str.pop();
                int n2 = str.top();
                str.pop();
			  //扔出来两个数
                if(tokens[i] == "+") str.push(n2 + n1);
                if(tokens[i] == "-") str.push(n2 - n1);//注意这是个栈 先进后出
                if(tokens[i] == "*") str.push(n2 * n1);
                if(tokens[i] == "/") str.push(n2 / n1);//后面出来的n2应该是被除数或者被减数
            }
            else {
                str.push(stoi(tokens[i]));// string to interger
            }
        }
        return str.top();
    }
};

算法基本思想：

使用栈来模拟计算过程。遍历表达式中的每个元素，如果遇到操作符，则从栈中弹出两个操作数进行计算，并将计算结果压入栈中；如果遇到操作数，则将其压入栈中。最后，栈中剩下的元素即为计算结果。

时间复杂度：

遍历表达式需要O(n)的时间，其中n是表达式中的元素个数。每个元素的处理时间为O(1)，因此总时间复杂度为O(n)。

空间复杂度：

使用了一个栈来存储操作数，栈的最大空间取决于表达式中的操作数个数。因此，空间复杂度为O(n)。