题目链接

题目描述

根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：

  • 整数除法只保留整数部分。
  • 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

    示例

    示例1：

    输入：tokens = [“2”,”1”,”+”,”3”,”“] 输出：9 解释：该算式转化为常见的中缀算术表达式为：((2 + 1) 3) = 9

提示

  • 1 <= tokens.length <= 10

  • tokens[i] 要么是一个算符（"+"、"-"、"*" 或 "/"），要么是一个在范围 [-200, 200] 内的整数

    思路

    栈

    维护一个栈储存操作数，从头遍历表达式：

  • 如果是操作数，则直接入栈

  • 如果是运算符，则将两个操作数出栈，将运算结果入栈

最后栈内只会剩下一个元素，即最终结果。

题解

  1. class Solution {
  2.    public:
  3.     int evalRPN(vector<string>& tokens) {
  4.         stack<int> stk;
  5.         for (string str : tokens) {
  6.             if (str == "+" || str == "-" || str == "*" || str == "/") {
  7.                 int num2 = stk.top();
  8.                 stk.pop();
  9.                 int num1 = stk.top();
  10.                 stk.pop();
  11.                 switch (str[0]) {
  12.                     case '+':
  13.                         stk.push(num1 + num2);
  14.                         break;
  15.                     case '-':
  16.                         stk.push(num1 - num2);
  17.                         break;
  18.                     case '*':
  19.                         stk.push(num1 * num2);
  20.                         break;
  21.                     case '/':
  22.                         stk.push(num1 / num2);
  23.                         break;
  24.                 }
  25.             } else {
  26.                 stk.push(stoi(str));
  27.             }
  28.         }
  30.         return stk.top();
  31.     }
  32. };

复杂度分析

  • 时间复杂度：0150-逆波兰表达式求值 - 图1
  • 空间复杂度：0150-逆波兰表达式求值 - 图2