前言
前缀表达式、中缀表达式、后缀表达式都是四则运算的表达方式,用以四则运算表达式求值,即数学表达式的求值。
中缀表达式
简介
中缀表达式就是常见的运算表达式，如(3+4)×5-6
前缀表达式
简介
前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前
比如:- × + 3 4 5 6
前缀表达式的计算机求值
- 1）从右至左扫描表达式，
- 2）遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 op 次顶元素），并将结果入栈；
- 3）重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果
将中缀表达式转换为前缀表达式
转换步骤如下:
1、初始化两个栈:运算符栈s1，储存中间结果的栈s2
2、从右至左扫描中缀表达式
3、遇到操作数时，将其压入s2
4、遇到运算符时，比较其与s1栈顶运算符的优先级
1）如果s1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈
2）否则，若优先级比栈顶运算符的较高或相等，也将运算符压入s1
3）否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较
5、遇到括号时
1）如果是右括号“)”，则直接压入s1
2）如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃
6、重复步骤2至5，直到表达式的最左边
7、将s1中剩余的运算符依次弹出并压入s2
8、依次弹出s2中的元素并输出，结果即为中缀表达式对应的前缀表达式
后缀表达式
简介
后缀表达式又称逆波兰表达式,与前缀表达式相似，只是运算符位于操作数之后
比如:3 4 + 5 × 6 -
后缀表达式计算机求值
与前缀表达式类似，只是顺序是从左至右：
- 1、从左至右扫描表达式
- 2、遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素op 栈顶元素 ），并将结果入栈
- 3、重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果
例如后缀表达式“3 4 + 5 × 6 -”：
将中缀表达式转换为后缀表达式
与转换为前缀表达式相似，步骤如下：
1、初始化两个栈：运算符栈s1和储存中间结果的栈s2；
2、从左至右扫描中缀表达式；
3、遇到操作数时，将其压s2；
4、遇到运算符时，比较其与s1栈顶运算符的优先级：
1）如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
2）否则，若优先级比栈顶运算符的高，也将运算符压入s1（注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况）；
3）否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较；
5、遇到括号时：
1）如果是左括号“(”，则直接压入s1；
2）如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃；
6、重复步骤2至5，直到表达式的最右边；
7、将s1中剩余的运算符依次弹出并压入s2；
8、依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）
中缀表达式转化为前缀和后缀表达式
转化步骤：
-
1、按照运算符的优先级对所有的运算单位加括号
-
2、将运算符移动到对应括号的前面（前缀表达式）或后面（后缀表达式）
-
3、去掉括号，得到前缀或后缀表达式
示例：
中缀表达式：1+(2+3)×4-5
1）加括号
式子变成 ((1+((2+3)×4))-5)
2）移动运算符
对于前缀表达式，变成了 -(+(1×(+(23)4))5)
对于后缀表达式：变成了((1((23)+4)×)+5)-
3）去掉括号
前缀表达式： - + 1 × + 2 3 4 5
后缀表达式：1 2 3 + 4 × + 5 -
参考：https://www.cnblogs.com/chensongxian/p/7059802.html
https://www.cnblogs.com/zzliu/p/10801113.html
评论区