中缀表达式转换为后缀表达式并求值(栈的使用)

 

中缀表达式如2*3+(4-3), 其运算符一般出现在操作数之间, 因此称为中缀表达式,也就是大家编程中写的表达

式。编译系统不考虑表达式的优先级别, 只是对表达式从左到右进行扫描, 当遇到运算符时, 就把其前面的两

个操作数取出, 进行操作。为达到上述目的, 就要将中缀表达式进行改写,变为后缀表达式 如上面的表达式

2*3+(4-3), 就变为2 3 * 4 3 – + ;

后缀表达式中不含有括号, 且后缀表达式的操作数和中缀表达式的操作数排列次序完全相同, 只是运算符的

次序发生了改变。我们实现的时候,只需要用一个特定工作方式的数据结构(栈),就可以实现。

其中stack op;用来存放运算符栈。数组ans用来存放后缀表达式。

算法思想:

从左到右扫描中缀表达式,是操作数就放进数组ans的末尾。

如果是运算符的话,分为下面3种情况:

1)如果是‘(’直接压入op栈。

2)如果是‘)’,依次从op栈弹出运算符加到数组ans的末尾,知道遇到’(’;

3) 如果是非括号,比较扫描到的运算符,和op栈顶的运算符。如果扫描到的运算符优先级高于栈顶运算符

则,把运算符压入栈。否则的话,就依次把栈中运算符弹出加到数组ans的末尾,直到遇到优先级低于扫描

到的运算符或栈空,并且把扫描到的运算符压入栈中。

就这样依次扫描,知道结束为止。

如果扫描结束,栈中还有元素,则依次弹出加到数组ans的末尾,就得到了后缀表达式。

下面是程序代码和问题描述:

问题描述:
请编写程序将一个中缀表达式转换为后缀表达式。
输入
仅一行,是一个中缀表达式。输入的符号中只有这些基本符号“0123456789+-*/()”,并且不会出现形如2*-3的格式,所有数字都是个位数,“/”表示整除运算。
输出
仅一行,是转换后的后缀表达式。数字之间、运算符之间、数字和运算符之间都用一个空格隔开(参见样例)。
样例
.in
8-(3+2*6)/5+4
.out
8 3 2 6 * + 5 / – 4 +

 

以下附全部代码

 

作者:u010927811 发表于2013-10-8 23:56:18 原文链接
阅读:115 评论:0 查看评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">