《表达式求值c++ 数据结构课设报告》由会员分享，可在线阅读，更多相关《表达式求值c++ 数据结构课设报告（23页珍藏版）》请在金锄头文库上搜索。
1、1数 据 结 构 课 程 设 计院 别 计 算 机 与 通 信 工 程 学 院专 业 计 算 机 科 学 与 技 术班级学号 姓 名 指导教师成 绩2013 年 7 月 18 日2目录一、设计课题 .3二、需求分析 .3三、算法设计 .3四、调试分析 .9五、用户手册 .10六、测试结果 .10七、附录（源代码） .13八、参考文献 .21 31、设计课题： 表达式求值二、需求分析：当用户输入一个合法的算术表达式后，能够返回正确的结果。能够计算的运算符包括：加、减、乘、除、括号；能够计算的操作数要求在实数范围内；对于异常表达式能给出错误提示。3、算法设计：概要说明：为实现上述程序功能，1. 首
2、先置操作数栈为空栈，表达式起始符为运算符栈的栈底元素；2. 依次扫描表达式中每个字符，若是操作数则进 OPND 栈；若是运算符，则 和 OPTR 栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕。3. 先做一个适合个位的+-*/运算, 其次就要考虑到对 n 位和小数点的运算。模块间调用关系：调用主程序模块输出模块详细说明（ADT 描述） ： ADT SqStack数据对象：D= | ElemSet,i=1,2,，n, n0iai数据对象：R1=| , ,i=2,，n1,iiDai约定 端为栈顶， 端为栈底。ni基本操作：InitStack(&S)操作结果：构造一个空栈 S。GetT
3、op(S)初始条件：栈 S 已存在。操作结果：用 P 返回 S 的栈顶元素。Push(&S，e)初始条件：栈 S 已存在。操作结果：插入元素 ch 为新的栈顶元素。Pop(&S，e)初始条件：栈 S 已存在。操作结果：删除 S 的栈顶元素。In(c)操作结果：判断字符是否是运算符，运算符即返回 1。Precede(c1, c2) 初始条件：c1,c2 为运算符。4操作结果：判断运算符优先权，返回优先权高的。Operate(a,op,b)初始条件：a,b 为整数，op 为运算符。操作结果：a 与 b 进行运算，op 为运算符，返回其值。EvaluateExpression()初始条件：输入表达式
4、合法。操作结果：返回表达式的最终结果。ADT Stack流程图及主要函数模块说明:1. 数据类型：typedef struct double *base;double *top;int stacksize;SqStack1;typedef struct char *base;char *top;int stacksize;SqStack2;2. Precede(char c1,char c2) 判断运算符优先权，返回优先权高的。算符间的优先关系如下：+ - * / ( ) #+ - * / ( # , , , , , , , , , , , , , , , , , , , , , , , ,
5、!, , , =0&c=0&c:/退栈并将运算结果入栈/ cout#include #include #include using namespace std;#define OK 1#define ERROR 0#define OVERFLOW -1#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef int Status; typedef structdouble *base;double *top;int stacksize;SqStack1;typedef structchar *base;char *top;int s
6、tacksize;SqStack2;Status InitStack1(SqStack1 &S)14S.base=(double *)malloc(STACK_INIT_SIZE*sizeof(double);if(!S.base) exit (OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;/InitStack1Status InitStack2(SqStack2 &S)S.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char);if(!S.base) exit (OVERFL
7、OW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;/InitStack2Status GetTop1(SqStack1 S,double &e)/若栈不空，则用 e 返回 S 的栈顶元素，并返回 OK;否则返回 ERRORif(S.top=S.base) return ERROR;e= *(S.top-1); /返回栈顶元素return OK;/GetTop1char GetTop2(SqStack2 S)15/若栈不空，则用 e 返回 S 的栈顶元素，并返回 OK;否则返回 ERRORif(S.top=S.base) /cout=S
8、.stacksize) /栈满，追加存储空间S.base=(double*) realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(float);if(!S.base) return ERROR;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;/if*S.top+=e;return OK;/Push116Status Push2(SqStack2 &S,char e)/插入元素 e 为新的栈顶元素if(S.top-S.base=S.stacksize) /栈满，追加存储空间S.base=(
9、char*) realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char);if(!S.base) return ERROR;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;/if*S.top+=e;return OK;/Push2Status Pop1(SqStack1 &S,double &e)/若栈不空，则删除 S 的栈顶元素，用 e 返回其值，并返回 OK；否则返回 ERRORif(S.top=S.base) /cout,!,=0&a=0&a=0&c=0&c:/退栈并将运算结果
10、入栈/ coutworldendl;Pop2(OPTR,theta);/coutwwthetaendl;Pop1(OPND,b);/coutbendl;Pop1(OPND,a);Push1(OPND,Operate(a,theta,b);break;case!:cout请输入正确的表达式：endl;break; /switch/whileGetTop1(OPND,k); cout表达式结果为： kendl;return OK;/EvaluateExpressionint main()EvaluateExpression();return 0;八、参考文献231.数据结构(C 语言版) 严蔚敏 清华大学出版社2.C 语言程序设计 丁峻岭 中国铁道出版社3.C+程序设计 谭浩强 清华大学出版社
