表达式,转换和计算,用C语言描述--Part2

王朝c/c++·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

表达式,转换和计算,用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

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航