算术表达式求值

1、第 1 页算术表达式求值演示、需求分析(1) 输入的形式：语法正确的、不含变量的字符序列形式的整数表达式 输入值的范围：整数的范围是 (2 15-l)(2 15-1)运算符： +，-，*，/ ，(，)表达式结束运算符 #(2) 输出的形式：范围是 (2 15-l)(2 15-1) 的整数(3) 程序所能达到的功能：实现对算术四则混合运算表达式的求值 ; 程序执行命令包括：1) Calculate计算表达式的值2) Exit退出(4) 测试数据1) 82) 2-2-2-3;3) 4+26/12-2*7;4) 18-3*7-15/6;" 提示信息 " 之 ( 滤去输入中5) 2

2、*(6+2*(3+6*(6+6) ；演示程序以用户与计算机交互方式执行，即在计算机终端上显示 后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据 的 非法字符 ) 和运算结果显示在其后。、概要设计(1) 为实现上述程序功能需要的抽象数据类型：1) 栈的抽象数据类型：ADT Stack数据对象：D= |ai|ai elemset, i=1,2,n , n0 数据关系：R1=<ai-1 , ai >| ai-1 , ai D, i=2，n 基本操作：InitStack() 操作结果：构造一个空栈。GetTop(S， &e) 初始条件：栈 S 已存在且非空。操作结果：

3、用e返回S的栈顶元素。Push(&S ， e)初始条件：栈S已存在。操作结果：插入元素 e 为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并且用e返回其值。ADT Stack2) 系统中子程序及功能要求：Precede(char c1,char c2):比较两个字符的优先级，并返回比较结果。Operate(SElemType a,char op,SElemType b):函数进行四则运算，并返回运算结果。judge(char op):判断是否为运算符。EvaluateExpression() ：进行四则混合运算，并返回运算结

4、果。(2) 本次程序设计中一共有三个模块，一个是由主函数构成的模块，一个是由各个子 功能函数构成的栈模块 , 第三个是由运算等函数构成的运算模块。(3) 主模块可以对子模块中的函数进行调用，但子模块不能对主模块中的内容进行调 用；子模块中的函数可相互调用。具体函数调用关系如下：main 调用 EvaluateExpression()EvaluateExpression() 调 用 Precede 、 Operate 、 judge 、 InitStack()GetTop、 Push 、Pop。三、详细设计typedef int Status;typedef int SEIemType; /元素

5、类型typedef structSEIemType *base;SEIemType *top;int stacksize;SqStack; /结点类型和指针类型第 3页(3) 栈的基本操作定义如下： Status InitStack(SqStack *S);/ 构造一个空栈 SStatus GetTop(SqStack S)/若栈不空，则返回栈顶元素，否则返回ERRORStatus Push(SqStack *S,SElemType e);/插入 e 为新的栈顶元素Status Pop(SqStack *S,SElemType *e);/若栈不空，贝U删除S的栈顶元素，用e返回其值，返回0K否

6、则返回ERROR(4) 系统中子程序的基本操作定义：Char Precede(char c1,char c2);/进行运算符的优先级比较，并返回比较结果。SElemType Operate(SElemType a,char op,SElemType b);/进行两个整数数的四则运算，并返回运算结果。Status judge(char op)/判断是否为运算符。SElemType EvaluateExpression()/进行四则混合运算，并返回运算结果。(5) 部分基本操作的源程序如下：Status Push(SqStack *S,SElemType e)*(S->top)+=e;ret

