CSP初赛知识点讲解（六）

运算表达式

运算表达式有三种，前缀表达式，中缀表达式，后缀表达式，我们常用的是中缀表达式，即符号在数字之间， 运算符有优先级，人肉眼看着很方便，计算也比较方便。 但是脑补一下就会发现计算机计算这种表达式很麻烦， 不信你自己写个代码试试，计算机比较好识别的是后缀 表达式，即运算符号在数字后面，遇到符号就把最近的 两个数字计算，这样运算符之间没有优先级。

那么这里就涉及到两个知识

（1）中缀表达式转后缀表达式(反过来)

（2）后缀表达式计算

中缀变后缀

转换规则：

（1）遇到数字的时候直接存入一个新的数组

（2）遇到“(”的时候，无论此时栈顶元素为什么，都入栈

（3）遇到“)”的时候，无论此时栈顶元素为什么，都出栈。依 次把栈顶的元素存入新的数组，直到“(”出栈为止。“(”不放 入数组。

（4）遇到“*”和“/”的时候，如果栈为空或者栈顶元素是左括 号。入栈。如果优先级大于栈顶元素，入栈(乘除的优先级>加减), 如果优先级小于等于栈顶元素，出栈，直到栈顶元素优先级小于 当前字符优先级的时候。当前字符入栈。

（5）遇到“+”和“-”的时候。如果栈为空或者栈顶元素为左括 号，入栈，否则出栈（因为加减的优先级最低，无论栈顶是什么 运算符，优先级都大于等于他，都要出栈），当前字符入栈。

（6）字符串遍历完之后，一次出栈，并存储。

eg:9+(3-1)*3+10/2转为后缀表达式

• 当前元素：9，直接添加到后缀表达式列表中。

• 当前元素：+，压入栈中。

• 当前元素：(，压入栈中。

• 当前元素：3，直接添加到后缀表达式列表中。

• 当前元素：-，压入栈中。

• 当前元素：1，直接添加到后缀表达式列表中。

• 当前元素：)，将栈顶元素弹出并添加到后缀表达式列表中，直到遇到左括号"("。

• 当前元素：*，压入栈中。

• 当前元素：3，直接添加到后缀表达式列表中。

• 当前元素：+，栈顶元素的优先级低于当前运算符，将当前运算符压入栈中。

• 当前元素：10，直接添加到后缀表达式列表中。

• 当前元素：/，栈顶元素的优先级低于当前运算符，将当前运算符压入栈中。

• 当前元素：2，直接添加到后缀表达式列表中。

• 遍历完毕，将栈中剩余的运算符依次弹出并添加到后缀表达式列表中。

所以最终后缀表达式：9 3 1 - 3 * + 10 2 / +

表达式求值

在中缀转后缀的基础上，我们对这个表达式进行求值

eg:9+(3-1)*3+10/2转为后缀表达式

• 当前元素：9，压入栈中。

• 当前元素：3，压入栈中。

• 当前元素：1，压入栈中。

• 当前元素：-，从栈中弹出3和1，计算3-1=2，将结果2压入栈中。

• 当前元素：3，压入栈中。

• 当前元素：，从栈中弹出2和3，计算23=6，将结果6压入栈中。

• 当前元素：+，从栈中弹出9和6，计算9+6=15，将结果15压入栈中。

• 当前元素：10，压入栈中。

• 当前元素：2，压入栈中。

• 当前元素：/，从栈中弹出10和2，计算10/2=5，将结果5压入栈中。

• 当前元素：+，从栈中弹出15和5，计算15+5=20

  所以最终结果为20。

前缀表达式

后缀表达式是运算符在数字后面，那么前缀表达式就很明显是运算符在数字前面，实际上规则和中缀 转后缀差不多。 对于中缀表达式，先倒着读，按照类似中缀转后 缀的方式转换完之和再倒序。

eg:1+2*3+(4*5+6)*7 转换成前缀表达式，第一步先倒着读。

(1)读入‘7’，并送到输出，然后‘*’被读入并压入栈中。 接下来‘）’读入并送到栈中，此时状态如下：

栈：*） 输出：7

(2)接下来读入‘6’，并送到输出，然后读入‘+’此时状态 如下：

栈：* ) + 输出：7 6

(3)然后读入‘5’，并送到输出，然后继续读入‘*’，由于 ‘*’的优先级比‘+’高，所以直接加入栈中，再将‘4’送 到输出，因此状态如下：

栈：* ) + * 输出：7 6 5 4

(4)下一个读入的符号‘（’，由于规则，因此将符号栈中的 操作符依次出栈，然后读入‘4’，并在最后将右括号弹出：

栈：* 输出： 7 6 5 4 * +

(5)继续读入，此时读入‘+’，由优先级小于栈中‘*’的优 先级，因此依照规则，依次出栈，最后将‘+’入栈，接下来 读入‘3’：

栈：+ 输出：7 6 5 4 * + * 3

(6)往后读入的符号是‘*’，将‘*’入栈。然后将‘2’放 入输出：

栈：+ * 输出：7 6 5 4 * + * 3 2

(7)现在读入‘+’，由于符号栈中存在‘+’且它们的优先级 相同，根据规则，除非，优先级大于栈顶元素，否则不出栈， 依次栈中状态如下：

栈：+ + 输出：7 6 5 4 * + * 3 2 *

(8)下一个读入‘1’：

栈：+ + 输出：7 6 5 4 * + * 3 2 * 1

(9)现在输入为空，弹出所有栈中元素

栈：空 输出：7 6 5 4 * + * 3 2 * 1 + +

(10)最后翻转 输出：+ + 1 * 2 3 * + * 4 5 6 7

前缀表达式转换成中缀表达式也差不多。 第一步，先倒序，剩下的和后缀转中缀差不多

比如: + + 1 * 2 3 * + * 4 5 6 7

翻转：7 6 5 4 * + * 3 2 * 1 + +

遇到数字就放入栈内，遇到运算符就栈顶两个元素计算。

例题训练（八）

• 表达式a*(b+c)*d的后缀形式是( )

  A：a b c d * + *

  B：a b c + * d *

  C：a * b c + * d

  D：b + c * a * d

​ 答案：B

​ 题解：可以直接模拟得到

• 表达式a*d-b*c的前缀形式是（ ）

  A：a d * b c * -

  B：- * a d * b c

  C：a * d – b * c

  D：- * * a d b c

​ 答案：B

​ 题解：可以直接模拟得到