《带括号算术表达式的计算》实验报告.docx

1、带括号算术表达式的计算实验报告四川大学数据结构与算法分析实验报告实验名称 ：带括号的算术表达式求值*_*_学 院 ：_软件学院_专 业 ：_软件工程_* * *_*_学 号 ：_*_班 级 ：_5 班_日 期 ：_2014年10月24日_一、实验题目:带括号的算术表达式求值二、实验目的和要求:采用算符优先数算法,能正确求值表达式;熟练掌握栈的应用;熟练掌握计算机系统的基本操作方法,了解如何编辑、编译、链接和运行一个C程序;上机调试程序,掌握查错、排错使程序能正确运行。三、实验的环境:硬件环境:联想 笔记本电脑软件环境:操作系统: windows 7 旗舰版编译软件:Visual C+ 6.0四

2、、算法描述:程序框图文字解释:1.用户从键盘读入算术中缀表达式，以”=”结尾;2.程序判断用户输入表达式是否正确;3.若表达式正确，则用栈计算算术表达式;4.打印输出计算过程和最终结果;5.程序询问用户是否继续计算;6.若继续，则执行第1步;若否定，则退出程序7.若表达式错误，则打印错误信息，提示用户重新输入8.返回第1步;函数及结构说明:结构体:1) 存储算数表达式的单链表:struct Expression char sign;struct Expression *next;2) 操作符和操作数栈:typedef struct char *top; char *bottom; int st

3、ack_size; Stack;构造函数:1) 栈相关操作函数:初始化空栈 int StackCreate(Stack *s);入栈操作 int PUSH(Stack *s, char c);出栈操作 int POP(Stack *s, char c);获取栈顶元素 char GetTop(Stack *s);2) 计算相关操作函数:利用栈计算算术表达式 int Calculate(struct Expression *exp);子式的值的计算 int Count(char num1, char sign, char num2);判断字符是否为运算符 int IsOpOrNum(char c)

