(盐城工学院数据结构课程设计)栈的应用表达式求值(2)

栈的应用：表达式求值的设计

3.2中缀表达式求值

中缀表达式：每个二目运算符在两个运算量的中间，假设操作数是整型常数，运算符只含加、减、乘、除等四种运算符，界限符有左右括号和表达式起始、结束符“＃”，如：＃(7+15)*(23-28/4)＃。要对一个简单的算术表达式求值，首先要了解算术四则运算的规则，即： (1) 从左到右；

(2) 先乘除，后加减； (3) 先括号内，后括号外。

运算符和界限符可统称为算符，它们构成的集合命名为OPS。根据上述三条运算规则，在运算过程中，任意两个前后相继出现的算符θ1和θ2之间的优先关系必为下面三种关系之一： θ1<θ2，θ1的优先权低于θ2。 θ1=θ2，θ1的优先权等于θ2。 θ1>θ2，θ1的优先权高于θ2。

实现算符优先算法时需要使用两个工作栈：一个称作operator，用以存放运算符；另一个称作operand，用以存放操作数或运算的中间结果。算法的基本过程如下：

首先初始化操作数栈operand和运算符栈operator，并将表达式起始符“＃”压入运算符栈；

依次读入表达式中的每个字符，若是操作数则直接进入操作数栈operand，若是运算符，则与运算符栈operator的栈顶运算符进行优先权比较，并做如下处理：

(1) 若栈顶运算符的优先级低于刚读入的运算符，则让刚读入的运算符进operator栈；

(2) 若栈顶运算符的优先级高于刚读入的运算符，则将栈顶运算符退栈，送入θ，同时将操作数栈operand退栈两次，得到两个操作数a、b，对a、b进行θ运算后，将运算结果作为中间结果推入operand栈；

(3) 若栈顶运算符的优先级与刚读入的运算符的优先级相同，说明左右括号相遇，只需将栈顶运算符（左括号）退栈即可。operator栈的栈顶元素和当前读入的字符均为“#”时，说明表达式起始符“#”与表达式结束符“#”相遇，整个表达式求解结束。 int ExpEvaluation()?

{ /*读入一个简单算术表达式并计算其值。*/

InitStack(&operand); InitStack(&operator); PushStack(&operator, ’＃’); printf(″\\n\\n Please input an expression (Ending with ＃) :″);?

4

栈的应用：表达式求值的设计

ch=getchar();? /*读入表达式中的一个字符*/ while(ch!=‘＃’||GetTop(operator)!=‘＃’)

{ if(!In(ch, OPS))? /*判断ch是否运算符*/

{ a=GetNumber(&ch); /* 用ch逐个读入操作数的各位数码，并转化为十进制数a */

PushStack(&operand,a);} else?

switch(Compare(GetTop(operator),ch))? { case ′<′: PushStack(&operator, ch); ch=getchar(); break;?

case ′=′: PopStack(&operator,&x); ? ch=getchar(); break;? case ′>′: PopStack(&operator, &op); PopStack(&operand, &b);

? PopStack(&operand, &a);? v=Execute(a,op,b);

? PushStack(&operand,v);? break;

}? }?

v=GetTop(operand); return(v); }

为了处理方便，编译程序常把中缀表达式首先转换成等价的后缀表达式，后缀表达式的运算符在运算对象之后。在后缀表达式中，不再引入括号，所有的计算按运算符出现的顺序，严格从左向右进行，而不用再考虑运算规则和级别。中缀表达式“（a+b*c）-d/e”的后缀表达式为：“abc*+de/-”。

3.3后缀表达式求值

计算一个后缀表达式，算法上比计算一个中缀表达式简单的多。这是因为表达式中即无括号又无优先级的约束。具体做法：只使用一个对象栈，当从左向右扫描表达式时，每遇到一个操作数就送入栈中保存，每遇到一个运算符就从栈中取出两个操作数进行当前的计算，然后把结果再入栈，直到整个表达式结束，这时送入栈顶的值就是结果。

下面是后缀表达式求值的算法，在下面的算法中假设，每个表达式是合乎语法的，并且假设后缀表达式已被存入一个足够大的字符数组A中，且以‘#’为结束字符，为了简化问题，限定运算数的位数仅为一

5

栈的应用：表达式求值的设计

位且忽略了数字字符串与相对应的数据之间的转换问题。

double calcul_exp(char *A) /*本函数返回由后缀表达式A表示的表达式运算结果*/

{ SeqStarck s;

ch=*A++ ; InitStack(s); while(ch!= ’#’ )

{ if(ch!=运算符) PushStack(s, ch); else

{ PopStack(s, &a);

PopStack(s, &b); /*取出两个运算量*/ switch(ch)

{ case ch==’+’： c=a+b; break ; case ch==’-’： c=a-b; break ; case ch==’*’： c=a*b; break ; case ch==’/ ’： c=a/b; break ; case ch==’%’：c=a%b; break ; }

PushStack (s, c) ; } ch=*A++ ; }

PopStack(s, result) ; return result ; }

3.4中缀表达式转换成后缀表达式

将中缀表达式转化为后缀表达式和前述对中缀表达式求值的方法完全类似，但只需要运算符栈，遇到运算对象时直接放后缀表达式的存储区，假设中缀表达式本身合法且在字符数组A中，转换后的后缀表达式存储在字符数组B中。具体做法：遇到运算对象顺序向存储后缀表达式的B数组中存放，遇到运算符时类似于中缀表达式求值时对运算符的处理过程，但运算符出栈后不是进行相应的运算，而是将其送入B中存放。读者不难写出算法，在此不在赘述。 程序的整体算法分两步：

第一步，从”input.txt”文件中读取中缀表达式，并应用运算符栈OpHolder把中缀表达式转换为后缀表达式，将输出结果存放在一个temp文件中。

第二步，从temp文件中读取中缀表达式，并应用操作栈Operands

6

栈的应用：表达式求值的设计

计算后缀表达式结果，将结果输出到”output.txt”文件中。

4测试方法

设计针对程序的input.txt文件，并将运行结果与期望测试进行比较。

5 程序运行效果 5.1 基本测试：

在input文件中输入表达式如下图2： 则输出结果如下图3：

图2 图3

图4

5.2扩展测试：

在input文件中输入表达式如下图5： 则输出结果如下图6：

7

栈的应用：表达式求值的设计

图5 图6

5.3容错测试：

在input文件中输入表达式如下图7： 则输出结果如下图8：

图7 图8

6 设计心得

通过此次的课程设计，巩固和加深了我对栈、队列、字符串等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（；提高利用计

8

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库(盐城工学院数据结构课程设计)栈的应用表达式求值(2)在线全文阅读。