表达式，转换和计算，用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
未完待续。
作者：Pradeep P. Chandiramani.
联系方式：[email protected]
译者：liudows
联系方式：[email protected]
本文地址：http://com.8s8s.com/it/it37015.htm