中缀表达式转后缀表达式规则

betball贝博app 数据结构 445 次浏览 没有评论

中缀表达式a + b*c + (d * e + f) * g,其转换成后缀表达式则为a b c * + d e * f  + g * +。

转换过程需要用到栈,具体过程如下:

1)如果遇到操作数,我们就直接将其输出。

2)如果遇到操作符,则我们将其放入到栈中,遇到左括号时我们也将其放入栈中。

3)如果遇到一个右括号,则将栈元素弹出,将弹出的操作符输出直到遇到左括号为止。注意,左括号只弹出并不输出。

4)如果遇到任何其他的操作符,如(“+”, “*”,“(”)等,若优先级小于栈顶运算符,从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止。优先级大于栈顶优先级,才将遇到的操作符压入到栈中。有一点需要注意,只有在遇到" ) "的情况下我们才弹出" ( ",其他情况我们都不会弹出" ( "。

5)如果我们读到了输入的末尾,则将栈中所有元素依次弹出。

 

请试试应用堆栈将中缀表达式2*(6/3+4)-5转换为后缀表达式。在这个转换过程中,堆栈元素最多时元素个数是多少?(3)

右侧为栈顶

2       *(

26     *(

263    *(/

263/4    *(+

263/4+   *

263/4+5-*

发表评论

邮箱地址不会被公开。

Go