4、;判断运算符优先级 char JudgeLevel(char c1, char c2);判断表达式正确性 int IsExpresiion(struct Expression *exp);输出计算结果 void PrintResult(struct Expression *exp,int result);3) 算术表达式输入函数:键盘读入存于单链表 struct Expression *GetExp();符号2构造操作符优先级表符号1比较+-*/()=(#)+-*/(=(#)=五、源程序清单见附录六、运行结果测试表本次测试采用用户从键盘输入算数表达式，共进行16组测试序号测试功能测试内容输入项

5、预期输出实际输出结果1基本计算操作单括号运算2*(3+4)+5*3=2929通过2基本计算操作多括号运算3+(4+3)*6)/3=1717通过3基本计算操作不能除整运算6*(2+(3/2)=2118有误差4基本计算操作不能除整运算(1+2+3)/4=1.51有误差5式子正误判断括号不匹配1+(1+3*2=输出错误信息输出错误信息通过6式子正误判断计算符多余1+2*3+6=输出错误信息输出错误信息通过7式子正误判断含非计算符x+y*z+w=输出错误信息输出错误信息通过8式子正误判断未输入”=”1+2*377通过9容错能力除数为02+3/0=输出除数为0输出除数为0通过10容错能力自动去空格1+

6、2 * ( 3 + 4)=1515通过11容错能力“=”输为”#”2*(3+2)#1010通过12拓展功能多位正数计算10*(2+13)=150输出错误信息未通过13拓展功能负数计算4+3*(-4)+5=-3输出错误信息未通过15拓展功能小数计算1+10*0.1/2=6输出错误信息未通过16全体测试最终测试2 *(4 (3+3) )+3 #-1-1通过部分运行截图基本计算操作不能整除运算(3)多括号运算(2)式子正误判断容错能力全体测试七、实验运行情况分析优点:用户输入格式较为自由。增添了一些能想到的容错系统，如用户未输入”=”，或是用户将”=”错输成”#”，或是用户在字符间输入空格，程序都会

7、智能识别出正确的算数表达式，计算正确答案。防错报错系统较为完善。多方面考虑输入方面的错误，如括号不匹配、计算符少输多输、输入非计算符等方面均考虑，并提示用户错误信息，便于用户检查输入状况。存储方式较为规范。采用单链表存储用户输入的算术表达式，更加清晰简单,头结点存储表达式中符号的个数，方便在必要的时候统计对照最终结果的正确性。缺点:只能实现数字之间的四则运算，不能实现其他算数功能如平方，开方等。仅仅局限于个位数之间的运算，无法运算两位数或两位以上数字的运算。计算数字只能为0-9的整数，无法对负数或者小数进行计算。在除法中若遇到无法除尽的结果，只能保留其整数部分，造成最终结果跟预期结果存在误差由

8、于控制台系统的限制，与用户交互性较差，界面太过简单单调。感受:通过本次“带括号算数表达式的计算”实验，我不光复习了之前学习的单链表的相关知识并加以采用，而且还巩固了有关于栈的相关操作；在实现题目要求基本功能的基础上，还增加拓展了一些内容。在为期两周的实验中，从刚开始的整理思路，到接下里的编写代码，到最后的填写实验报告，都是我自己一步步完成。唯独可惜的是，由于知识掌握不够全面，导致只能实现最基本的功能，无法进行进一步的扩展和完善，致使用户输入一些运算式未得到预期的结构，这是比较遗憾的方面。附录(源程序代码)/*实验一：带括号的算数表达式求值*实现：栈*语言：C*作者：马健*/#include #

9、include #include #define STACK_SIZE_FIRST 100 /栈的初始空间大小#define STACK_SIZE_INCREASE 20 /栈的增加空间大小/*-算术表达式单链表-*/struct Expression char sign; struct Expression *next;/*-操作符和操作数栈-*/ typedef struct char *top; char *bottom; int stack_size; /栈的空间大小Stack;struct Expression *GetExp(); /键盘读入表达式存入单链表/*-栈相关的操作函数-

10、*/int StackCreate(Stack *s); /初始化一个空栈函数int PUSH(Stack *s, char c); /入栈函数int POP(Stack *s, char c); /出栈函数char GetTop(Stack *s); /取出栈顶元素/*-计算相关操作函数-*/int Calculate(struct Expression *exp); /带括号的算数表达式计算函数int Count(char num1, char sign, char num2); /两个数的计算int IsOpOrNum(char c); /判断一个字符是不是运算符char JudgeLe

11、vel(char c1, char c2); /判断两运算符优先级void PrintResult(struct Expression *exp,int result); /打印最终结果int IsExpresiion(struct Expression *exp); /判断是否为正确的算术表达式void main() struct Expression *head; int Result = 0; /定义最终计算结果 int temp = 0; /定义循环参数 char select; while(temp = 0) head = GetExp(); /创建算术表达式单链表 if(IsExp

12、resiion(head) = 0 | head = NULL) /算术表达式错误，重新输入 printf(算术表达式错误，请认真检查并重新输入); getch(); system(cls); else Result = Calculate(head); /计算算术表达式 PrintResult(head,Result); /输出最终计算结果 printf(是否继续计算? 是(y) 否(n)n); /是否继续 select = getch(); if(select = n | select = N) temp = 1; else system(cls); /读入算术表达式并存储于链表struc

13、t Expression *GetExp() printf(t带括号的算术表达式求值n); printf(请输入需要计算的算数表达式:(以=结尾)n); char c; int number = 0; struct Expression *head = NULL,*p1,*p2,*first = NULL; /定义指针变量 head = (struct Expression *)malloc(sizeof(struct Expression); while(c = getchar() != n) if(c != ) /若出现空格,自动删除 p1 = (struct Expression *)m

14、alloc(sizeof(struct Expression); if(c = =) c = #; p1-sign = c; if(first = NULL) first = p1; else p2-next = p1; p2 = p1; number+; if(p2-sign != #) /若未输入=,则自动补齐 p1 = (struct Expression *)malloc(sizeof(struct Expression); p1-sign = #; p2-next = p1; p2 = p1; number+; head-next = first; head-sign = numbe

15、r + 0; /头结点存储表达式中字符个数 if(head-next != NULL) p2-next = NULL; return head;/创建空栈int StackCreate(Stack *s) s-bottom = (char *)malloc(STACK_SIZE_FIRST * sizeof(char); if (s-bottom = NULL) printf(栈初始化失败!n); exit(0); else s-top = s-bottom; s-stack_size = STACK_SIZE_FIRST; return 1; /入栈int PUSH(Stack *s, ch

16、ar c) if(s-top - s-bottom = STACK_SIZE_FIRST) s-bottom = (char *)realloc(s-bottom,(STACK_SIZE_FIRST+STACK_SIZE_INCREASE) * sizeof(char); if(s-bottom = NULL) printf(增加栈空间失败!n); exit(0); s-stack_size = s-stack_size + STACK_SIZE_INCREASE; *(s-top) = c; /赋值需要入栈的元素 s-top +; /栈顶指针上移 return 1;/出栈int POP(St

17、ack *s, char c) if(s-top = s-bottom) printf(栈为空!出栈失败!n); exit(0); else c = *(s-top); s-top -; return 1;/获取栈顶元素char GetTop(Stack *s) char c; if(s-top = s-bottom) printf(栈空，无法获取栈顶元素!n); else c = * (s-top - 1); return c;/计算算术表达式int Calculate(struct Expression *exp) exp = exp-next; /取表达式开始 char OpSign =

18、 ; /存储出栈操作符 char NumSign1= ,NumSign2= ; /存储出栈数字符 char result; /存储部分运算结果 char temp = ; /接受出栈操作数 Stack s_operator, s_number; StackCreate(&s_operator); /创建操作符栈 StackCreate(&s_number); /创建数字栈 PUSH(&s_operator,#); /先在操作栈底压入# printf(n计算过程如下:n); while(exp-sign != # | GetTop(&s_operator) != #) /操作数存入操作数栈 if

19、(IsOpOrNum(exp-sign) = 0) PUSH(&s_number,exp-sign); exp = exp-next; /操作符存入操作符栈 else if(IsOpOrNum(exp-sign) = 1) OpSign = GetTop(&s_operator); /获取栈顶元素 switch(JudgeLevel(OpSign,exp-sign) /比较栈顶元素和运算符的优先级 case sign); exp = exp-next;break; case =:POP(&s_operator,OpSign); exp = exp-next; break; case : POP

20、(&s_operator,OpSign); NumSign1 = GetTop(&s_number); POP(&s_number,temp); NumSign2 = GetTop(&s_number); POP(&s_number,temp); result = Count(NumSign2,OpSign,NumSign1); PUSH(&s_number,result); break; default: break; result = GetTop(&s_number); /获取最终计算结果 return result - 0; /判断两个运算符的优先级char JudgeLevel(ch

21、ar c1, char c2) switch(c1) case +: switch(c2) case *: case /: case (: return ; break; break; case -: switch(c2) case *: case /: case (: return ; break; break; case *: switch(c2) case (: return ; break; break; case /: switch(c2) case (: return ; break; break; case (: switch(c2) case ): return =; break; default: return ; break; default: return ; break; break; case #: switch(c2) case #: return =; break; default: return ; break; break; default: return next; while(exp != NULL) if( exp-sign = #) exp-sign = =; printf( %c