数据结构课程设计

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)将操作

3、码弹出堆栈int 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. 是“)”，若操作码栈顶是“ (”，把弹出操作码栈顶元素，否则“ )”视为12.最后计算出结果并将其存放在 expri ，计量器加 1；13. 重复计算后，将结果保

5、存在文件里，并统计计算次数；14. 查看多次计算结果，以表形式输出；15. 查看本次计算记录，以表形式输出；16. 清除计算记录，重新计算。三、算法说明(一)程序总共有如下函数：主要函数：void start(opnd *op,num *nu)/ 程序主菜单void start2(opnd *op,num *nu)/ 第二层计算选择，子菜单void load()显示所有计算记录void save()保存计算结果void check()显示本次计算结果void result(op nd *op ,num *nu) 计算结果double caculate(opnd *op,num *nu)/简单计

6、算 +, -, *, / 表达式处理函数：int make_str()语法检查double change_num(char str)/数字字符串转成 double 型数字char procede(char top,char code)处理操作码，判断栈的操作in t cha nge_op nd(char code)/字符型操作码转换优先级，非表达式字符返回 栈操作函数：double get_num( num *n u)/查看操作数栈栈顶double pop_n um(n um *n u)/操 作数栈出栈int push_num (n um *nu ,double da)/压入操作数栈int e

