数据结构7:表达式转换(一)
目录
一、中缀表达式
什么是中缀表达式
- 对于这样的表达式:B*C,我们真容易知道这是B乘以C,这种操作符(operator)介于操作数(operand)中间的表示方法,称为“中缀表示法”。
- 但是有时候中缀表示法会引起混淆,比如"A+B*C",是A+B然后再乘以C,还是B*C然后再加A呢?
中缀表达式中的优先级
人们引入了操作符“优先级”的概念来消除混淆,规定:1、高优先级的操作符先计算。2、相同优先级的操作符从左到右依次计算。这样的话,A+B*C就不存在上面提到的疑义了。
同时,引入了括号来表示强制优先级,括号内的优先级最高,而且在嵌套的括号内,内层的优先级更高。(A+B)*C就是A与B的和再乘以C。
全括号中缀表达式
虽然人们已经习惯了这种表示法,但是计算机处理最好是能明确规定所有的计算顺序,这样就不需要那些复杂的计算规则了,那要怎么做呢?
这里引入了全括号表达式:其实很简单,就是在所有的表达式项的两边都加上括号就行了,比如:
A+B*C+D,应该表示为((A+(B*C))+D),那么,再考虑一下,能不能把表达式中的操作符的位置移动一下呢?
二、前缀表达式和后缀表达式
- 对中缀表达式:A+B,是不是可以这样做呢?
将操作符移到前面,变为:+AB
或将操作符移到后面,变为:AB+
这样我们就得到了表达式的另外两种表示方法:前缀表示法和后缀表示法,这是根据操作符相对于操作数的位置来定义的。
这样A+B*C就可以变为+A*BC的前缀表达式,或者ABC*+的后缀表达式了。
前缀、中缀和后缀表达式
观察可以发现,在中缀表达式中必须的括号,在前缀表达式和后缀表达式中消失不见了。
这是因为在前缀和后缀表达式中,操作符的次序完全决定了运算的次序。所以在很多情况下,表达式的计算机表示都避免用复杂的中缀形式。
看更多的例子:
三、中缀表达式转化为前缀和后缀的形式
大家可能会这样想,中缀表达式怎么转化为前缀或者后缀形式的呢?能不能用算法来实现呢?
肯定是可以的。
为了分解算法的复杂度,我们从全括号中缀表达式入手。
A+B*C,写成全括号的形式是:((A+(B*C)),观察可以发现,每一对括号都包含一组完整的操作数和操作符。
看表达式(B*C)的右括号,如果把它的操作符*移到右括号的位置,并且替换它,再删去对应的做括号,得到BC*,就可以把子表达式转化为后缀的形式了,是不是很简单呢。
进一步的,把操作符“+”移到相应的右括号处并且替换,再删掉对应的做括号,那么整个表达式就转化成了后缀表达式了。
同样的,如果我们把操作符移动到对应的左括号位置并替换它,再删掉对应的右括号,就可以得到前缀表达式了。
四、总结
- 无论表达式多复杂,转化成前缀或者后缀时,只需要两个步骤:
- 将中缀表达式转化为全括号的形式。
- 将所有的操作符移动到对应的左括号(前缀)或者右括号(后缀)处,替换之,再删除所有的括号。
代码怎么实现呢?请看下一节。