前缀表达式、中缀表达式、后缀表达式总结

今天药忘吃喽~ 2022-07-16 11:39 440阅读 0赞

**一、前缀表达式**

**（1）定义**

前缀表达式是一种没有括号的算术表达式，其将运算符写在前面，操作数写在后面。例如表达式1-(2+3)的前缀表达式是- 1 + 2 3。

**（2）求值方法**

对前缀表达式求值，要**从右至左扫描**表达式，首先从右边第一个字符开始判断，若当前字符是数字则一直到数字串的末尾再记录下来，若为运算符，则将右边离得最近的两个“数字串”作相应运算，然后以此作为一个新的“数字串”并记录下来；扫描到表达式最左端时扫描结束，最后运算的值即为表达式的值。

例如：对前缀表达式“- 1 + 2 3”求值，扫描到3时，记录下这个数字串，扫描到2时，记录下这个数字串，当扫描到+时，将+右移做相邻两数字串的运算符，记为2+3，结果为5，记录下5这个新数字串，然后继续向左扫描，扫描到1时，记录下这个数字串，扫描到-时，将-右移做相邻两数字串的运算符，记为1-5，结果为-4，此时关于这个表达式的全部运算已完成，故表达式的值为-4。

**（3）中缀表达式转化为前缀表达式**

**方法**：从右往左扫描

**例子**：将中缀表达式“1+((2+3)\*4)-5”转换为前缀表达式：

