天天看点

前缀表达式,后缀表达式

我们算简单的算术运算十分easy,但是复杂的呢?这就要考计算机的帮忙了,但是计算机怎么识别运算的优先级呢,这就需要前缀表达式或者后缀表达式了

先说后缀表达式

规则是从左到右遍历中缀表达式的每个数字和符号,若是数字就输出,即成为后缀表达式的一部分;若是符号,则判断其与栈顶符号的优先级,是优先级低于找顶符号(乘除优先加减)则栈顶元素依次出找并输出,并将当前符号进栈,一直到最终输出后缀表达式为止,还有就是括号,如果是左括号,直接进栈,之后的符号只要不是右括号就都进栈,不用比较优先级了,当碰见右括号时,左括号之上的元素全部按顺序弹出,左括号删除

来一个例子:

(25+3)*(2*(1+4)+6)

这个从头来,首先有个符号栈

第一个是“(”进栈

然后是数字25,直接输出

“+”号因为之前又左括号所以不必判断优先级,直接进栈

数字3直接输出

到了右括号了

把左括号上的全部输出,是“+”,删除左括号

然后乘号因为栈里什么都没有,直接进栈

左括号进栈

数字2输出

乘号进栈

左括号进栈

数字1输出

加号进栈

数字4输出

碰见右括号,最近的左括号之上的符号全部输出,删除一个最近左括号

加号碰见栈里的乘号,因为优先级低于乘号,所以弹出栈顶的乘号,就好进栈

数字6输出

碰见右括号,直接弹出左括号上面的符号

如果没有已经结束了,就全部弹出

所以结果为: 25 3 + 2 1 4 + * 6 + *

这就是后缀表达式也称逆波兰式

前缀表达式也称波兰式

这个与后缀差不多,

(1) 首先构造一个运算符栈(也可放置括号),运算符(以括号分界点)在栈内遵循越往栈顶优先级不降低的原则进行排列

(2)从右至左扫描中缀表达式,从右边第一个字符开始判断:如果当前字符是数字,则分析到数字串的结尾并将数字串直接输出

如果是运算符,则比较优先级。如果当前运算符的优先级大于等于栈顶运算符的优先级(当栈顶是括号时,直接入栈),则将运算符直接入栈;否则将栈顶运算符出栈并输出,直到当前运算符的优先级大于等于栈顶运算符的优先级(当栈顶是括号时,直接入栈),再将当前运算符入栈。如果是括号,则根据括号的方向进行处理。如果是右括号,则直接入栈;否则,遇左括号前将所有的运算符全部出栈并输出,遇右括号后将左右的两括号一起删除

(3) 重复上述操作(2)直至扫描结束,将栈内剩余运算符全部出栈并输出,再逆缀输出字符串。中缀表达式也就转换为前缀表达式了。

再来一个百科中的例子吧

前缀表达式,后缀表达式
前缀表达式,后缀表达式