《算数表达式的求解课程设计报告.doc》由会员分享，可在线阅读，更多相关《算数表达式的求解课程设计报告.doc（17页珍藏版）》请在三一办公上搜索。
1、合肥学院计算机科学与技术系课程设计报告20 12 20 13 学年第 2 学期课程数据结构与算法 课程设计名称算数表达式的求解学生姓名周丽娟学号1104012013专业班级11计本3班指导教师李红20 13 年 3 月 【问题描述】（算数表达式的求解）给定一个算数表达式，通过程序求出最后的结果。【要求】1、 从键盘输入要求解的算术表达式；2、 采用栈结构进行算数表达式的求解过程；3、 能够判断算数表达式的正确与否；4、 对于错误表达式给出提示；5、 对于正确表达时给出最后的结果。1、 问题分析和任务定义有题目可知，程序要求给定一算数表达式并计算最后的结果，我们知道，在高级语言中，任何一个表达式
2、都是有操作数、运算符和界限符组成。在计算过程中，还要考虑表达式中有无括号以及左右括号之分。由于运算符有优先级的高低，因此一个算数表达是不可能总是按顺序执行。 通过以上可知，可以用栈来实现运算符的优先级完成算术表达式的求解。为实现算法的优先级，设置两个栈：一个称为操作数栈opnd，用以寄存操作数和运算结果，另一个为操作符栈optr，用以寄存运算符。该算法的基本思想是：（1） 首先置操作数栈opnd为空栈，表达式结束符“#”为操作符栈optr的栈底元素。（2）依次读入表达式中每个字符，若为操作数，则进opnd栈；若是运算符，则与optr栈的栈顶运算符比较优先级后做相应操作：若当前操作符大于optr
3、栈的栈顶，则当前操作符入栈；否则，opnd栈的栈顶元素、次栈顶元素出栈，同时optr栈的栈顶元素也出栈，形成运算，并将结果压入opnd栈，直至整个表达式求值完毕（即optr栈的栈顶元素和当前读入的字符均为“#”）。 对于算术表达式的输入，本程序采用gets()的方法读入，将运算符+，-，*，/，（，），#存储在数组中时，定义表达式求解函数，在函数中判断读入的字符，如果是运算符，将这些字符入操作符optr栈，并比较优先级，判断是否运算。若读入的字符为0到9之间的数字时，用字符相减转化为整型，然后将转化后的整型再转化为ASCII的形式压入操作数栈opnd中。2、数据结构的选择和概要设计（1） 存储
4、结构设计本程序主要采用顺序栈结构类型（Stack）来存储表达式计算中的数据。程序中需要建立两个栈，一个栈用于寄存运算符，另一个则用于寄存操作数和计算结果，故需要建立两个顺序栈结构类型。（2） 算数优先级设计 对一任意的表达式，由于表达式中运算符的优先级不同，可能会使表达式不按顺序进行计算。在本程序中定义函数Proceed（）来比较运算符的优先级，而函数中各优先级的比较主要根据以下优先级比较的表格：表1：运算符优先级运算符+-*/（）#用数字表示0123456栈内操作符的优先级3355160栈外操作符的优先级2244610 在Precede（）函数中定义两个字符型参数变量op和c，其中op表示栈
5、顶运算符，c表示当前读入运算符，对于当前运算符是否入栈，进行如下操作：比较当前运算符和栈顶运算符的优先级的大小： 1、如果当前运算符的优先级大于栈顶运算符的优先级，即opc;令函数返回值为c；令函数返回值为，此时应将栈顶运算符出栈和栈顶、次栈顶操作数出栈并进行相应的运算。 3、如果当前元素的优先级等于栈顶运算符的优先级，即op=c；令函数的返回值为=，此时界限符内的表达式已计算完毕。（3）程序模块设计 1）程序模块 本程序主要包含3个模块：主程序模块、计算模块以及顺序栈操作模块，调用关系如图所示：顺序栈操作模块计算模块主程序模块 图1：程序模块图 2）系统功能模块 本程序大致包含10个函数，其
6、中包含主函数。每个函数都有其相对应的功能实现。 操作符的输入函数 int In(char c); 运算符比较优先级函数 char Proceed(char op,char c); 进行四则运算函数 int Operate(int a,char a1,int b); 实现表达式的求值函数 int EvalExpres(void); 初始化栈函数 void InitStack(Stack *s); 入栈函数 void Push(Stack *s, int x); 出栈函数 int Pop(Stack *s); 取栈顶元素函数 int GetTop(Stack *s) ; 判栈空函数 void Em
7、pty(Stack *s); 主函数 int main() 3)函数之间主要调用的关系图 本程序主要包含10个程序，各程序之间的关系如图所示：（部分函数用以上的编号表示）Void main()Int EvalExpres(void) 图2：函数之间调用关系图 3、详细设计和编码（1）、结构体类型的定义 typedef struct int dataMAXSIZE; int top; int base; /栈底 Stack; （2） 、全局变量定义/以下为函数声明void InitStack(Stack *); /初始化栈 int Empty(Stack *); /判空栈 void Push(S
8、tack *, int ); /进栈 int Pop(Stack *);/出栈 int GetTop(Stack *); /取栈顶元素 int Operate(int ,char ,int ); / 计算结果 char Proceed(char ,char ); / 比较优先级 int In(char ); /判断输入符int EvalExpres(void); /表达式计算函数/ 定义两个栈分别存放运算符和操作数Stack StackR,StackD; （3） 、系统主要子程序的详细设计 1）、主函数模块设计int main()/主函数 int v; char ch;while(1) pri
9、ntf(t*欢迎使用算术表达式的求解的小程序*n); v = EvalExpres(); printf(t表达式的计算结果为:%d,v); printf(ntInput n to quit and ENTER run again:); do scanf(%c,&ch); if(ch = n | ch = N) exit(0); while(ch!=n); system(cls); return 0; 在主函数中，设定用户操作界面的形式，通过调用表达式求解的子函数实现算法所要实现的功能，然后通过while()循环语句控制，可以实现多次调试。 2）、计算函数模块 int Operate(int a
10、,char a1,int b) int s; int d1 = a; int d2 = b; /把字符ab变为对应数字 switch(a1) case +: s = d1+d2; break; case -: s = d2-d1;break; case *: s = d1*d2; break; case /: s = d2/d1; return (s+0); /将运算结果转化为ascii码的形式入栈， 在计算函数中，定义3个变量，表示基本运算中的变量。采用开关语句实现表达式的基本运算，将运算结果转化为ASCII的形式返回。 3）、表达式求解的函数模块 int EvalExpres(void)
11、/ 表达式求解函数 int a,b,i=0,s=0; char c80,r; InitStack(&StackR); /初始化栈 Push(&StackR,#); /将表达式起始符压入栈 InitStack(&StackD); printf( t请输入表达式并以#结束：); gets(c); while(ci!=# | GetTop(&StackR)!=#) if(!In(ci) /判断读入的字符是不是运算符 不是则进opnd栈 if(ci = 0 & ci = 9) s += ci-0; /字符的ascii相减将字符型转化为整型 while(!In(c+i) /继续判断下一个字符，若不是运算
12、符，表明为多位数，直到读取到字符为运算符为止 s*=10; s += ci-0; Push(&StackD,s+0); /将整型转化为ascii的形式入栈，使字符在栈内以ascii的形式保存，实现多位数的计算 s = 0; /初始化s，继续判断 else printf(你输入的表达式有误!n); return 0; else switch(Proceed(GetTop(&StackR),ci) /此函数用来比较读取的运算符和栈顶运算符的优先级 case : /栈顶的优先级高则出栈，并将计算结果压入栈内 r = Pop(&StackR); a = Pop(&StackD)-0; /操作数在栈内以
13、ascii的形式存储，出站后要将ascii转化为整型，然后进行运算 b = Pop(&StackD)-0; Push(&StackD,Operate(a,r,b) ; break; return (GetTop(&StackD)-0); / 将栈顶元素转化为整型的形式输出 对于表达式求解函数，在程序中主要思想是对读入的表达式进栈进行判断。若读入的是0到9之间的字符，将这些字符采用ascii相减的形式转化为整型，再入opnd栈，若读入的字符为运算符，则将运算符入栈，并比较运算符之间的优先级，看是否运算，若栈顶的运算符小于当前输入的运算符，则不需运算，只要将当前运算符入栈即可。否则，运算。运算时先
14、将optr栈的栈顶运算符和opnd栈的栈顶、次栈顶元素出栈，并将opnd栈中出栈的元素的ASCII形式转化为整型再计算，最后讲计算结果再转化为ASCII码的形式压入opnd栈中。使表达式求解函数返回值为opnd的栈顶元素。4、上级调试过程遇到问题以及解决方案 问题1、调试时没有错误，但运行时显示错误。解决方案：通过它提示的错误和警告，在判断是否为运算符的子函数中出现错误，如果为运算符时返回1，其次返回0，在返回0时没有用else，这样使得整个子函数可以返回一个有效值。 问题2、调试时程序显示没有错误，可以运行，但在运行时结果却出现错误。解决方案：把程序从头看了一遍，发现在比较优先级的函数中，优
15、先级的比较比较乱，而且部分出错，后来查了关于运算符优先级的资料，通过在纸上把各种优先级列出，解决这个错误。算法的时间复杂度 由于在主函数用到嵌套循环，故算法的时间复杂度为O（n2）。5、 测试结果及其分析 （1）、实现基本的加减乘除运算，当想要继续输入表达式时点击enter键，若要结束，点击n或N键即可，而且可实现多位数的运算。（2）、实现复杂的算术表达式（3）、错误表达式的处理6、用户使用说明 （1）本程序执行的文件为“算数表达式的求解问题”。 （2）所求表达式中都只是仅包含加、减、乘、除4种基本运算的，其中也包含括号的应用，所有的运算对象均为简单变量，要求将表达式中的数字字符转化为整型，且
16、输入表达式以“#”结束。 （3）输入表达式时，以#结束，当点击回车键时即可得到运算结果，当想继续输入表达式时，再次点击回车键即可，当想结束时，点击字母n或N。 （4）当输入错误表达式时，程序会给出相应的提醒。7、 参考文献 （1）王昆仑 、李红主编，数据结构与算法，北京：中国铁道出版社，2007年5月 （2）阮宏一 、鲁静主编，数据结构课程设计（C/C+描述），北京：电子工业出版社，2011年1月8、 附录（源程序）：#include #include #define MAXSIZE 16typedef struct int dataMAXSIZE; int top; int base; /栈
17、低 Stack; / 顺序栈的定义/以下为函数声明void InitStack(Stack *); /初始化栈 int Empty(Stack *); /判空栈 void Push(Stack *, int ); /进栈 int Pop(Stack *);/出栈 int GetTop(Stack *); /取栈顶元素 int Operate(int ,char ,int ); / 计算结果 char Proceed(char ,char ); / 比较优先级 int In(char ); /判断输入符int EvalExpres(void); /表达式计算函数/ 定义两个栈分别存放运算符和操作
18、数Stack StackR,StackD; int main()/主函数 int v; char ch;while(1) printf(t*欢迎使用算术表达式的求解的小程序*n); v = EvalExpres(); printf(t表达式的计算结果为:%d,v); printf(ntInput n to quit and ENTER run again:); do scanf(%c,&ch); if(ch = n | ch = N) exit(0); while(ch!=n); system(cls); return 0; void InitStack(Stack *s) /初始化栈 s-t
19、op = 0; s-base = 0; int Empty(Stack *s)/判断栈是否为空 if(s-top =s-base) return 1; /栈空时返回1，否则返回0 else return 0; void Push(Stack *s, int x) / 进栈 if(s-top = MAXSIZE) printf(terror!n);exit(0); else s-datas-top = x; s-top+; int Pop(Stack *s)/ 出栈 int e; if(Empty(s) printf(terror!n); exit(0); else s-top-; e = s-
20、datas-top; return e; int GetTop(Stack *s) /取栈顶元素 if(Empty(s) printf(terror!n); exit(0); else return s-datas-top-1; int EvalExpres(void) / 表达式求解函数 int a,b,i=0,s=0; char c80,r; InitStack(&StackR); Push(&StackR,#); InitStack(&StackD); printf( t请输入表达式并以#结束：); gets(c); while(ci!=# | GetTop(&StackR)!=#) i
21、f(!In(ci) /判断读入的字符不是运算符 是则进栈 if(ci = 0 & ci = 9) s += ci-0; /字符相减将字符型转化为整型 while(!In(c+i) /继续判断下一个字符，若不是运算符，表明为多位数，直到读取到字符为运算符为止 s*=10; s += ci-0; Push(&StackD,s+0); /将整型转化为ascii的形式入栈，使字符在栈内以ascii的形式保存，实现多位数的计算 s = 0; /初始化s，继续判断 else printf(t你输入的表达式有误!n); exit(0); else switch(Proceed(GetTop(&StackR)
22、,ci) /此函数用来比较读取的运算符和栈顶运算符的优先级 case : /栈顶的优先级高则出栈，并将计算结果压入栈内 r = Pop(&StackR); a = Pop(&StackD)-0; /操作数在栈内以ascii的形式存储，出站后要将ascii转化为整型，然后进行运算 b = Pop(&StackD)-0; Push(&StackD,Operate(a,r,b) ; break; return (GetTop(&StackD)-0); / 将栈顶元素转化为整型的形式输出 int In(char c) /判断C是否为运算符是返回1否则返回0 char ch7=+,-,*,/,#,(,)
23、; int i; for(i = 0; i ; break; case *: case /: case (: ch = ; break; case (: ch = ; else if(op=() /*栈顶元素为(的时候*/ switch(c) case +: case -: case *: case /: case (: ch = ; break; case (: printf(tError!括号匹配错误!n); exit(0); else if(op=#) /栈顶元素为#的时候 switch(c) case +: case -: case *: case /: case (: ch = ;
24、break; case ): printf(tError!没有左括号!n);exit(0); return ch; int Operate(int a,char a1,int b) int s; int d1 = a; int d2 = b; /把字符ab变为对应数字 switch(a1) case +: s = d1+d2; break; case -: s = d2-d1;break; case *: s = d1*d2; break; case /: if(d1!=0)s = d2/d1;else printf(t除数不可以为0!n);exit(0); return (s+0); /将运算结果转化为ascii码的形式入栈，
