算术表达式中前缀表达式、中缀表达式、后缀表达式相互转换(手算法)
概念:三者的区别在于运算符相对于操作数的位置有所不同
前缀表达式(波兰式)
前缀表达式是一种没有括号的算术表达式,与中缀表达式不同的是,其将运算符写在前面,操作数写在后面。
中缀表达式
中缀表达式是一种通用的算术或逻辑公式表示方法,操作符以中缀形式处于操作数的中间。中缀表达式是人们常用的算术表示方法。
后缀表达式(逆波兰式)
后缀表达式将运算符写在操作数之后
虽然人的大脑很容易理解与分析中缀表达式,但对计算机来说中缀表达式却是很复杂的,因此计算表达式的值时,通常需要先将中缀表达式转换为前缀或后缀表达式,然后再进行求值。对计算机来说,计算前缀或后缀表达式的值非常简单。
运算符优先级
转换
1. 中缀表达式转换为其他两种
方法:
- 首先按照运算符的优先级对所有的运算单位加括号
- 转前缀则将符号移动到对应括号之前
- 转后缀则将符号移动到对应括号之后
转换过程
中缀表达式为:a + b * c - ( d + e )
- 使用按照运算符的优先级对所有的运算单位加括号
操作完成后式子变成:( ( a + ( b * c ) ) - ( d + e ) )
-
中缀表达式转前缀表达式:
1)将运算符移动到对应括号之前:- ( + ( a * ( b c ) ) + ( d e ) )
2)去掉括号:- + a * b c + d e
3)转换完成 -
中缀表达式转后缀表达式:
1)将运算符移动到对应括号之后:( ( a ( b c ) * ) + ( d e ) + ) -
2)去掉括号:a b c * + d e + -
3)转换完成
2. 前缀表达式转中缀表达式
方法:
-
从后向前
遍历前缀表达式,如果遇到运算符,将其与后面两个操作数
相结合,并在外层加上括号
,当做一个新的运算符
。 - 遍历完成后,将运算符移动到括号内的操作数中间。
- 去掉不影响运算的括号。
转换
前缀表达式为:- + a * b c + d e
- 从后向前遍历遇到运算符,与后面两个结合,外层套括号,当做新的运算符。操作完成后,表达式变为:
( - ( + a ( * b c ) ) ( + d e ) )
- 将运算符移动到括号内操作数中间,操作完成后,表达式变为:
( ( a + ( b * c ) ) - ( d + e ) )
- 去掉多余括号后,表达式变为:
a + b * c - ( d + e)
3. 后缀表达式转中缀表达式
方法:
-
从前向后
遍历后缀表达式,如果遇到运算符,将其与前面两个操作数
相结合,并在外层加上括号
,当做一个新的运算符
。 - 遍历完成后,将运算符移动到括号内的操作数中间。
- 去掉不影响运算的括号。
转换
后缀表达式为:a b c * + d e + -
- 从前向后遍历遇到运算符,与前面两个结合,外层套括号,当做新的运算符。操作完成后,表达式变为:
( ( a ( b c * ) + ) ( d e + ) - )
- 将运算符移动到括号内操作数中间,操作完成后,表达式变为:
( ( a + ( b * c ) ) - ( d + e ) )
- 去掉多余括号后,表达式变为:
a + b * c - ( d + e)