表达式,转换和计算,用C语言描述--Part2
(关于表达式的所有你应该知道的东西)
现在我们进入程序设计的话题。如何将表达式从一种形式转换成另一种形式?有两种方法完成这种转换。第一种是用栈完成,另一种是使用表达式树。
因为有三种表示方式,所以一共可以做6种转换,也就是说有 中缀 -> 前缀, 中缀 -> 后缀, 前缀 -> 中缀, 前缀 -> 后缀, 后缀 -> 前缀, 后缀 -> 中缀这些转换。对头两个转换我们准备用栈完成,剩下的4种用二分表达式树完成。
为了将表达式从中缀表示转换成前缀和后缀表示,我们将要用到栈。对那些不了解栈为何物的读者,下面我们对栈作一简要介绍。栈是一种特殊的数据结构,栈中元素被移出栈的顺序与它们进入栈的顺序相反。栈遵循后进先出(LIFO)的模式。向栈中添加元素称作压栈(PUSH),从栈中移出元素被称为出栈(POP)。
使用栈将表达式从中缀形式转换成后缀形式
为了将表达式从中缀形式转换成后缀形式,我们将使用栈。
算法
1)检查输入的下一元素。
2)假如是个操作数,输出。
3)假如是个开括号,将其压栈。
4)假如是个运算符,则
i) 假如栈为空,将此运算符压栈。
ii) 假如栈顶是开括号,将此运算符压栈。
iii) 假如此运算符比栈顶运算符优先级高,将此运算符压入栈中。
iv) 否则栈顶运算符出栈并输出,重复步骤4。
5)假如是个闭括号,栈中运算符逐个出栈并输出,直到遇到开括号。开括号出栈并丢弃。
6)假如输入还未完毕,跳转到步骤1。
7)假如输入完毕,栈中剩余的所有操作符出栈并输出它们。
举例
假设我们想要把表达式2*3/(2-1)+5*(4-1)转换成后缀形式:原表达式的逆序是)1-4(*5+)1-2(/3*2。
当前扫描字符
栈中字符(栈顶在右)
后缀表达式
2
Empty
2
*
*
2
3
*
23
/
/
23*
(
/(
23*
2
/(
23*2
-
/(-
23*2
1
/(-
23*21
)
/
23*21-
+
+
23*21-/
5
+
23*21-/5
*
+*
23*21-/5
(
+*(
23*21-/5
4
+*(
23*21-/54
-
+*(-
23*21-/54
1
+*(-
23*21-/541
)
+*
23*21-/541-
Empty
23*21-/541-*+
所以,得到的后缀表达式是23*21-/541-*+。
使用栈将表达式从中缀形式转换成前缀形式
上面的算法有一定的技巧性,我们首先写出输入表达式的逆序,所以a+b*c就变成了c*b+a,然后才进行转换。这样做有一个好处是只需要对算法进行一些小的修改,它就能应用于中缀到前缀形式的转换。
算法
1)求输入串的逆序。
2)检查输入的下一元素。
3)假如是操作数,把它添加到输出串中。
4)假如是闭括号,将它压栈。
5)假如是运算符,则
i)假如栈空,此运算符入栈。
ii)假如栈顶是闭括号,此运算符入栈。
iii)假如它的优先级高于或等于栈顶运算符,此运算符入栈。
iv)否则,栈顶运算符出栈并添加到输出串中,重复步骤5。
6)假如是开括号,栈中运算符逐个出栈并输出,直到遇到闭括号。闭括号出栈并丢弃。
7)假如输入还未完毕,跳转到步骤2。
8)假如输入完毕,栈中剩余的所有操作符出栈并加到输出串中。
9)求输出串的逆序。
举例
假设我们要将表达式2*3/(2-1)+5*(4-1)转换成前缀形式:原表达式的逆序是)1-4(*5+)1-2(/3*2
当前扫描字符
栈中字符(栈顶在右)
前缀表达式(从右到左)
)
)
1
)
1
-
)-
1
4
)-
14
(
Empty
14-
*
*
14-
5
*
14-5
+
+
14-5*
)
+)
14-5*
1
+)
14-5*1
-
+)-
14-5*1
2
+)-
14-5*12
(
+
14-5*12-
/
+/
14-5*12-
3
+/
14-5*12-3
*
+/*
14-5*12-3
2
+/*
14-5*12-32
Empty
14-5*12-32*/+
输出串的逆序为+/*23-21*5-41,所以,最终求得的前缀表达式是+/*23-21*5-41。
以上算法参考程序#1。
文中源代码:http://www.csdn.net/Develop/read_article.asp?id=27543[/url]
未完待续。
作者:Pradeep P. Chandiramani.
联系方式:[url=mailto:pradeepchandiramani@yahoo.co.in]pradeepchandiramani@yahoo.co.in
译者:liudows
联系方式:mysea000@163.com