7、mpty_num(num *nu)/ 判空void initstack(num *nu)char get_op nd(op nd *op)/查看栈顶char pop_op nd(op nd *op)/出栈int push_op nd(op nd *op,char co)/压栈int empty_op nd(op nd *op)/ 判空void in itstack(op nd *op)/ 初始化栈(二)函数间的调用关系：mai n()：主函数start();/ load() start();start ()程序模式函数清空文件exit(); make_str( result(op ,nu) s

8、tart2()start();/ load start();start2()子 菜单 save() start2(); check() start2();result(op ,nu计算结果in itstack(op) in itstack (nu) push_op nd(op,'=')/ push_ num(nu ,cha nge_nu m(str2);cha nge_op nd(*ps)/ push_op nd(op,*ps); procede(get_op nd(op),*ps) pop_op nd(op); push_ num(n ucaculate(op ,nu cac

9、ulate(op,nu) b=pop_num(nu) a=pop_num(nu) pop_opnd(op)main()函数：调用了一个函数start(), start()判断执行查看所有计算记录函数load(),或是清空以往的所有计算记录，或是退出程序，或是检查 输入表达式语法make_str()并计算表达式result(op,nu)的操作。result(op, nu)函数：是计算表达式，调用了初始化栈函数和字符级别判断 change_opnd(*ps,若是数字，则调用转化数字change_num(str2然后压入操作数栈，若是运算符，刚调用判断操作procede(get_opnd(op),*

10、ps)，若是“ v”，则压入操作码栈push_opnd(op,*ps),若是“=”,则弹出操作码栈顶pop_opnd(op),若是“”，则弹出操作码栈的栈顶元素和操作数 栈的两个栈顶元素，进行运算caculate(op,nu后再压入操作数栈，计算完 毕后按start()顺序运行。start2()函数：在计算结果后调用跟随的选择菜单，进行查看结果check()、保存结果save()、查看计算记录load()、回到主菜单的操作。(三)流程图:load()save()四、全部源程序清单#i nclude <stdio.h>#i nclude <stdlib.h>#includ

11、e <string.h>#in clude <math.h>#defi ne MAXSIZE 100 #defi ne N 1000int i=0;/表达式数struct expressi on/表达式结构long double result;char expstrMAXSIZE;exprN;/ 表达式的一个整体容器 stypedef struct/ 操作码栈定义char codeMAXSIZE;int top;opnd;typedef struct/ 操作数栈定义double dateMAXSIZE;int top;num;/ opnd 栈操作：void initst

12、ack(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("The "opnd" stack is full."); return 0;op->top+;op->codeop->top=co;return 1;char pop_opnd(opnd *op)/ 出栈

13、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; else

14、 return 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->d

15、atenu->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(num *nu)/ 查看栈顶 if(nu->top!=-1) return nu->datenu->top;/ 结束栈定义操作/ 函

16、数操作 ：int change_opnd(char code)/ 将字符型操作码转换成优先级，非表达式字符反 回-2 switch(code) case '=':return 1;break;case ')':return 2;break;case '+':return 3;break; case '-':return 3;break;case '*':return 4;break;case '/':return 4;break;case '(':return 0;break;/操作

17、码级别 >=0;case '1':case '2':case'3':case '4':case'5':case '6':case '7':case '8':case '9':case'0':case '.': return-1;/ 操作数级别 =-1 ；default: return -2;/其它符号级别 =-2char procede(char top,char code)/处理操作码，判断栈的操作if(chan

18、ge_opnd(code)=0)/ “(”入栈return ('<');elseif(change_opnd(code)=2&&change_opnd(top)=0)/ “(”和“)”同时 出现，“(”出栈，“)”不入栈return ('=');elseif(change_opnd(code)<=change_opnd(top)/ 弹出两个数字和一 个符号进行计算 return ('>');else return ('<');/ 入栈double change_num(char str)/

19、数字字符串转成 double 型数字char *s=str;in t p=1,q=0;/p=小数点前位数，q=小数点后位数char d=".",z="0"double da=0;if(strstr(str,d)=0)/判断是否有小数点p=strlen(str);elseif(strstr(str,d)=str)/没有输入小数点前的数，如“ .032”p=1;q=strlen(str)-1; strcpy(str,strcat(z,str);elsep=strstr(str,d)-str; q=strlen(str)-p-1;for(int i=0;i&l

20、t;p;i+)/ 小数点前的各位数乘以各自的阶数，然后叠加： 123=1*100+2*10+3*1da=da+(int)stri-48)*pow(10,p-i-1);for(int j=0;j<q;j+)/ 小数点后的各位数乘以各自的阶数，然后叠加： 0.123=1*0.1+2*0.01+3*0.001 da=da+(int)strstrlen(str)-1-j-48)*pow(0.1,q-j);return da;int make_str()/ 语法检查char *p,*p1;int n=0;printf("n 请输入表达式，以“ =”结尾： ");gets(exp

21、ri.expstr);p=expri.expstr;p1=p;while(1) if(*p='0') if(*(p-1)='=')/ 语法检查结束 break; else / 没有以"=" 结尾 printf("n 表达式以 "=" 结尾。请重新输入： "); gets(expri.expstr); p=expri.expstr; n=0; continue;if(change_opnd(*p)=2)/ 一个")" ， n-1n-;if(change_opnd(*p)=0)/ 一个&

22、quot;(" ， n+1n+;if(*p1=*p)/ 第一个字符的判断，只能以“数字”或“ ( ”开头，不能 有非法字符if(change_opnd(*p)>0)printf("n 表达式只能以“数字”或“ ( ”开头。请重新输入： ");gets(expri.expstr);p=expri.expstr;n=0; continue;elseif(change_opnd(*p)=-2)printf("n 表达式 "%c" 为非法字符。请重新输入： ",*p); gets(expri.expstr);p=expri.e

23、xpstr;n=0;continue;else/ 合法刚跳到下一个字符 p=p+1; continue;if(change_opnd(*p)=-2)/ 非法字符判断printf("n 表达式 "%c" 为非法字符。请重新输入： ",*p); gets(expri.expstr);p=expri.expstr;n=0; continue;if(change_opnd(*p)=0)/"(" 前一个字符只能是 "+、-、*、/ 、(" if(change_opnd(*(p-1)<3&&change_

24、opnd(*(p-1)>4) if(change_opnd(*(p-1)!=0)printf("n 表达式"%c"或"%c"不符合语法。请重新输 入：",*(p-1),*p);gets(expri.expstr); p=expri.expstr; n=0;continue;if(change_opnd(*p)>0)/"+、-、*、/ 、=、)" 前一个字符只能是数字和")"if(change_opnd(*(p-1)!=-1) if(change_opnd(*(p-1)!=2) pri

25、ntf("n 表达式"%c"或"%c"不符合语法。请重新输 入： ",*(p-1),*p);gets(expri.expstr); p=expri.expstr; n=0;continue;if(change_opnd(*p)=1)/ 判断表达式中是否有 "=" 重复出现，最后括号 是否配对 if(*(p+1)!='0') printf("n 表达式中 "=" ，只能出现在表达式结束处。请 重新输入： ");gets(expri.expstr);p=expri

26、.expstr;n=0;continue;if(n!=0)printf("n 表达式括号不配。请重新输入： "); gets(expri.expstr);p=expri.expstr;n=0;continue; p=p+1;return 1;double caculate(opnd *op,num *nu)/简单计算 +，- ，* ，/double b=pop_num(nu),a=pop_num(nu); switch(pop_opnd(op)case '+':return(a+b);break;case '-':return(a-b);br

27、eak;case '*':return(a*b);break;case '/':return(a/b);break;void result(opnd *op,num *nu)/ 计算结果 char str2MAXSIZE="",str32="0"char *ps=expri.expstr;初始化栈initstack(op);/ initstack(nu);push_opnd(op,'=');while(!(*ps='=')&&(get_opnd(op)='='

28、)/ 检查是表达式和操作码是 否到尾if(change_opnd(*ps)=-1)/ 操作数处理while(change_opnd(*ps)=-1)strncpy(str3,ps,1);/ 数字字符一个个取出放在 str2 strcat(str2,str3);ps+;push_num(nu,change_num(str2);strcpy(str2,"");else / 操作码处理switch(procede(get_opnd(op),*ps)case '<':push_opnd(op,*ps);break;case '=':pop_op

29、nd(op);break;case '>':push_num(nu,caculate(op,nu);continue;break;if(*ps=')'&&get_opnd(op)='=')ps+; continue;if(*ps='='|get_opnd(op)='=')continue;/ 表达式和操作码有一个到尾，则跳出继续循环ps+;expri.result=get_num(nu);printf("nt 表 达 式 ： %st 计 算 结 果： %lfn",expri

30、.expstr,expri.result);printf("tn");i+;/ 表达式个数加 1；void check()/ 显示计算结果for(int n=0;n<i;n+) printf("n"); printf("t%dn",n+1);printf("t 表达式： %s",exprn.expstr); printf("t 计算结果： %.2lfn",exprn.result); if(exprn.expstr0='#')break;/ 只显示当次计算的记录printf

31、("tn");void save()/ 保存计算结果FILE *fp;int m,n; if(fp=fopen("calculate.dat","ab")=NULL)/ 创建文件 printf("cannot open filen"); return; if(expri-1.expstr0='#')/ 不能重复保存printf("* 提醒：记录已保存过，不需要再次保存。 n"); return;for(n=i;n>0;n-)/记录最后一个 #号位置，即未保存的结果的开始位置

32、 , 重复保存只会追加if(exprn-1.expstr0='#') break;strcpy(expri.expstr,"# 表达式个数： ");/ 每次保存都统计计算次数 expri.result=i-n;i+; for(m=n;m<i;m+) if(fwrite(&exprm,sizeof(struct expression),1,fp)!=1)/ 将表达 式和计算结果存到文件中printf("file write errorn");fclose(fp);printf("* 提醒：计算记录已经保存 n&quo

33、t;);void load()/ 显示所有计算记录 int m; expression eN; FILE *fp; printf("n"); if(fp=fopen("calculate.dat","rb")=NULL)/ 空文件 printf("tn");printf("* 提醒：没有记录信息，请进行计算并保存信息 :n"); return;for(m=0;fread(&em,sizeof(struct expression),1,fp);m+)/ 按 照 expression 结构一

34、个个读取printf("t%d n",m+1);printf("t 表 达 式 ： %st 计 算 结 果： %.2lfn",em.expstr,em.result);if(em.expstr0='#')/ 控制输出不同次计算的记录 m=-1; printf("n");printf("tn"); fclose(fp); printf("n");void help()printf("t 表达式计算，请用户正确输入表达式，不得出现非法字符及 字符nt重复出现，表达式以“二”

35、号结尾，若计算到负数，如“-20”，请输nt 入“ (0-20) ”。");printf(" 请用户及时保存计算结果以便查看， 每次回到主菜单 nt 时，若没 有保存结果，则当次计算结果会被清除。 n");void start(opnd *op,num *nu);void start2(opnd *op,num *nu)/ 第二层计算选择菜单char r;while(1)printf("tn");prin tf("nttt查看本次计算记录，请输入 "r" 或 "R"nnttt保存本次计算记录，请

36、输入"s"或"S"nnttt查看所有计算记录，请输入"1"或"L"nnttt回到主菜单，按任意键返回ntt:");scanf("%s",&r);if(r='r'|r='R')check();elseif(r='s'|r='S')save();elseif(r='l'|r='L')load();elsei=0; start(op,nu);void start(opnd *op,num

37、*nu)/ 程序主导char ch,c,g;g='Y'printf("nttt查看记录，请输入 "1" 或"L"nnttt 清空记录，请输入"C"或"c"nnttt计算式子，请输入 "丫"或"y"nnttt 退出程序，按任意键退出 ntt:");scanf("%s",&c);getchar(ch);if(c='l'|c='L')load();start(op,nu);elseif(

38、c='Y'|c='y') while(1) if(g='Y'|g='y') if(make_str()/ 语法检查 printf("tn");result(op,nu);/ 计算elseprintf("nt* 提醒：计算结束！ nn"); break;，否则按任意键结printf("n继续计算，请输入"丫"或"y"束计算 :");scanf("%s",&g); getchar(ch); start2(op

39、,nu);else if(c='C'|c='c')/ 清空文件 /* FILE *fp; fp=fopen("calculate.dat","w"); fclose(fp);*/printf("tn");remove("calculate.dat");printf("* 提醒：所有记录已经清空。 "); start(op,nu);elseprintf("nt* 提醒：结束！ n"); exit(0);void main()opnd op;/ 操作码栈num nu;/ 操作数栈printf("nt 计 算 表 达 式nn");help();start(&op,&nu);/ 启动程序五、程序运行的测试与分析A组：测试输入：1