How to assess Reverse Polish Notation expressions in LeetCode?

本文共计596个文字，预计阅读时间需要3分钟。

问题 150. 评估逆波兰表达式逆波兰表示法（Reverse Polish Notation，RPN）是一种后缀表示法，它避免了使用括号来表示运算符的优先级。在逆波兰表示法中，运算符位于其操作数之后。计算逆波兰表达式时，可以使用栈来简化计算过程。

具体步骤如下：

1.从左到右扫描表达式。

2.遇到数字时，将其压入栈中。

3.遇到运算符时，从栈中弹出相应数量的操作数（通常是两个），执行运算，并将结果压回栈中。

4.当表达式扫描完毕后，栈中的最后一个元素就是表达式的结果。

例如，对于表达式 2 1 + 3 *，计算过程如下：

1.遇到数字 2，压入栈。

2.遇到数字 1，压入栈。

3.遇到运算符 +，弹出栈中的 1 和 2，计算 2 + 1=3，将结果 3 压入栈。

4.遇到数字 3，压入栈。

5.遇到运算符 *，弹出栈中的 3 和 3，计算 3 * 3=9，将结果 9 压入栈。

6.表达式扫描完毕，栈中的元素 9 即为最终结果。

所以，2 1 + 3 * 的逆波兰表示法结果是 9。

Question

150.?Evaluate Reverse Polish Notation

Solution

2 1 + 3 *是((2+1)*3)的后缀(postfix)或逆波兰(reverse Polish)记法，计算这个表达式容易想到栈，当见到一个数时就入栈，见到操作符时该运算符作用于从该栈中弹出的两个数上，将所得结果入栈。

public int evalRPN(String[] tokens) { Stack<Integer> stack = new Stack<>(); for (String tmp : tokens) { if (tmp.length() > 1) { stack.push(Integer.parseInt(tmp)); continue; } char c = tmp.charAt(0); // String转char int a, b; switch (c) { case '+': b = stack.pop(); a = stack.pop(); stack.push(a + b); break; case '-': b = stack.pop(); a = stack.pop(); stack.push(a - b); break; case '*': b = stack.pop(); a = stack.pop(); stack.push(a * b); break; case '/': b = stack.pop(); a = stack.pop(); stack.push(a / b); break; default: stack.push(c - '0'); // char 转 int } } return stack.pop(); }

Reference

• gitee.com/okokabcd/leetcode