现在的位置: 首页 > 综合 > 正文

中缀表达式转后缀表达式

2013年02月06日 ⁄ 综合 ⁄ 共 579字 ⁄ 字号 评论关闭

中缀表达式和后缀表达式

中缀表达式是我们人能够正常阅读的表达式。比如说a+(b*c-d)/e。

后缀表达式中没有括号,比如上面式子的后缀表达式就是abc*d-e/+。

看两个式子可以知道,表达式中,变量的出现次序是相同的。但是操作符的次序是不同的。在后缀表达式中,操作符的次序是真正进行操作的次序。

将中缀表达式转换为后缀表达式的过程如下:

要使用一个栈存放操作符,具体可以按照下面的方式进行:
(1)从左到右依次扫描中缀表达式的每一个字符,如果是数字字符和圆点“.”则直接将它们写入后缀表达式中。
(2)如果遇到的是开括号“(”,则将它们压入一个操作符栈(不需要与栈顶操作符相比较),它表明一个新的计算层次的开始,在遇到和它匹配的闭括号“)”时,将栈中的元素弹出来并放入后缀表达式中,直到栈顶元素为“(”时,将栈顶元素“(”弹出(不需要加入后缀表达式),表明这一层括号内的操作处理完毕。
(3)如果遇到的是操作符,则将该操作符和操作符栈顶元素比较:

1、当所遇到的操作符的优先级小于或等于栈顶元素的优先级时,则取 出栈顶元素放入后缀表达式,并弹出该栈顶元素,反复执行直到当前操作符的优先级大于栈顶元素的优先级小于;
2、当所遇到的操作符的优先级大于栈顶元素的优先级的时则将它压入栈中。
(4)重复上述步骤直到遇到中缀表达式结束。弹出栈中的所有元素并放入后缀表达式中,转换结束。


 

 

抱歉!评论已关闭.