7、urn OK; /插入元素 e 为新的栈顶元素Status Pop(SqStack *S,SElemType *e)if(S->top=S->base)return ERROR; / 若栈为空，返回 ERROR*e=*(-(S->top);return OK; /栈不为空，删除S的栈顶元素，用e返回其值，并返回OK char Precede(char a,char b)/根据课本P53,表3-1算符间优先关系编写程序实现算符间的优先级比较SElemType r;switch(a)case'+':case'-': /+', '-&

8、#39;运算符优先级相同， 故放在一起进行比较if(b='*'|b='/'|b='(')r='<' else r='>'/ '运算符优先级相同，故放在一起进行比较break;case'*': /case'/':if(b='(') r='<' else r='>'case'(':if(b='#')printf("nLogicbracket！");retur

9、n(0')break;expression error ！There is no right/ 逻辑错误，只有左括号，缺少右括号else if(b=')')r='=' else r='<'break; case')':if(b='(') printf("nMatching errors in brackets! "); return( 0' ) ; / 括号匹配错误else r='>'break;case'#':if(b=')&

10、#39;)printf("nLogic expression error!There is no left bracket!");return( 0' ) ; / 逻辑错误，只有右括号，缺少左括号else if(b='#')r='=' else r='<'break; return(r);SElemType Operate(SElemType a,char op,SElemType b) / 进行算数运算 op 为运算符switch(op)case'+':return(a+b);break;cas

11、e'-':return(a-b);break;case'*':return(a*b);break;case'/':if(b!=0) return(a/b);elseprintf("n0 can not do Divisor");return( 0' ) ;SElemType EvaluateExpression()SqStack OPTR,OPND;声明各个变量初始化创建运算符栈'#'所对的整型量进运算符栈创建操作数栈SElemType a,b,e,sum,theta,x; char c; / sum=

12、0; / InitStack(&OPTR);/Push(&OPTR,('#'-'0');/InitStack(&OPND);/c=getchar();while(c!='#'|GetTop(OPTR)!=('#'-'0') if(!judge(c)while(c>='0'&&c<='9')sum=(sum*10+(c-'0');c=getchar();Push(&OPND,sum); / 不是运算符进栈sum

13、=0;elseswitch(Precede(GetTop(OPTR)+'0'),c)case'<': / 栈顶元素优先级低Push(&OPTR,(c-'0');c=getchar();break;case'=': /托括号并接受下一个字符Pop(&OPTR,&x);c=getchar();break;case'>': /栈顶元素优先级高，退栈并将运算结果进栈Pop(&OPTR,&theta);Pop(&OPND,&b);Pop(&OPND,

14、&a);e=Operate(a,(theta+'0'),b);Push(&OPND,e);break;case'0':Push(&OPND,0);c='#' / 逻辑错误， 0 进栈 ，并结束运算 break;return (GetTop(OPND);四、调试分析(1) 在调试过程中遇到的两大问题：1)如何进行超过一位的数的存储 原因分析：按照预想的想法，对表达式进行实际操作时发现，当输入超过一 位的数时，在程序的运行过程中，只进行了数的最低位的运算： 例如 1+15#，由于系统将 15 进行两个字符处理后仍按两个字符进

15、行进栈存储，使得实际运行结果为 6，显然是错误的 解决方案：对操作数的进栈存储程序进行优化，使其能将多位数视为单个字 符进行进栈存储 具体程序由原来的 if(!judge(c)Push(&OPND,sum); c=getchar();优化如下：if(!judge(c)while(c>='0'&&c<='9')sum=(sum*10+(c-'0'); c=getchar();Push(&OPND,sum);sum=0;当然，在声明变量时已经对sum进行了初始化：sum=02) 如何进行数的转换原因分析：最

16、初对站内元素类型的定义为 char ，但进行运算时发现其运算 或则是运算的结果均不能超过 128，这是由 char 类型本身的性 决定的解决方案：将栈内元素的类型定义为 int ，无论是运算符，还是数字字符，在 进栈之前都进行( - 0')操作，对于已经整型化的数字字符在进 行其后的运算或进栈时不用在进行数的转换， 但是由于个人程序的 编制要求，运算符在出栈时仍需要进行相关的操作( +0')，即将 运算符重新字符化(2) 实验总结：经过本次课程设计，我深刻地感受到数据结构的重要性， 数据结构是计算机专 业很重要的一门课程，也是必须要熟练掌握的课程。本次课程设计， 我选择的项目是

17、算术表达式的求值 , 它的实现主要是栈的应用， 所 以，通过这次的实习，特别加深了我对栈这一数据类型的理解，在实际应用中也比以 前更加得心应手。另外，在本次的程序设计中，我还切身的体会到不同的类型的数据 的实际意义，一个程序可能会因为元素类型定义不当而永远得不到预期得结果。在本 次课程设计当中，在做完需求分析和概要设计后，我又进行了详细设计，经过一番分 析之后，我首先对自己需要的模块进行了详细的编写，在确保各个功能模块的可行性 以及正确性后，进行了与主函数、函数与函数之间的连接，调试后又进行了数据测试， 并对结果进行分析，并做了多次改进和调试。在调试的过程中，我深刻的认识到，对 于计算机专业的

18、学生来说，应更好的掌握应用软件的分析方法和调试方法，应该能够 熟练运用高级语言的程序调试器 DEBUG 调试程序。经过这次课程设计，我真的学到了很多东西，一方面巩固和加深了我对数据结构 这门课程的理解，在实际应用方面也较以前有了很大的进步。在设计的过程难免会遇 到很多问题，此时千万不要气馁，解决问题的方法可以有很多，可以通过网络、书籍 等方法进行需求信息的查找，寻求他人帮助自然也是一个好办法，但我个人觉得更多 的应该是自己独立思考，才能达到提升自己分析问题、解决问题的能力作用。此次课程设计将我们所学的理论知识和实际运用进行了一次很好的连接，有利于 加强我们用理论知识来分析实际问题的能力，进而加

19、强了我们对知识认识的实践度， 巩固了我们的理论知识，深化了对知识的认识，并为走向社会打下一个良好的基础。 当然在这次课程设计中除了程序本身的问题外，我也发现了很多别的问题，发现自己 的数据结构基础还不是很扎实，还有很多需要改进和努力的地方，在今后的学习中， 我一定会努力地去巩固我的基础知识，并在实践中加强应用。在这次课程设计中我遇到不少问题和麻烦，在老师们和同学们的帮助和提示下， 才能够如此顺利地完成了设计，在次对老师们表示真诚的感谢！五、用户使用说明(1) 进入程序运行界面后，出现欢迎语并显示执行命令项(2) 用户按程序提示进行命令项的选择(3) 按提示要求输入待运算的表达式 ( 必须输入合

20、法的，不含变量并且以 #结束的表达第 9 页式）（4）系统输出运算结果，并重复（1）（3）的操作，需要退出时，可在（2）中进行 选择六、测试结果（1）输入：8#输出：The value of expression: 8运行结果截图为WeIcome to th巴 expression fot* the vlue of smll procedure? I l.To calculate the expression2 . e x itPlease enter youl* choicePlease enter arithmet ic express ions to the end of the tt:

21、SttiThe ualue Qf express ion ：SlTo calculate the expressionPlea&e enter your choice =(2) 输入：2-2-2-3#输出：The value of expression : -5运行结果截图为第13页2 exitPlease七咅¥ your choice：1Please enter ar it hmet ic express ions to the end of the tt:8ttThe value of expression:81. To calculate the expression2

22、-exitPlease enter youti* choice =1Please enter arithnetic expressions to the end of the tt =2-2-2-3ITThe value oF express ion：-5tTo calcuLate the express ion2. exitEntE於 atiuF choixE；(3) 输入：4+26/12-2*7#输出：The value of expression: -8运行结果截图为2 exitPlease enterchoice:1Please enter- arithmet ic express i

23、oto tlie end of tlie tt:2-2-2-3Uhe ualue of express ion:-51. .To calculate the expesiDn2 -exitPlease enter your choice：1Please entei arithmet ic express ions to the end of the tt:4+26zl2-2*7tthe ualue of express ion：-81_To calculate the expression2exitPlease entee vour choice = 输入：18-3*7-15/6#输出：The

24、 value of expression: -5运行结果截图为2.exitPlease enter your choice：1Please enter arithnetic expressionstotheend ofthett：4+26/12-2*7«The value of express ion-8Please enter your choice：1Please enter arithmetic expressionstheend oftheThe value of expression：-51 .To calculate the expression2. exitPlease

25、 entei* your clio ice -(5) 输入：2*(6+2*(3+6*(6+6)#输出：The value of expression: 312运行结果截图为2.exitPlease enter youti* cha ice : 1Please enter ar it hmetic expressions to the end of the It：18-3*715/611The value of expression J-5calculate the express ion2-exitPlease enter vauF clia ice -1Please enter arithe

26、tic expressions to the end of the 4 2*<6+2*C3+6*<6+6>>>#The value of expression：3121_To calculate the express ion2.exitPI俭办s儘 entet-jrouF 右hujxE：七、附录源代码#include <stdio.h>#include <stdlib.h>#define STACK_INIT_SIZE 100#define MAX100#define TURE 1#define ERROR 0#define OK 1#d

27、efine FALSE 0#define OVERFLOW -2typedef int SElemType;typedef int Status;typedef structSElemType *base;/* 栈的存储空间初始分配量 */*元素类型 */* 字符存储空间分配量 */SElemType *top;/*栈顶指针 */int stacksize;/*当前已分配的存储空间，以元素为单位 */SqStack;/*结点类型和指针类型 */*在构造之前和销毁之后，base的值为NULL*/Status InitStack(SqStack *S)/*构造一个空栈 S*/S->base=

28、(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!(S->base)exit(OVERFLOW); /*存储空间分配失败 */ S->top=S->base;S->stacksize=STACK_INIT_SIZE;return OK;Status GetTop(SqStack S)if(S.top>S.base)return(*(S.top-1); /* 栈不为空，返回栈顶元素 */elsereturn ERROR;/* 栈为空，返回 ERROR*/Status Push(SqStack *S,

29、SElemType e) /* 插入元素 e*/*(S->top)+=e;return OK;/* 插入成功，返回 OK*/Status Pop(SqStack *S,SElemType *e) /* 删除栈顶元素，并用 e 返回*/ /* 栈为空，返回 ERROR*/* 栈不为空，删除栈顶元素，返回OK*/if(S->top=S->base) return ERROR;*e=*(-(S->top);return OK;Status judge(char op) /* 判断是否为运算符 */switch(op)case'+':case'-'

30、;:case'*':case'/':case'(':case')':case'#':return TURE;/* 是运算符，返回 TURE*/default:return FALSE;/* 不是运算符，返回 ERROR*/SElemType Operate(SElemType a,char op,SElemType b) /*对两个整型数进行算术运算op为运算符*/switch(op)case'+':return(a+b);/*若为' +', 返回进行加法运算的运算结果 */brea

31、k;case'-':return(a-b);/*若为' -', 返回进行减法运算的运算结果 */break;case'*':return(a*b);/* 若为' *', 返回进行乘法运算的运算结果 */ break;case'/':if(b!=0)return(a/b);/* 若为'/',且除数不为 0 返回进行除法运算的运算结果*/elseprintf("n0 can not do Divisor"); /* 除数为 0，提示错误 */exit(0);char Precede(

32、char a,char b) /* 比较运算符的优先级 */SElemType r;switch(a)case'+':/* '+','-'运算符的优先级相同，故放在/* '* ','/'运算符的优先级相同，故放在case'-':起进行比较 */if(b='*'|b='/'|b='(') r='<'else r='>'break;case'*':case'/':起进行比较 */i

33、f(b='(') r='<'第 17 页break 八 case-?宀pinff(-VILOgic expression error 一 There is no righf bracked崩#>沛)n皿叶战4n®eMnt4nrefuln(Q)八e-se宀if(bHHy)几J1-e-se rHAr芒 2break 八=h(bHHd宀prinmvIMaohing errors in brackets-) -* 战血目碍 *一refuln(Q)八e-se rHvrbreak 八casett.rif(bHy)宀pinff(-VILOgic expr

34、ession error一 There is no -eff bracked) 、*® w8曰辑错误，只有右括号，缺少左括号 */return('0');elseif(b='#')r='='/* 运算结束标志 */else r='<'break;return(r);/* 返回比较结果 */SElemType EvaluateExpression()/* 算术表达式求值的算符优先级运算 */SqStack OPTR,OPND;SElemType a,b,e,m,n,sum,theta,x;char c;/* 声明函数

35、内变量的类型 */sum=0;InitStack(&OPTR);/* 建立运算符栈 */Push(&OPTR,('#'-'0');/* '#'所对的整型量进运算符栈 */InitStack(&OPND);/* 建立操作数栈 */c=getchar();while(c!='#'|GetTop(OPTR)!=('#'-'0')if(!judge(c) while(c>='0'&&c<='9')第 21 页sum=(sum*10+(c-'0');c=getchar();Push(&OPND,sum)