数据结构与算法课程设计报告13002918

1、装.订.线.通达学院算法与数据结构设计报告（ 2014/2015学年 第 二 学期 ）题 目： 模拟简单计算器 专 业 物联网工程 学 生 姓 名 汤 勇 班 级 学 号 13002918 指 导 教 师 余亮 指 导 单 位 通达学院 日 期 2015年4月10日 目录一、课题内容和要求1二、需求分析1三、概要设计11设计理念12.子函数功能23.函数的调用4四、详细设计4五、测试及结果分析11加法测试11减法测试11乘法测试12除法测试12混合运算13六、调试过程中的问题13七、课程设计总结15一、课题内容和要求利用所学的数据结构的基本知识，设计一个计算器（90）输入：带有括号、+，-，X

2、,/ 的表达式；输出：运算结果实例：输入：（4*3-（2+1）*2 输出： 18要求：1）对不合法输入进行检测并提示；2）对合法输入求出正确解；二、需求分析本程序主要是采用栈的理论知识，主要用到两个结构体栈，一个用来转化表达式，一个用来计算表达式。三、概要设计1设计理念 首先，用一个字符数组来存储用户输入的中缀表达式。然后用栈来把这个表达式转化为后缀表达式，转化时要进行符号优先级比较，这里将*/的优先级定为2，+-定为1，括号和=定为0。具体思想如下：例如用户输入了1+2*3=，将其存放入一个字符数组中。先在栈的底部存放一个=号符，用作符号优先级比较。首先将1存放到另外一个字符数组s1中，再将

3、+号入栈。入栈的同时与底部的=比较优先级，+的优先级高于=，所以不出栈，之后将2存放入s2中，然后再将*入栈，入栈的同时与+比较符号优先级，*比+高，所以不出栈。再将3存入s2中。之后将栈中不是=的运算符都弹出栈，并依次存入s2中。所以s2中的表达式为123*+。之后进行计算，计算时用到浮点栈。首先将s2中的字符依次入栈，遇到运算符时进行计算。所以将123入栈后，再将*入栈的同时，将前面两个数字进行运算，算出结果为6并存入栈中，之后再将+入栈，再与1进行运算，结果即为7，然后输出结果。2.子函数功能pseqstack1 init_seqstack1(void) pseqstack1 S; S=

