四川大学数据结构与算法分析课程设计报告 带括号的算术表达式

1、数据结构与算法分析课程设计报告课题名称： 带括号的算数表达式求值 课题设计人（学号）： 指导教师： 朱宏评阅成绩： 评阅意见： 提交报告时间：2014 年 12月 9日带括号的算数表达式求值计算机类 专业学生 指导老师 朱宏 摘要 在平时的生活中，我们可以解决一些简单的算术表达式，如果当我们遇到一些式子较为冗长，运算比较复杂的算术表达式时，我们都会选择计算器。那么，计算器又是通过怎样的原理来进行运算的呢。本程序利用堆栈先进后出的特点，采用操作数和操作符两个堆栈，实现由中缀表达式到后缀表达式的转换并求值的过程。带括号的算术表达式的求值是堆栈的一个典型的应用实例。 关键词：计算器 堆栈 C+一、实

2、验名称:带括号的算术表达式求值二、实验的目的和要求:1.采用算符优先数算法,能正确求值表达式;2.熟练掌握栈的应用;3.熟练掌握计算机系统的基本操作方法,了解如何编辑、编译、链接和运行一个C+程序;4.上机调试程序,掌握查错、排错使程序能正确运行。三、实验的环境：硬件环境：处理器：Inter(R) Core(TM) i7-4500U内存：8.00GB软件环境：操作系统：Windows8.1编译软件：Microsoft Visual Studio 2012四、算法描述:我设计的带有括号的算术表达式求值的程序中，运算符的优先级是这样子的：1. 先乘除，后加减2. 同级运算从左到右依次运算。3. 先

3、括号内的运算，再括号外的运算。我的设计思路是，先输入一个最后不带等于号的中缀表达式，先对表达式检查是否有错误，如果有将会输出“表达式有错误”，否则通过堆栈方法将这个中缀表达式转化为后缀表达式，然后将后缀表达式求值。开始程序输入一个表达式检查表达式是否有错误没有错误是有错转化为后缀表达式计算求值输出结果输出“表达式有错”是否继续否退出程序函数清单：transform()用于将中缀表达式转换为后缀表达式calculate()将后缀表达式进行求值examine()检查输入的表达式是否有错误main()主程序。五：源程序清单：#include #include #include #include us

4、ing namespace std;string transform(string str)/转换为后缀表达式stack ope;int i;string exp=;for(i=0;iint(str.size();i+)if(stri=.|isdigit(stri)exp+=stri;else if(stri=+|stri=-)int j=i-1;if(isdigit(strj)exp+= ;/每个数字的后面都加一个空格加以区分if(ope.empty()|ope.top()=()ope.push(stri);elsewhile(!ope.empty()&ope.top()!=()exp+=o

5、pe.top();ope.pop();ope.push(stri);elseif(ope.empty()|ope.top()=()ope.push(stri);elsewhile(!ope.empty()&ope.top()!=()exp+=ope.top();ope.pop();ope.push(stri);else if(stri=*|stri=/|stri=%) int j=i-1;if(isdigit(strj)exp+= ;if(ope.empty()|ope.top()=(|ope.top()=+|ope.top()=-) ope.push(stri); else while(!o

6、pe.empty()&ope.top()!=(&ope.top()!=+&ope.top()!=-) exp+=ope.top();ope.pop(); ope.push(stri); elseif(ope.empty()|ope.top()=(|ope.top()=+|ope.top()=-)ope.push(stri);elsewhile(!ope.empty()&ope.top()!=(&ope.top()!=+&ope.top()!=-)exp+=ope.top();ope.pop();ope.push(stri);/else if(stri=)int j=i-1;if(strj!=)

7、exp+= ;ope.push(stri);else if(stri=()ope.push(stri);else if(stri=)exp+= ;while(ope.top()!=()exp+=ope.top();ope.pop();ope.pop();elsereturn 有错误;while(!ope.empty()/遍历完表达式将堆栈中的所有运算符输出 if(isdigit(expexp.length()-1)exp=exp+ +ope.top(); ope.pop(); else exp=exp+ope.top(); ope.pop();return exp;int examine(st

8、ring str)/检查输入的表达式是否有误if(isdigit(strstr.length()-1)!=0|strstr.length()-1=)&(isdigit(str0)!=0|str0=+|str0=-|str0=()int i;for(i=0;iint(str.length();i+)if(stri=/|stri=%|stri=*|stri=) int a=i+1; if(stra=/|stra=*|stra=%|stra=)|stra=.)cout表达式有错误endl; return 1; break;else if(stri=+|stri=-)int a=i+1;if(stra

9、=/|stra=*|stra=%|stra=)|stra=.|stra=)cout表达式有错误endl;return 1;break;else if(isdigit(stri)!=0)int a=i+1;if(stra=()cout表达式有错误endl;return 1;break;else if(isdigit(stri)=0&stri!=+&stri!=-&stri!=*&stri!=/&stri!=&stri!=%&stri!=(&stri!=)&stri!=.)cout表达式有错误endl;return 1;break;else if(stri=.)int a=i+1;if(isdig

10、it(stra)=0)cout表达式有错误endl; return 1; break;while(i=str.length()-1)cout表达式正确endl;return 2;break;elsecout表达式有错误endl;return 1;double calculate(string exp)stack number;double digit;string str=;for(int i=0;i=2) double result;double right;double left;right=number.top();number.pop();left=number.top();numbe

11、r.pop();switch(expi)case +:result=left+right;number.push(result);break;case -:result=left-right;number.push(result);break;case *:result=left*right;number.push(result);break;case /:result=left/right;number.push(result);break;case %:int(result)=int(left)%int(right);number.push(result);break;case :resu

12、lt=pow(left,right);number.push(result);break;double finalresult=number.top();number.pop();return finalresult;void main()int x=1;cout计算表达式endl;cout支持加+ 减- 乘* 除/ 整数取余% 次幂 小括号()endl;while(x=1)string str;cout请输入表达式，最后不加等号str;string exp;int a=examine(str);if(a=2)exp=transform(str); coutstr=calculate(exp)

13、endl;cout继续运算请输入Y，否则按任意键退出ch;if(ch=Y|ch=y)x=1;elsex=2;system(pause);六、运行结果：这个是一开始运行的情况。输入完表达式后会判断表达式是否正确，如果正确会输出“表达式正确”，错误会输出“表达式错误”。正确的情况下会输出结果，选择是否继续计算输入y或者Y都会进行下一次运算结果仍然正确。接下来测试如果输入错误的表达式会怎么样。输入的表达式有错误，判断出错误后选择是否继续任意输入不是y或者Y的字符，退出程序。七、实验运行情况分析1.算法：定义字符串exp用来存储后缀表达式，每个数字之间间隔一个空格用以区分数字。调用堆栈ope来存放依次输入的操作符，如果输入的操作符运算优先级高于栈顶运算符，那么进栈。反之出栈直至当前运算符运算优先级高于栈顶运算符，将当前运算符进栈。如果遇到左括号“（”，直接进栈。如果遇到右括号“）”，一直出栈直到遇到左括号。将出栈的运算符依次加到exp中。调用堆栈number，用来存放后缀表达式中出现的数字。每当遇到一个操作符的时候，便取出堆栈中的两个数字放在运算符右边和左边进行计算，将计算结果继续