在本文中，我将详细的讲解一个重要的程序设计概念，即代数表达式，它的不同的表示方式如前缀，后缀，中缀表示，如何将一种表示方式转换成另一种表示方式，以及如何用计算机计算代数表达式的值。
每一个原理都会附有算法，C语言编写的示例性程序，以帮助新手们更清楚地理解这些概念。
我们将使用栈和二叉树来转换表达式并计算表达式的值，所以要求读者在阅读本文之前要清楚这些基本概念。
本文覆盖的主题有：
什么是代数表达式？ 什么是表达式的中缀，前缀，后缀表示法？ 为什么对同一表达式我们需要有不同的表示方法？ 为什么我们要把表达式从一种形式转换成另一种形式？ 我们如何把表达式从一种表示形式转换成另一种表示形式？（算法，程序，例子） 表达式树 怎样计算一个表达式的值？（算法，程序）代数表达式简介：
代数表达式是由操作数和运算符连接起来的合法的串。操作数是一个数量（数据的单位），数学运算在操作数的基础上运行。操作数可以是一个变量，比如x,y,z，也可以是一个常量，比如5,4,0,9,1等等。运算符是一个表示操作数间数学或逻辑操作的符号。大家熟悉的运算符有＋，－，，*，/，^（本教程中^用来表示指数运算符）等等。根据操作数和运算符的定义，现在我们可以写出一个表达式的示例，如x+y*z。注意代数表达式定义中的用语“合法的串”，在前面提到的例子x+y*z中，操作数x,y,x和运算符+,*就形成了某种形式的合法的串。再举另一个例子+xyz*，此表达式中操作数和运算符就没有组成合法的串；这个表达式不是一个有效的表达式。
一个代数表达式有三种表示方法：
中缀表示：从我们的学校时代开始，我们就已经熟悉了这种用操作数包围着运算符的表示法，比如x+y,6*3等等。这种书写表达式的方法被称为中缀表示法。
前缀表示：前缀表示法也被称为波兰表示法，它是一种由波兰数学家Jan Lukasiewicz发明的逻辑记法。顾名思义，前缀表示法中，运算符要放到操作数前面，比如+xy，*+xyz等。
后缀表示：后缀表示法也被称为逆波兰表示法。它与中缀和前缀表达式不同之处在于，后缀表示法中，运算符放在操作数之后，如xy+，xyz+*等。
现在，我们自然而然地会想到一个问题，我们已经由了可爱而简单的中缀表示法，为什么还要这些古怪的前缀和后缀表示法？
事实上，令我们感到惊讶的是中缀表示并不像它看起来那么简单，特别是当计算中缀表达式的值的时候。为了计算中缀表达式的值我们需要考虑运算符的优先级和结合性的问题。
举例说明，表达式3＋5*4被看作(3+5)*4时计算结果得32，被看作3+(5*4)是计算得23。为了解决这个问题，需要定义运算符之间的优先级。运算符优先级规定了计算的次序。优先级高的运算符先计算，优先级低的运算符后计算。
下表以递减的顺序列出了各个运算符的优先级。
现在，我们已经知道了各运算符的优先级，我们就可以确定地计算出表达式3＋5*4的值为23。但是请等等，问题还没完全解决，对表达式6/3*2又该怎么办呢？当把这个表达式看作（6/3）*2时得2，看作6/(3*2)时得1，因为*和/的优先级相同。为了解决这个冲突，我们要用到运算符的结合性这个概念。运算符的结合性规定了同优先级的运算符间的运算次序。对有左结合性的运算符而言，计算次序是从左到右，而对右结合性的运算符，是从右到左计算。
*，/， +， －都具有左结合性。所以上面的表达式最后计算得4，而不是1。
注意：我们使用结合性的概念只是为了解决同优先级操作符间的冲突问题。
由于使用中缀表示法时还要考虑运算符的优先级和结合性的问题，我们换用前缀和后缀表示。前缀和后缀表示相比中缀表示的优点在于计算表达式值的时候不需要考虑运算符的优先级和结合性。比如，x/y*z用前缀表示就变成了*/xyz，用后缀表示就变成xy/z*。前缀和后缀表示都能使表达式值的计算变得容易得多。（关于这点，我们将在后面详细讨论）
但是这两种表示方式都不便于记忆，也不便于手工书写。比如，(x+y)/z*a （中缀表示）和xy+z/a*（后缀表示），哪一个更容易记住呢？
所以，实际上我们要做的就是由用户扫描中缀表达式；将其转换成前缀或后缀形式，然后计算其值，而不用考虑括号和运算符的优先级。
未完待续。
作者：Pradeep P. Chandiramani.
联系方式：[email protected]
译者：liudows
联系方式：[email protected]
本文地址：http://com.8s8s.com/it/it37014.htm