Evaluate Reverse Polish Notation

150. 逆波兰表达式求值

分析

遍历 tokens 数组，对于每个元素：
- 如果是数字，将其转换为整数并压入栈中
- 如果是运算符，弹出栈顶的两个数字进行运算，并将结果压回栈中
最后，栈中会留下一个元素，这个元素即为整个表达式的结果

时间复杂度

时间复杂度 O(n)

空间复杂度

空间复杂度为 O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


class Solution
{
public:
    int evalRPN(vector<string>& tokens)
    {
      std::stack<int> stk;  // 用来存储操作数
      for (std::string& token : tokens)
      {
        // 如果是运算符，弹出两个元素进行运算
        if (token == "+" || token == "-" || token == "/" || token == "*")
        {
          int b = stk.top();  // 弹出栈顶元素作为右操作数
          stk.pop();
          int a = stk.top();  // 弹出新的栈顶元素作为左操作数
          stk.pop();

          // 进行相应的运算，并将结果压回栈中
          if (token == "+")
            stk.push(a + b);
          else if (token == "-")
            stk.push(a - b);
          else if (token == "/")
            stk.push(a / b);
          else
            stk.push(a * b);
        }
        else  // 如果是数字，直接将其转换为整数压入栈中
        {
          stk.push(stoi(token));
        }
      }
      return stk.top();  // 返回栈中的唯一元素，即计算结果
    }
};