《数据结构课程设计利用栈求表达式的值》由会员分享，可在线阅读，更多相关《数据结构课程设计利用栈求表达式的值（22页珍藏版）》请在金锄头文库上搜索。
1、课 程 设 计 报 告题目十三、利用栈求表达式的值一、 设计任务与目标编写程序实现表达式求值，即验证某算术表达式的正确性，若正确，则计算该算术表达式的值。主要功能描述如下：1、从键盘上输入表达式，以“=” 号结束表达式。2、分析该表达式是否合法：（1）是数字，则判断该数字的合法性。若合法，则压入数据到堆栈中。（2）是规定的运算符，则根据规则进行处理。在处理过程中，将计算该表达式的值。（3）若是其它字符，则返回错误信息。3、若上述处理过程中没有发现错误，则认为该表达式合法，并打印处理结果。附加功能：1. 规定表达式的合法性2. 小数计算3. 计算记录的保存与查看4.（1）规定表达式的合法性，括号
2、配对，不能出现“6+3”、“6+3”等符号重叠的情况。（2）表达式开头只能是数字或“（”，表达式中只能有一个“=”。程序中应主要包含下面几个功能函数：void initstack()：初始化堆栈int make_str()：语法检查并计算int push_num(double num)：将操作数压入堆栈char procede(char top,char code)：处理操作码int change_opnd(int operate)：将字符型操作码转换成优先级int change_opnd(char code)：将操作码压入堆栈char pop_opnd(opnd *op)：将操作码弹出堆栈i
3、nt caculate(int cur_opnd)：简单计算+，-，*，/double pop_num(num *nu)：弹出操作数二、 方案设计与论证1. 定义一个expression全局表达式结构体expr1000存放计算过的表达式(expstrMAXSIZE)和计算结果(result)、一个计量器(i)、一个表达式字符串、 一个操作码栈和一个操作数栈；2. 把表达式字符串从头到尾逐一扫描，将输入的表达式进行语法检查；3. 第一个字符只能是数字或“（”，最重一个字符只能是“=”；4. 表达式括号必须配对，中间不能出现“=”；5. 在“（”前面只能是“+、*、/、( ”，在“+、*、/、=、
4、)”前面只能是数字或“）”；6. 把表达式字符串从头到尾逐一扫描，直到表达式扫描完毕，操作码栈为空；7. 把字符根据运算优先级别选择操作；8. 把表达式中的数值部分字符串转成数值压入操作数栈；9. 是“(”直接压入到操作码栈，级别比操作码栈顶元素高的，把运算符压入操作码栈；10. 级别比操作码栈低的，弹出操作码栈的栈顶元素和操作数栈的两个栈顶元素，进行运算后再压入操作数栈；11. 是“)”，若操作码栈顶是“(”，把弹出操作码栈顶元素，否则“)”视为级别最低的元素，重复7；12. 最后计算出结果并将其存放在expri，计量器加1；13. 重复计算后，将结果保存在文件里，并统计计算次数；14. 查
5、看多次计算结果，以表形式输出；15. 查看本次计算记录，以表形式输出；16. 清除计算记录，重新计算。三、 算法说明(一) 程序总共有如下函数：主要函数：void start(opnd *op,num *nu)/程序主菜单void start2(opnd *op,num *nu)/第二层计算选择，子菜单void load()/显示所有计算记录void save()/保存计算结果void check()/显示本次计算结果void result(opnd *op,num *nu)/计算结果double caculate(opnd *op,num *nu)/简单计算+，-，*，/表达式处理函数：in
6、t make_str()/语法检查double change_num(char str)/数字字符串转成double型数字char procede(char top,char code)/处理操作码，判断栈的操作int change_opnd(char code)/字符型操作码转换优先级，非表达式字符返回-2栈操作函数：double get_num(num *nu)/查看操作数栈栈顶double pop_num(num *nu)/操作数栈出栈int push_num(num *nu,double da)/压入操作数栈int empty_num(num *nu)/判空void initstack
7、(num *nu)char get_opnd(opnd *op)/查看栈顶char pop_opnd(opnd *op)/出栈int push_opnd(opnd *op,char co)/压栈int empty_opnd(opnd *op)/判空void initstack(opnd *op)/初始化栈(二) 函数间的调用关系：l main()：主函数 start();load() start();l start()程序模式函数清空文件exit();make_str()result(op,nu) start2()start(); load start();l start2()子菜单 save
8、() start2(); check() start2();l result(op,nu)计算结果initstack(op) initstack(nu) push_opnd(op,=) push_num(nu,change_num(str2);change_opnd(*ps) push_opnd(op,*ps)；procede(get_opnd(op),*ps) pop_opnd(op); push_num(nu,caculate(op,nu)l caculate(op,nu) b=pop_num(nu) a=pop_num(nu) pop_opnd(op) main()函数：调用了一个函数s
9、tart()，start()判断执行查看所有计算记录函数load()，或是清空以往的所有计算记录，或是退出程序，或是检查输入表达式语法make_str()并计算表达式result(op,nu)的操作。 result(op,nu)函数：是计算表达式，调用了初始化栈函数和字符级别判断change_opnd(*ps)，若是数字，则调用转化数字change_num(str2)然后压入操作数栈，若是运算符，刚调用判断操作procede(get_opnd(op),*ps)，若是“”，则弹出操作码栈的栈顶元素和操作数栈的两个栈顶元素，进行运算caculate(op,nu)后再压入操作数栈，计算完毕后按sta
10、rt()顺序运行。 start2()函数：在计算结果后调用跟随的选择菜单，进行查看结果check()、保存结果save()、查看计算记录load()、回到主菜单的操作。(三) 流程图:load()mainstart()result()save()ClearFileExit()Start2()check()四、 全部源程序清单#include #include #include #include #define MAXSIZE 100#define N 1000int i=0;/表达式数struct expression/表达式结构long double result;char expstrMA
11、XSIZE;exprN;/表达式的一个整体容器stypedef struct/操作码栈定义char codeMAXSIZE;int top;opnd;typedef struct/操作数栈定义double dateMAXSIZE;int top;num;/opnd栈操作：void initstack(opnd *op)/初始化栈op-top=-1;int empty_opnd(opnd *op)/判空if(op-top=-1)return 0;else return 1;int push_opnd(opnd *op,char co)/压栈if(op-top=MAXSIZE-1)printf(T
12、he opnd stack is full.);return 0;op-top+;op-codeop-top=co;return 1;char pop_opnd(opnd *op)/出栈char a=0;if(op-top=-1)printf(error:The opnd stack is empty.);return a;a=op-codeop-top;op-top-;return a;char get_opnd(opnd *op)/查看栈顶char a=0;if(op-top=-1)printf(error:The opnd stack is empty.);return a;elsere
13、turn op-codeop-top;/num栈操作：void initstack(num *nu)nu-top=-1;int empty_num(num *nu)/判空if(nu-top=-1)return 0;else return 1;int push_num(num *nu,double da)/压栈if(nu-top=MAXSIZE-1)printf(error:The date stack is full.);return 0;nu-top+;nu-datenu-top=da;return 1;double pop_num(num *nu)/出栈double a=0;if(nu-top=-1)printf(error:The date stack is empty.);return a;a=nu-datenu-top;nu-top-;return a;double get_num
