16、算数表达式的求解.doc

数据结构课程设计Course Design of Data Structures计算机系072姓名：杨明明 学号：06422020指导老师：张敏 2011年4月8日 目录一、设计题目 二、设计内容三、实验分析四、程序设计五、实验步骤六、调试分析七、测试、八、程序所用到的函数九、结论一、设计题目问题描述：给定一个算术表达式，通过程序求出最后的结果二、设计内容1 从键盘输入要求解的算术表达式；2 采用栈结构进行算术表达式的求解过程；3 能够判断算术表达式正确与否；4 对于错误表达式给出提示；5 对于正确的表达式给出最后的结果；三实验分析首先通过键盘输入表达式并将字符串入栈,然后按从左到右的循环判断表达式的格式正确与否，当表达式的+，-，/,( )等运算符号间有两个小数点时，表达式为错误，给出错误提示并转到起始环节，然后根据给定运算顺序来做运算，有括号要先算括号里面的，计算的结果赋值到浮点型数据并输出结果。四程序设计 1.栈的建立 先建立两个不同的栈分别存放运算符号和数字，然后初始化栈。当从键盘输入符号时，首先判断输入的是否是括号，若是，则在括号标志位置1，再判断是否是负号，若为负，则再输入一位，并将负号标志位置1；输入字符不满足要求时，提示错误，重新输入；（1）、定义栈的抽象数据类型定义：ADT Stack数据对象： D=ai| aiDateType,i=1,2,，n，n=0数据关系： R1=| ai-1,aiD,i=2,n基本操作：InitStack(& S)（2）、栈类型 思想： 本程序中栈采用的链式存储结构，因为存放操作符和操作数的结点类型不一样，所以设计了两个结点。栈的基本操作采用了重载的方法，使两种结点类型都能使用。 （1）、存放操作符的结点： struct node2 char data2; /存放操作符 node2 *next2; （2）、存放操作数的结点：struct node double data; /存放操作数 node *next;2.数字输入当字符是数字时，若紧接该字符之后的仍然是数字，则说明输入的为多位数，按十进制算法*10相加得到实数a入栈。3.符号输入输入符号时，根据不同的标志位，有不同的处理方法：若两运算符相连，提示错误，重新输入；当有左括号时，根据标志位判断，若未找到右括号，则提示输入错误，重新输入。4.运算符号栈中运算符号op出栈，数字栈中的数字出栈并赋值给a，b，根据给定的运算优先级（括号，*，/,+，-），在除数b不为0的条件下，调用Execute(float a,char op,float b)函数，得出结果v，压入栈中，若之前有负号（负号标志位位为1），则求其相反数v=-v，并将结果压入数字栈中，然后不断循环，直到遇到“=”停止，然后从数字栈输出结果。5、本程序包含的三个模块（1）、主程序模块； (2)、栈模块实现栈抽象数据类型；（3）、表达式求解模块求解表达式值的抽象数据类型； 主程序模块 表达式求解模块 栈模块 图1三个模块之间的调用关系如图1所示。6、函数的调用关系图： 主程序s.Output() s.Put() s.Help() 退出程序五实验步骤 #includeusing namespace std;#define TRUE 1#define FALSE 0#define Stack_Size 20#define Stack_Float 30/*建立字符栈*/ typedef struct char elemStack_Size;/存储定义 int top;Stack_char; void InitStack(Stack_char*S)/初始化顺序栈 S-top=-1; int Push(Stack_char *S,char x)/进栈 if(S-top=Stack_Size-1) return (FALSE); S-top+; S-elemS-top=x; return (TRUE);int Pop(Stack_char*S,char*x)/出栈 if(S-top=-1) return(FALSE); else *x=S-elemS-top; S-top-; return(TRUE); int GetTop(Stack_char*S,char*x)/ 取栈顶 if(S-top=-1) return(FALSE); else *x=S-elemS-top; return(TRUE); char GetTop(Stack_char S) char x; GetTop(&S,&x); return x;void ClearStack(Stack_char*S)/清空栈 if(S-top!=-1) S-top=-1;/*建立数字栈*/ typedef struct/建立 float elemStack_Float; int top;Stack_float;void InitStack(Stack_float*S)/初始化 S-top=-1;int Push(Stack_float*S,float e) /进栈 if(S-top=Stack_Float-1) return(FALSE); else S-top+; S-elemS-top=e; return(TRUE); int Pop(Stack_float*S,float*x)/出栈 if(S-top=-1) return(FALSE); else *x=S-elemS-top; S-top-; return(TRUE); int GetTop(Stack_float*S,float*x)/ 取栈顶 if(S-top=-1) return(FALSE); else *x=S-elemS-top; return(TRUE); float GetTop(Stack_float S) float x; GetTop(&S,&x); return x;void ClearStack(Stack_float*S)/清空栈 if(S-top!=-1) S-top=-1;/*一些函数*/ char a7= +,-,*,/,(,), =; char p77= /优先权集合 , , , , , ,=48&ch=57) return(TRUE); else return(FALSE); bool Inc(char ch)/判断字符 if(ch=+|ch=-|ch=*|ch=/|ch=(|ch=)|ch=) return (TRUE); else return(FALSE); float GetNumber(char*ch)/转化数码 return (*ch-48);float Execute(float a,char op,float b) switch(op) case+:return(a+b);break; case-:return(a-b);break; case*:return(a*b);break; case/:return(a/b);break; default:cout不能运算;break; char Compare(char x,char ch) int i,j,k; for(i=0;i7;i+) if(x=ai) j=i; if(ch=ai) k=i; return pjk;Stack_char TA;Stack_float TB;void Caculate() InitStack(&TA); InitStack(&TB); Push(&TA,=); cout请输入一个表达式串（以=结束）endl; char ch; int w=0,q=0,y=0,z=0,m=0;float n=0,v,a,b;char op; ch=getchar(); if(!Ins(ch) if(ch=() z=1; else if(ch=-) w=1;ch=getchar();/记录输入负号 else cout您输入的表达式有误，请重新输入。endl; fflush(stdin); /清理缓存 ClearStack(&TA); Caculate(); exit(1); while(ch!=|GetTop(TA)!=) if(Ins(ch) n=n*10+GetNumber(&ch); q=1;/记录输入数字 y=0;/记录输入字符 ch=getchar(); if(Inc(ch) if(ch=() z=1; if(w=1) if(q=0) if(z=1) Push(&TA,ch); z=0; m=2;/记录负的左括号 ch=getchar(); continue; else if(ch=-) w=0;ch=getchar(); else cout您输入的表达式有误，请重新输入。endl; fflush(stdin); /清理缓存 ClearStack(&TA); Caculate(); exit(1); else coutwwendl;n=-n;w=0; if(m=2)n=-n;m-;coutmmendl; if(q=1) Push(&TB,n); n=0; q=0; if(y=1) if(GetTop(TA)=(&ch=-) w=1;ch=getchar(); else if(ch=() z=1;/记录左括号 else cout您输入的表达式有误，请重新输入。endl; fflush(stdin); /清理缓存 ClearStack(&TA); ClearStack(&TB); Caculate(); exit(1); if(y=0|z=1) switch(Compare(GetTop(TA),ch) case: Pop(&TA,&op); Pop(&TB,&b); Pop(&TB,&a); if(op=/&b=0) cout您输入的表达式有误，请重新输入。endl; fflush(stdin); /清理缓存 ClearStack(&TA); ClearStack(&TB); Caculate(); exit(1); v=Execute(a,op,b); if(m=1)v=-v;m=0; Push(&TB,v); break; case=: Pop(&TA,&op); ch=getchar(); break; case: cout括号不匹配，请重新输入。endl; fflush(stdin); /清理缓存 ClearStack(&TA); ClearStack(&TB); Caculate(); exit(1); if(!Inc(ch)&!Ins(ch) cout您输入的表达式有误，请重新输入。endl; fflush(stdin); /清理缓存 ClearStack(&TA); ClearStack(&TB); Caculate(); exit(1); v=GetTop(TB); coutv=48&chtop=-1; 5.进栈（字符栈）int Push(Stack_char *S,char x) if(S-top=Stack_Size-1) return (FALSE); S-top+; S-elemS-top=x;return (TRUE); 6.出栈（字符栈） int Pop(Stack_char*S,char*x)/ if(S-top=-1) return(FALSE); else *x=S-elemS-top; S-top-; return(TRUE); 7.取栈顶（字符栈）int GetTop(Stack_char*S,char*x) if(S-top=-1) return(FALSE); else *x=S-elemS-top; return(TRUE); char GetTop(Stack_char S) char x; GetTop(&S,&x); return x; 8.清空栈（字符栈） void ClearStack(Stack_char*S) if(S-top!=-1) S-top=-1;9. 建立数字栈#define Stack_Float 30 typedef struct float elemStack_Float; int top;Stack_float;10. 初始化（数字栈）void InitStack(Stack_float*S) S-top=-1;11. 进栈（数字栈）int Push(Stack_float*S,float e) if(S-top=Stack_Float-1) return(FALSE); else S-top+; S-elemS-top=e; return(TRUE); 12. 出栈（数字栈）int Pop(Stack_float*S,float*x) if(S-top=-1) return(FALSE); else *x=S-elemS-top; S-top-; return(TRUE); 13.取栈顶（数字栈）int GetTop(Stack_float*S,float*x) if(S-top=-1) return(FALSE); else *x=S-elemS-top; return(TRUE); float GetTop(Stack_float S) float x; GetTop(&S,&x); return x; 14.清空栈（数字栈） void ClearStack(Stack_float*S) if(S-top!=-1) S-top=-1; 15.转化数码 float GetNumber(char*ch) return (*ch-48); 16.运算关系的实行float Execute(float a,char op,float b) switch(op) case+:return(a+b);break; case-:return(a-b);break; case*:return(a*b);break; case/:return(a/b);break; defaul