带你了解Java数据结构和算法之前缀,中缀和后缀表达式

带你了解Java数据结构和算法之前缀、中缀和后缀表达式

1. 前缀表达式（Prefix Expression）

前缀表达式是指运算符位于操作数之前的表达式，也被称为波兰式。前缀表达式的优点在于，每个运算符的优先级都可以通过括号来明确，不需要考虑运算符的优先级。同时，整个表达式的意义也可以很清晰地传达。

举个例子，下面是一个前缀表达式：

+ * 4 5 6  // 等价于 (4 * 5) + 6 = 26

解释一下这个表达式，首先遇到的是加号。因为加号是二元运算符，所以要取两个操作数，也就是向后读两个数字。读到 6 后，算法要回溯并读取运算符。这个运算符是乘号，同样是二元运算符，所以要取两个操作数。这两个操作数是4和5，因此表达式的意义应该是 (4 * 5) + 6。最终结果是 26。

2. 中缀表达式（Infix Expression）

中缀表达式是一般我们所见到的形式，即运算符位于操作数之间。例如，下面是一个中缀表达式：

4 * 5 + 6  // 等价于 (4 * 5) + 6 = 26

中缀表达式表达式的缺点在于，运算符的优先级不明确。因此，需要用括号来明确优先级。例如：

4 * (5 + 6)  // 等价于 4 * 11 = 44

3. 后缀表达式（Postfix Expression）

后缀表达式也叫做逆波兰式（Reverse Polish Notation），是一种将运算符置于操作数之后的表达式。

举个例子，下面是一个后缀表达式：

4 5 * 6 +  // 等价于 (4 * 5) + 6 = 26

读取后缀表达式很简单：从左到右读取每个元素，如果是数字，则加入栈中；如果是运算符，则取出栈顶的两个元素，进行运算，并将运算结果入栈。上述的后缀表达式的算法流程如下：

读取4，入栈
读取5，入栈
读取*，从栈中取出5和4，计算4*5=20，将结果入栈
读取6，入栈
读取+，从栈中取出6和20，计算6+20=26，将结果入栈

最终，栈中只剩下一个元素，它就是整个表达式的计算结果。

4. 注意事项

• 中缀表达式需要使用括号来明确优先级。而前缀和后缀表达式则不需要。
• 在进行后缀表达式的计算时，必须遵循运算符对应的先后顺序。例如，在上述的后缀表达式中，运算符 * 的优先级要高于 + 的优先级。

5. 示例说明

示例1

下面是一个中缀表达式：

3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3

这个表达式包含了加、乘、除、括号和幂次运算。为了将其转换成后缀表达式，需要定义每个运算符的优先级。

在这个表达式中，按照运算优先级排序，幂次运算最高，其次是括号，然后是乘除法，最后是加减法。根据这个优先级表，将中缀表达式转成后缀表达式，结果如下：

3 4 2 * 1 5 - 2 3 ^ ^ / +

将这个后缀表达式代入计算器中，最终结果是 3.0001220703125。

示例2

下面是一个前缀表达式：

- + * AB - CD / E F

这个表达式用运算符表示法会变成：

(((A*B)+(C-D))/E)-F

其中，运算符的优先级通过使用括号来明确。这个表达式的值为 （A×B）+（C - D）/ E - F。