怎么求后缀表达式

后缀表达式（也叫逆波兰表达式）是数学中一种常见的表示方式，其优点在于避免了使用括号来表示优先级，同时使计算过程更加简单。当我们需要对后缀表达式进行计算时，需要将其转化为计算机可以处理的形式，也就是求值。

本文将从多个角度分析怎么求后缀表达式，并介绍一些常见的转化方法和求值算法。

一、什么是后缀表达式

后缀表达式是一种中缀表达式的另一种表示方式，它将运算符放在后面，将操作数放在前面，同时去掉了括号。例如，将中缀表达式“3 + 4 * ( 2 – 1 )”转化为后缀表达式，得到“3 4 2 1 - * +”。

二、如何将中缀表达式转化为后缀表达式

1.利用栈

我们可以使用栈来完成中缀表达式转后缀表达式的过程。具体做法如下：

（1）从左至右遍历中缀表达式的各个元素；

（2）若当前元素为数值，则直接输出；

（3）若当前元素为运算符，则需将其与栈顶元素进行比较，如果当前运算符的优先级高于栈顶元素的优先级，则将当前运算符入栈，否则将栈顶元素出栈并输出，直到当前运算符的优先级高于栈顶元素的优先级为止；

（4）如果当前元素为左括号，则直接入栈；

（5）如果当前元素为右括号，则需将栈顶元素出栈并输出，直到遇到左括号为止。

例如，对于中缀表达式“5 * ( 6 + 3 ) - 7”，按照以上方法转化为后缀表达式时，得到“5 6 3 + * 7 -”。

2.利用表达式树

另一种将中缀表达式转化为后缀表达式的方法是利用表达式树。表达式树是一种二叉树，其每个非叶子结点代表一个运算符，每个叶子结点代表一个操作数。将中缀表达式转化为表达式树的过程是一个递归的过程，具体做法如下：

（1）将中缀表达式的最后一位作为根节点，从后向前遍历中缀表达式；

（2）如果当前元素为左括号，则扫描到与其匹配的右括号时停止；

（3）如果当前元素为运算符，则将其作为当前节点的值，并将中缀表达式按照运算符所在的位置分成左右两部分，递归地对左右两部分进行同样的操作，直到得到一个叶子结点。

例如，对于中缀表达式“5 * ( 6 + 3 ) - 7”，按照以上方法可以得到如下表达式树：

```

-

/ \

* 7

/ \

5 +

/ \

6 3

```

最终将表达式树按照后序遍历的方式输出就得到了后缀表达式“5 6 3 + * 7 -”。

三、如何求值

求后缀表达式的值是一个逆波兰表达式求值的过程。具体做法如下：

（1）从左至右遍历后缀表达式的各个元素；

（2）如果当前元素为数值，则直接入栈；

（3）如果当前元素为运算符，则从栈顶取出两个数进行计算，并将计算结果压入栈中；

（4）当遍历结束时，栈中仅剩一个数，也就是后缀表达式的值。

例如，对于后缀表达式“5 6 3 + * 7 -”，按照以上方法可以得到计算过程如下：

```

5 6 3 + * 7 -

= 5 9 * 7 -

= 45 7 -

= 38

```

四、小结

本文从两个方面介绍了如何求后缀表达式，一是如何将中缀表达式转化为后缀表达式，二是如何对后缀表达式进行求值。中缀表达式转后缀表达式的方法有利用栈和利用表达式树两种，其中利用栈的方法应用较为广泛。对于求后缀表达式的值，可以使用逆波兰表达式求值的方法，也同样使用栈来实现。