《16、算数表达式的求解 (3).doc》由会员分享，可在线阅读，更多相关《16、算数表达式的求解 (3).doc（26页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计Course Design of Data Structures计算机系072姓名：杨明明 学号：06422020指导老师：张敏 2011年4月8日 目录一、设计题目 二、设计内容三、实验分析四、程序设计五、实验步骤六、调试分析七、测试、八、程序所用到的函数九、结论一、设计题目问题描述：给定一个算术表达式，通过程序求出最后的结果二、设计内容1 从键盘输入要求解的算术表达式；2 采用栈结构进行算术表达式的求解过程；3 能够判断算术表达式正确与否；4 对于错误表达式给出提示；5 对于正确的表达式给出最后的结果；三实验分析首先通过键盘输入表达式并将字符串入栈,然后按从左到右的循环判断
2、表达式的格式正确与否，当表达式的+，-，/,( )等运算符号间有两个小数点时，表达式为错误，给出错误提示并转到起始环节，然后根据给定运算顺序来做运算，有括号要先算括号里面的，计算的结果赋值到浮点型数据并输出结果。四程序设计 1.栈的建立 先建立两个不同的栈分别存放运算符号和数字，然后初始化栈。当从键盘输入符号时，首先判断输入的是否是括号，若是，则在括号标志位置1，再判断是否是负号，若为负，则再输入一位，并将负号标志位置1；输入字符不满足要求时，提示错误，重新输入；（1）、定义栈的抽象数据类型定义：ADT Stack数据对象： D=ai| aiDateType,i=1,2,，n，n=0数据关系：
3、 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、.符号输入输入符号时，根据不同的标志位，有不同的处理方法：若两运算符相连，提示错误，重新输入；当有左括号时，根据标志位判断，若未找到右括号，则提示输入错误，重新输入。4.运算符号栈中运算符号op出栈，数字栈中的数字出栈并赋值给a，b，根据给定的运算优先级（括号，*，/,+，-），在除数b不为0的条件下，调用Execute(float a,char op,float b)函数，得出结果v，压入栈中，若之前有负号（负号标志位位为1），则求其相反数v=-v，并将结果压入数字栈中，然后不断循环，直到遇到“=”停止，然后从数字栈输出结果。5、本程序包含的三个模块（1）、主程序模块； (2)、栈模块实现栈
5、抽象数据类型；（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 I
6、nitStack(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=-
7、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_flo
8、at*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(T
9、RUE); 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
10、(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(!I
