栈的应用：表达式求值

前缀表达式求值

假设前缀表达式为：+ * 2 3 4

首先从右往左扫描表达式，遇到4,3,2, 将它们入栈，此时栈顶元素为2，次顶元素为3。

扫描到 * 号，栈顶 2 和次顶 3 出栈做乘法，将结果 6 入栈。

接下来继续往左扫描表达式，遇到 2 入栈，最后遇到 + 号，将栈顶 6 和次顶 4 相加，结果 10 入栈。

因此，前缀表达式+ * 2 3 4的值为10。

后缀表达式求值

假设后缀表达式为：2 3 * 4 +

从左往右扫描表达式，遇到2和 3 , 将它们入栈，遇到 * 号， 将栈顶和次顶元素出栈，并计算得到 6， 入栈。

接下来继续往右扫描表达式，遇到 4 入栈，遇到 + 号，将栈顶和次顶元素出栈，计算得到10。

因此，后缀表达式2 3 * 4 +的值为10。

单选题

1、表达式a*(b+c)*d 的后缀表达式为（ ），其中“*”和“+”是运算符。

A.**a+bcd

B.abc+*d*

C.abc+d**

D.*a*+bcd

2、表达式 a+(b-c)*d 的前缀表达式为（ ），其中+、-、*是运算符。

• A *+a-bcd
• B +a*-bcd
• C abc-d*+
• D abc-+d