题目

根据 逆波兰表示法，求表达式的值。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

注意 两个整数之间的除法只保留整数部分。

可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

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

示例 2：

  1. 输入：tokens = ["4","13","5","/","+"]
  2. 输出：6
  3. 解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

  1. 输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
  2. 输出：22
  3. 解释：该算式转化为常见的中缀算术表达式为：
  4.   ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
  5. = ((10 * (6 / (12 * -11))) + 17) + 5
  6. = ((10 * (6 / -132)) + 17) + 5
  7. = ((10 * 0) + 17) + 5
  8. = (0 + 17) + 5
  9. = 17 + 5
  10. = 22

提示：

  • 1 <= tokens.length <= 10^4

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

    解题方法

    栈

    使用栈存储运算数字或结果，遇到运算符号时，先后弹出两个数字，进行运算后在压入栈中，最后返回栈顶元素即可。
    时间复杂度O(n)，空间复杂度O(n)。
    C++代码：

    1. class Solution {
    2. public:
    3.   int evalRPN(vector<string>& tokens) {
    4.       stack<int> num;
    5.       for(int i = 0; i<tokens.size(); i++) {
    6.           if(tokens[i]=="+" || tokens[i]=="-" || tokens[i]=="*" || tokens[i]=="/") {
    7.               int b = num.top();
    8.               num.pop();
    9.               int a = num.top();
    10.               num.pop();
    11.               if(tokens[i]=="+")  num.push(a+b);
    12.               if(tokens[i]=="-")  num.push(a-b);
    13.               if(tokens[i]=="*")  num.push(a*b);
    14.               if(tokens[i]=="/")  num.push(a/b);
    15.           }
    16.           else {
    17.               num.push(stoi(tokens[i]));
    18.           }
    19.       }
    21.       return num.top();
    22.   }
    23. };

    数组模拟栈

    对于有效表达式，数字最多为(n+1)/2个，因此创建空间为(n+1)/2的数组存储运算数字。
    C++代码：

    1. class Solution {
    2. public:
    3.   int evalRPN(vector<string>& tokens) {
    4.       int n = tokens.size();
    5.       vector<int> out((n+1)/2);
    6.       int idx = -1;
    7.       for(int i = 0; i<n; i++) {
    8.           if(tokens[i]=="+" || tokens[i]=="-" || tokens[i]=="*" || tokens[i]=="/") {
    9.               idx--;
    10.               if(tokens[i]=="+")  out[idx] += out[idx+1];
    11.               if(tokens[i]=="-")  out[idx] -= out[idx+1];
    12.               if(tokens[i]=="*")  out[idx] *= out[idx+1];
    13.               if(tokens[i]=="/")  out[idx] /= out[idx+1];
    14.           }
    15.           else {
    16.               out[++idx] = stoi(tokens[i]);
    17.           }
    18.       }
    20.       return out[idx];
    21.   }
    22. };