如何评估逆波兰表达式，LeetCode的150题怎么解？

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

问题 150. 评估逆波兰表达式

逆波兰表示法（Reverse Polish Notation，RPN）是一种后缀表示法，也称为逆波兰记法。在这种表示法中，操作数和操作符的顺序与常规的算术表达式不同。在逆波兰表示法中，所有的操作符都放在它们所作用的操作数之后。

例如，表达式 2 1 + 3 * 的逆波兰表示法是 2 1 + 3 *。这个表达式表示的是 ((2 + 1) * 3)。

逆波兰表示法易于用栈来计算，其计算步骤如下：

1. 当遇到一个数字时，将其压入栈中。

2.当遇到一个操作符时，从栈中弹出两个操作数，按照操作符的优先级进行计算，然后将结果压回栈中。

3.重复步骤 1 和 2，直到所有操作符都被处理。

4.最后，栈中的唯一元素就是表达式的结果。

下面是一个简化的逆波兰表达式计算示例：

输入：2 1 + 3 *

输出：((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