表达式求值算法实现.doc

河南工程学院《数据结构与算法》课程设计
成果报告
表达式求值算法实现
2014 年 12 月 29 日
题 目
表达式的相关函数库实现
考核项目
考核建的两个栈直接对表达式进行计算。分别构建一个char类型和一个double类型的栈函数。
3
（2）在main函数中让用户进行输入，将用户输入的字符串进行循环、判断，并将判断后的字符串传递到新的数组中，循环结束后，再将数组传递给中缀表达式转后缀表达式函数。 
（3）在Operate()函数中先创建一个数字栈和一个符号栈，对表达式进行循环，直到元素为’\0’。在循环中如果元素为数字，将元素赋给新的数组s[]，再判断下一个元素，若是则利用函数将数组中的字符串转换成double类型的数字，然后数字进栈，清空数组s[]；否则，继续判断。若元素不为数字，则先看栈顶，如果栈为空或栈顶元素为‘（’或者栈顶元素为‘+’或‘—’并且现有元素为‘*’、‘/’或‘%’又或是现有元素为，则现有元素进栈；否则，再对现有元素进行判断：如果现有元素为‘）’，运算符出栈直到‘（’出栈；否则，运算符出栈直到栈空或者栈顶元素的优先级低于现有运算符，现有运算符才进栈。每当有一个运算符出栈，就从数栈中取两个数与运算符一起传递给Operate()函数,并将函数的返回值压入栈中。循环结束后，将栈中的运算符全部依次输出，每当有一个运算符出栈，就从数栈中取两个数与运算符一起传递给Operate()函数,并将函数的返回值压入栈中，最后输出数字栈中的数字成为表达式的最终结果，再销毁栈。 
（4）Operate()函数是利用switch语句对传入进来的运算符进行判断，并将传入的两个数进行相应的运算，并返回运算结果。
（5）各模块的主要功能
*Push(SC *s,char c)：把字符压栈
*Push(SF *s,float f)：把数值压栈
*Pop(SC *s)：把字符退栈
*Pop(SF *s)：把数值退栈
Operate(a,theta,b)：根据theta对a和b进行'+' 、'-' 、'*' 、'/' 、'^'操作
In(Test,*TestOp)：若Test为运算符则返回true，否则返回false
ReturnOpOrd(op,*TestOp)：若Test为运算符，则返回此运算符在数组中的下标
precede(Aop,Bop)：根据运算符优先级表返回Aop与Bop之间的优先级EvaluateExpression(*MyExpression)：用算符优先法对算术表达式求值
4
程序流程图
程序是通过栈与算法来实现表达式求值的。在程序执行之后，先判断算法的优先级在执行Operate算法。通过栈对字符与数据的存放之后，在对表达式进行判断,若表达式错误则输出错误提示，若表达式正确则进行计算输出正确结果。

测试程序说明
1． 一般来说，计算机解决一个具体问题时，需要经过几个步骤：首先要从具体问题抽象出一个适当的数学模型，然后设计一个解决此数学模型的算法，最后编出程序，进行测试，调试直至得到想要的答案。对于算术表达式这个程序，主要利用栈，把运算的先后步骤进行分析并实现简单的运算！为实现算符优先算法，可以使用两个栈，一个用以寄存运算符，另一个用以寄存操作数和运算结果。
2． 演示程序是以用户于计算机的对话方式执行，这需要一个模块来完成使用者与计算机语言的转化。
5
3．程序块的功能介绍：
（1）栈的抽象数据类型定义：
ADT Stack {
数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}
数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,…,n}
 约定an端为栈顶，ai端为栈底
（２）基本操作：
　Push (&S,e)
　初始条件：栈S已存在
　操作结果：插入元素e为新的栈顶元素
　Pop (&S,&e)
　初始条件：栈S已存在且非空
　操作结果：删除S的栈顶元素，并用e返回其值
　} ADT Stack
6
3 程序清单
#include""
#include""
#include""
#include""
#define true 1
#define false 0
#define OPSETSIZE 8
typedef int Status;
unsigned c