<table> 
 <tbody> 
 <tr> 
 <td> 中缀表达式 </td> 
 <td> 前缀表达式 </td> 
 <td> （栈顶）运算符栈（栈尾） </td> 
 <td> 说明 </td> 
 </tr> 
 <tr> 
 <td> 5 </td> 
 <td> 5 </td> 
 <td> 空 </td> 
 <td> 5，是数字串直接输出 </td> 
 </tr> 
 <tr> 
 <td> - </td> 
 <td> 5 </td> 
 <td> - </td> 
 <td> -，栈内无运算符，直接入栈 </td> 
 </tr> 
 <tr> 
 <td> ) </td> 
 <td> 5 </td> 
 <td> -) </td> 
 <td> )，直接入栈 </td> 
 </tr> 
 <tr> 
 <td> 4 </td> 
 <td> 5 4 </td> 
 <td> -) </td> 
 <td> 4，是数字串直接输出 </td> 
 </tr> 
 <tr> 
 <td> * </td> 
 <td> 5 4 </td> 
 <td> -)* </td> 
 <td> *，栈顶是括号，直接入栈 </td> 
 </tr> 
 <tr> 
 <td> ) </td> 
 <td> 5 4 </td> 
 <td> -)*) </td> 
 <td> )，直接入栈 </td> 
 </tr> 
 <tr> 
 <td> 3 </td> 
 <td> 5 4 3 </td> 
 <td> -)*) </td> 
 <td> 3，是数字串直接输出 </td> 
 </tr> 
 <tr> 
 <td> + </td> 
 <td> 5 4 3 </td> 
 <td> -)*)+ </td> 
 <td> +，栈顶是括号，直接入栈 </td> 
 </tr> 
 <tr> 
 <td> 2 </td> 
 <td> 5 4 3 2 </td> 
 <td> -)*)+ </td> 
 <td> 2，是数字串直接输出 </td> 
 </tr> 
 <tr> 
 <td> ( </td> 
 <td> 5 4 3 2 + </td> 
 <td> -)* </td> 
 <td> (，与栈里最后一个)抵消，并释放它们之间的+ </td> 
 </tr> 
 <tr> 
 <td> ( </td> 
 <td> 5 4 3 2 + * </td> 
 <td> - </td> 
 <td> (，方法与上类同，请参考下一目录 </td> 
 </tr> 
 <tr> 
 <td> + </td> 
 <td> 5 4 3 2 + * </td> 
 <td> -+ </td> 
 <td> +，优先级大于等于栈顶运算符，直接入栈 </td> 
 </tr> 
 <tr> 
 <td> 1 </td> 
 <td> 5 4 3 2 + * 1 </td> 
 <td> -+ </td> 
 <td> 1，是数字串直接输出 </td> 
 </tr> 
 <tr> 
 <td> 空 </td> 
 <td> 5 4 3 2 + * 1 + - </td> 
 <td> 空 </td> 
 <td> 扫描结束，将栈内剩余运算符全部出栈并输出 </td> 
 </tr> 
 <tr> 
 <td> 空 </td> 
 <td> - + 1 * + 2 3 4 5 </td> 
 <td> 空 </td> 
 <td> 逆缀输出字符串 </td> 
 </tr> 
 </tbody> 
</table>

**二、中缀表达式**

**（1）定义**

是一个通用的算术或逻辑公式表示方法，操作符是以中缀形式处于操作数的中间（例：3+4），中缀表达式是人们常用的算术表示方法。

（2）中缀表达式“8+4-6\*2”用后缀表达式表示为：8 4 + 6 2 \* -

（3）中缀表达式“2\*(3+5)+7/1-4”用后缀表达式表示为：3 5 + 2 \* 7 1 /4 - +

**三、后缀表达式**

**（1）定义**

不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不在考虑运算符的优先规则），如：(2+1)\*3，即2 1 + 3 \*

**（2）中缀表达式转换为后缀表达式**

思想：

开始扫描（从左往右）；

数字时，加入后缀表达式；

运算符：

a. 若为’(‘，入栈

b. 若为’)’，则依次把栈中的运算符加入后缀表达式中，直到出现’(‘，从栈中删除’(‘；

c. 若为除括号外的其他运算符，当其优先级高于除’(‘以外的栈顶运算符时，直接入栈。否则从栈顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符，直到一个比它优先级低的或者遇到了一个左括号为止。

例子，将中缀表达式“1+((2+3)\*4)-5”转换为后缀表达式的过程如下：

<table> 
 <tbody> 
 <tr> 
 <td> 中缀表达式 </td> 
 <td> 后缀表达式 </td> 
 <td> （栈顶）运算符栈（栈尾） </td> 
 <td> 说明 </td> 
 </tr> 
 <tr> 
 <td> 1 </td> 
 <td> 1 </td> 
 <td> 空 </td> 
 <td> 数字直接入栈 </td> 
 </tr> 
 <tr> 
 <td> + </td> 
 <td> 1 </td> 
 <td> + </td> 
 <td> 栈为空，直接入栈 </td> 
 </tr> 
 <tr> 
 <td> ( </td> 
 <td> 1 </td> 
 <td> + ( </td> 
 <td> 左括号，直接入栈 </td> 
 </tr> 
 <tr> 
 <td> ( </td> 
 <td> 1 </td> 
 <td> + ( ( </td> 
 <td> 左括号，直接入栈 </td> 
 </tr> 
 <tr> 
 <td> 2 </td> 
 <td> 1 2 </td> 
 <td> + ( ( </td> 
 <td> 数字直接入栈 </td> 
 </tr> 
 <tr> 
 <td> + </td> 
 <td> 1 2 </td> 
 <td> + ( ( + </td> 
 <td> 栈顶为左括号，运算符直接入栈 </td> 
 </tr> 
 <tr> 
 <td> 3 </td> 
 <td> 1 2 3 </td> 
 <td> + ( ( + </td> 
 <td> 数字直接入栈 </td> 
 </tr> 
 <tr> 
 <td> ) </td> 
 <td> 1 2 3 + </td> 
 <td> + ( </td> 
 <td> 右括号，弹出运算符直至遇到左括号 </td> 
 </tr> 
 <tr> 
 <td> * </td> 
 <td> 1 2 3 + </td> 
 <td> + ( * </td> 
 <td> 栈顶是左括号，运算符直接入栈 </td> 
 </tr> 
 <tr> 
 <td> 4 </td> 
 <td> 1 2 3 + 4 </td> 
 <td> + ( * </td> 
 <td> 数字直接入栈 </td> 
 </tr> 
 <tr> 
 <td> ) </td> 
 <td> 1 2 3 + 4 * </td> 
 <td> + </td> 
 <td> 右括号，弹出运算符直至遇到左括号 </td> 
 </tr> 
 <tr> 
 <td> - </td> 
 <td> 1 2 3 + 4 * + </td> 
 <td> - </td> 
 <td> -与+优先级相同，因此弹出+，再压入- </td> 
 </tr> 
 <tr> 
 <td> 5 </td> 
 <td> 1 2 3 + 4 * + &nbsp;5 </td> 
 <td> - </td> 
 <td> 数字直接入栈 </td> 
 </tr> 
 <tr> 
 <td> 空 </td> 
 <td> 1 2 3 + 4 * + &nbsp;5 - </td> 
 <td> 空 </td> 
 <td> 剩余的运算符 </td> 
 </tr> 
 </tbody> 
</table>

因此结果为“1 2 3 + 4 \* + 5 -”