前缀表达式、中缀表达式和后缀表达式
前缀、中缀、后缀表达式
前缀、中缀、后缀表达式是对表达式的不同记法，其区别在于运算符相对于操作数的位置不同，前缀表达式的运算符位于操作数之前，中缀和后缀同理
举例：
中缀表达式：1 + (2 + 3) × 4 - 5
前缀表达式：- + 1 × + 2 3 4 5
后缀表达式：1 2 3 + 4 × + 5 -
中缀表达式
中缀表达式是⼀种通⽤的算术或逻辑公式表⽰⽅法，操作符以中缀形式处于操作数的中间。中缀表达式是⼈们常⽤的算术表⽰⽅法。
虽然⼈的⼤脑很容易理解与分析中缀表达式，但对计算机来说中缀表达式却是很复杂的，因此计算表达式的值时，通常需
要先将中缀表达式转换为前缀或后缀表达式，然后再进⾏求值。对计算机来说，计算前缀或后缀表达式的值⾮常简单。
前缀表达式
前缀表达式的运算符位于两个相应操作数之前，前缀表达式⼜被称为前缀记法或波兰式
前缀表达式的计算机求值
1. 从右⾄左扫描表达式
2. 遇到数字时，将数字压⼊堆栈，遇到运算符时，弹出栈顶的两个数，⽤运算符对它们做相应的计算（栈顶元素 op 次
顶元素），并将结果⼊栈
3. 重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果
⽰例：
计算前缀表达式的值：- + 1 × + 2 3 4 5
1. 从右⾄左扫描，将5，4，3，2压⼊堆栈；
2）遇到+运算符，弹出2和3（2为栈顶元素，3为次顶元素），计算2+3的值，得到5，将5压⼊栈；
3）遇到×运算符，弹出5和4，计算5×4的值，得到20，将20压⼊栈；
4）遇到1，将1压⼊栈；
5）遇到+运算符，弹出1和20，计算1+20的值，得到21，将21压⼊栈；
6）遇到-运算符，弹出21和5，计算21-5的值，得到16为最终结果
可以看到，⽤计算机计算前缀表达式是⾮常容易的，不像计算后缀表达式需要使⽤正则匹配
后缀表达式
后缀表达式与前缀表达式类似，只是运算符位于两个相应操作数之后，后缀表达式也被称为后缀记法或逆波兰式
后缀表达式的计算机求值
与前缀表达式类似，只是顺序是从左⾄右：
1. 从左⾄右扫描表达式
2. 遇到数字时，将数字压⼊堆栈，遇到运算符时，弹出栈顶的两个数，⽤运算符对它们做相应的计算（次顶元素op 栈顶
元素 ），并将结果⼊栈
3. 重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果
⽰例：
计算
计算后缀表达式的值：1 2 3 + 4 × + 5 -
1）从左⾄右扫描，将1，2，3压⼊栈；
2）遇到+运算符，3和2弹出，计算2+3的值，得到5，将5压⼊栈；
3）遇到4，将4压⼊栈
4）遇到×运算符，弹出4和5，计算5×4的值，得到20，将20压⼊栈；
5）遇到+运算符，弹出20和1，计算1+20的值，得到21，将21压⼊栈；
6）遇到5，将5压⼊栈；
7）遇到-运算符，弹出5和21，计算21-5的值，得到16为最终结果
中缀表达式转化为前缀和后缀表达式
转化步骤：
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 -
⼩结
前缀、中缀、后缀是根据运算符与操作数的相对位置来划分的
中缀表达式符合⼈的计算习惯，⽽前缀和后缀表达式适合计算机计算
前缀表达式和后缀表达式计算的时候都是从⼀个⽅向扫描表达式，遇到数字压⼊栈，遇到运算符弹出栈顶的两个数进⾏运算并将结果⼊栈，重复知道结束
前缀和后缀表达式已经内在地包含运算顺序，因此不⽤括号来确定优先级

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。