CSP-J/S竞赛知识点 前缀中缀后缀表达式的转换

前缀表达式的计算（前缀转中缀）：从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的 两个数，用运算符对它们做相应的计算（栈顶元素 op 次顶元素），并将结果入 栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。

这里不再举例了，可以参考后缀转中缀的方法，区别是遇到运算符计算的时候，栈顶元素 op 次顶元素

后缀表达式的计算（后缀转中缀）：从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的 两个数，用运算符对它们做相应的计算（次顶元素 op 栈顶元素），并将结果入 栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果

举例：2023年CSP-J第8题：

后缀表达式 6 2 3 + - 3 8 2 / + * 2 ^ 3 + 对应的中缀表达式是

遇到数字压入数字栈 6 2 3 + - 3 8 2 / + * 2 ^ 3 +

遇到运算符时，弹出栈顶的 两个数，用运算符对它们做相应的计算，并将结果入 栈。这里大家需要注意顺序次顶元素 op 栈顶元素6 2 3 + - 3 8 2 / + * 2 ^ 3 +

栈中表达式当成一个整体，如果题目让求值的话可以转化成值。6 2 3 + - 3 8 2 / + * 2 ^ 3 +

依次类推，过程如下：6 2 3 + - 3 8 2 / + * 2 ^ 3 +

6 2 3 + - 3 8 2 / + * 2 ^ 3 +

6 2 3 + - 3 8 2 / + * 2 ^ 3 +

6 2 3 + - 3 8 2 / + * 2 ^ 3 +

6 2 3 + - 3 8 2 / + * 2 ^ 3 +

6 2 3 + - 3 8 2 / + * 2 ^ 3 +

6 2 3 + - 3 8 2 / + * 2 ^ 3 +

6 2 3 + - 3 8 2 / + * 2 ^ 3 +

中缀转前缀：

• (1) 初始化两个栈：运算符栈S1和储存中间结果的栈S2；
• (2) 从右至左扫描中缀表达式；
• (3) 遇到操作数时，将其压入S2；
• (4) 遇到运算符时，比较其与S1栈顶运算符的优先级：
• (4-1) 如果S1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈；
• (4-2) 否则，若优先级比栈顶运算符的较高或相等，也将运算符压入S1；
• (4-3) 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；
• (5) 遇到括号时：
• (5-1) 如果是右括号“)”，则直接压入S1；
• (5-2) 如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃；
• (6) 重复步骤(2)至(5)，直到表达式的最左边；
• (7) 将S1中剩余的运算符依次弹出并压入S2；
• (8) 依次弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。
• 
  
• 举例：2022年第6题：对表达式 a+(b-c)*d 的前缀表达式为（ ），其中+、-、*是运算符。
• 
  

从右至左扫描中缀表达式，遇到操作数时，将其压入S2，遇到运算符放入S1,要求栈顶元素优先级>=次顶元素

a+(b-c)*d

右括号直接进入a+(b-c)*d

遇到左括号，出栈计算，并放入结果栈，直到右括号出栈a+(b-c)*d

如果当前操作符比栈顶操作符优先级小，则符号出栈直到栈顶元素优先级>=次顶元素

a+(b-c)*d

结束以后把运算符栈内元素全都出栈到结果栈

结果就是结果栈从顶到底的序列+a*-bcd

中缀转后缀：

与转换为前缀表达式相似，遵循以下步骤：

• 1）如果遇到操作数，我们就直接将其输出。
• 2）如果遇到操作符，则我们将其放入到栈中，遇到左括号时我们也将其放入栈中。
• 3）如果遇到一个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为止。注意，左括号只弹出并不输出。
• 4）如果遇到任何其他的操作符，如（“+”， “*”，“（”）等，从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止。弹出完这些元素后，才将遇到的操作符压入到栈中。有一点需要注意，只有在遇到" ) "的情况下我们才弹出" ( "，其他情况我们都不会弹出" ( "。
• 5）如果我们读到了输入的末尾，则将栈中所有元素依次弹出。

中缀转后缀：跟中缀转前缀不同的地方在于：

1. 从前往后扫描表达式
2. 栈顶元素要大于次顶元素优先级（不是大于等于）
3. 读取最后结果从栈底到栈顶

例题：2021年第9题：表达式 a*(b+c)*d 的后缀表达式为( )，其中 * 和 + 是运算符。

大家可以自行试试，答案abc+*d*