4、(pseqstack1)malloc(sizeof(pseqstack1); if(S) S->top1=-1; return S;初始化栈 int empty_seqstack1(pseqstack1 S) if(S->top1=-1) return 1; else return 0; 判断栈是否为空int push_seqstack1(pseqstack1 S,datatype1 X进栈int pop_seqstack1(pseqstack1 S,datatype1 *X)出栈int GetTop(seqstack *s) 取栈顶元素int PP(char op,char c)

5、 比较栈顶元素与当前读入的运算符的优先级int Ope(int a,char m,int b) 从数字栈中取出的两个数的计算int priority(char op)优先级判断函数int infix_exp_value(char *infixexp,char *postfixexp将指针infixexp指向的中缀表达式转换为指针postfixexp指向的后缀表达式double postfix_exp(char *A)求后缀表达式的值3.函数的调用 主函数栈的建立typedef struct stack1 stack2计算表达式operand=operand*10+(ch-'0'

6、);输出postfix_exp(B) 四、详细设计15# include <stdio.h># include <malloc.h># include <conio.h># define maxsize 100typedef double datatype1;typedef char datatype2;typedef struct stack1 datatype1 data1maxsize; int top1;/*栈顶元素*/seqstack1,*pseqstack1; /*顺序栈*/typedef struct stack2 datatype2 data

7、2maxsize; int top2;/*栈顶元素*/seqstack2,*pseqstack2; /*顺序栈*/*栈的初始化*/pseqstack1 init_seqstack1(void) pseqstack1 S; S=(pseqstack1)malloc(sizeof(pseqstack1); if(S) S->top1=-1; return S;pseqstack2 init_seqstack2(void) pseqstack2 S; S=(pseqstack2)malloc(sizeof(pseqstack2); if(S) S->top2=-1; return S;/

8、*判断栈空*/int empty_seqstack1(pseqstack1 S) if(S->top1=-1) return 1; else return 0;int empty_seqstack2(pseqstack2 S) if(S->top2=-1) return 1; else return 0;/*X入栈*/int push_seqstack1(pseqstack1 S,datatype1 X) if(S->top1=maxsize-1) printf("栈满，无法入栈！n"); return 0; else S->top1+; S->

9、;data1S->top1=X; return 1; int push_seqstack2(pseqstack2 S,datatype2 X) if(S->top2=maxsize-1) printf("栈满，无法入栈！n"); return 0; else S->top2+; S->data2S->top2=X; return 1; /*X出栈*/int pop_seqstack1(pseqstack1 S,datatype1 *X) if(empty_seqstack1(S) return 0; else *X=S->data1S-&

10、gt;top1; S->top1-; return 1; int pop_seqstack2(pseqstack2 S,datatype2 *X) if(empty_seqstack2(S) return 0; else *X=S->data2S->top2; S->top2-; return 1; /*求栈顶元素*/int gettop_seqstack1(pseqstack1 S,datatype1 *X) if(empty_seqstack1(S) return 0; else *X=S->data1S->top1; return 1;int gett

11、op_seqstack2(pseqstack2 S,datatype2 *X) if(empty_seqstack2(S) return 0; else *X=S->data2S->top2; return 1;/*判断字符是否为操作数。若是返回1，否则返回0*/int isnum(char c) if(c>='0' && c<='9') return 1; else return 0;/*求后缀表达式的值*/double postfix_exp(char *A) pseqstack1 S;/*定义栈S*/double o

12、perand=0; double result;/*存放栈顶元素*/double a;/*运算符ch前的操作数出栈存入a*/double b;/*运算符ch后的操作数出栈存入b*/double c;/*c=a ch b*/ char ch;/*存放读取到的表达式(A)的字符*/ ch=*A+;/*读表达式字符=>A*/ S=init_seqstack1();/*初始化栈*/ while(ch!='#')/*遇到元素!='#'时*/ if(isnum(ch)/*判断ch是否为数字字符,计算出操作数*/ operand=operand*10+(ch-'

13、0'); else/*否则*/ if(operand)push_seqstack1(S,operand);/*当前字符不是数字,操作数结束,要入栈*/operand=0;if(ch!='' && ch!=' ')pop_seqstack1(S,&b);/*运算符ch后的操作数出栈存入b*/pop_seqstack1(S,&a);/*运算符ch前的操作数出栈存入a*/switch(ch)/*求 a ch b=? ,将结果赋给 c */ case '+' : c=a+b;break;case '-

14、9; : c=a-b;break;case '*' : c=a*b;break;case '/' :if(b!=0)c=a/b;elseprintf("分母为零!"); push_seqstack1(S,c);/*将c压入栈中*/ ch=*A+;/*指针向下移动一位*/ /*遇到'#'循环结束*/ gettop_seqstack1(S,&result);/*此时栈顶元素即为计算结果result*/ return result;/*优先级判断函数*/int priority(char op)switch(op)case

15、'#': return 1;case ')': return 2;case '+': case '-': return 3;case '*': case '/': return 4;case '(': return 5;default : return 0; /*将指针infixexp指向的中缀表达式转换为指针postfixexp指向的后缀表达式*/int infix_exp_value(char *infixexp,char *postfixexp)pseqstack2 S;/*定

16、义栈S*/int count=0;char w;/*存放读取到的表达式(infixexp)的字符*/char c;/*存放栈顶元素*/char topelement;/*存出栈元素*/S=init_seqstack2();/*初始化栈*/if(!S)/*栈的初始化判断*/printf("栈初始化失败!");return 0;push_seqstack2(S,'#');/*将结束符'# '加入运算符栈S中*/w=*infixexp;/*读表达式字符=>w*/while(gettop_seqstack2(S,&c),c)!='

17、;#'|w!='#')/*<3>栈顶元素不等于'#'或w不等于'#'时循环*/if(isnum(w)/*判断w是否为操作数,若是直接输出,读下一个字符=>w,转<3>*/if(count)*postfixexp=''postfixexp+;count=0;*postfixexp=w;postfixexp+;w=*(+infixexp);else/*w若是运算符分类如下*/count=1;if( (gettop_seqstack2(S,&c),c)='(' &&a

18、mp; w=')' )/*如果栈顶为'('并且w为')'则'('出栈不输出,读下一个字符=>w,转<3>*/pop_seqstack2(S,&topelement); /*将'('出栈存入topelement*/w=*(+infixexp);elseif( (gettop_seqstack2(S,&c),c)='(' | priority( (gettop_seqstack2(S,&c),c) ) < priority(w) )/*如果栈顶为'

19、('或者栈顶优先级小于w优先级,则w入栈,读下一个字符=>w，转<3>*/push_seqstack2(S,w);w=*(+infixexp);else/*否则*/*从运算符栈中出栈并输出,转<3>*/pop_seqstack2(S,&topelement);*postfixexp=topelement;postfixexp+;*postfixexp='#'/*在指针postfixexp指向的后缀表达式结尾追加字符'#'*/*(+postfixexp)='0'/*在指针postfixexp指向的后缀表达式最后追加结束符'0'*/return 1;/*主函数*/int main() int i=0;char Amaxsize;char Bmaxsize;printf("请输入表达式,如:11+22#,必须以#号结尾!n"); /* 1+2*(9+7)-4/2# 23+(12*3-2)/4+34*5/7)+108/9# */Ai=getchar();while(Ai+!='#&