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

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

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

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

4、序清单：#include <iostream>#include <cmath>#include <stack>#include <string>using namespace std;string transform(string str)/转换为后缀表达式stack<char> ope;int i;string exp=""for(i=0;i<int(str.size();i+)if(stri='.'|isdigit(stri)exp+=stri;else if(stri='+

5、9;|stri='-')int j=i-1;if(isdigit(strj)exp+=" "/每个数字的后面都加一个空格加以区分if(ope.empty()|ope.top()='(')ope.push(stri);elsewhile(!ope.empty()&&ope.top()!='(')exp+=ope.top();ope.pop();ope.push(stri);elseif(ope.empty()|ope.top()='(')ope.push(stri);elsewhile(!ope.

6、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(!ope.em

7、pty()&&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()!='('&

8、amp;&ope.top()!='+'&&ope.top()!='-')exp+=ope.top();ope.pop();ope.push(stri);/else if(stri='')int j=i-1;if(strj!=')')exp+=" "ope.push(stri);else if(stri='(')ope.push(stri);else if(stri=')')exp+=" "while(ope.top()!='(&

9、#39;)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(string str)/检查输入的表达式是否有误if(isdigit(strstr.length()-1)!=0|strstr.le

10、ngth()-1=')')&&(isdigit(str0)!=0|str0='+'|str0='-'|str0='(')int i;for(i=0;i<int(str.length();i+)if(stri='/'|stri='%'|stri='*'|stri='') int a=i+1; if(stra='/'|stra='*'|stra='%'|stra=')'|stra=

11、9;.')cout<<"表达式有错误"<<endl; return 1; break;else if(stri='+'|stri='-')int a=i+1;if(stra='/'|stra='*'|stra='%'|stra=')'|stra='.'|stra='')cout<<"表达式有错误"<<endl;return 1;break;else if(isdigit(s

12、tri)!=0)int a=i+1;if(stra='(')cout<<"表达式有错误"<<endl;return 1;break;else if(isdigit(stri)=0&&stri!='+'&&stri!='-'&&stri!='*'&&stri!='/'&&stri!=''&&stri!='%'&&stri!='

13、;('&&stri!=')'&&stri!='.')cout<<"表达式有错误"<<endl;return 1;break;else if(stri='.')int a=i+1;if(isdigit(stra)=0)cout<<"表达式有错误"<<endl; return 1; break;while(i=str.length()-1)cout<<"表达式正确"<<endl;r

14、eturn 2;break;elsecout<<"表达式有错误"<<endl;return 1;double calculate(string exp)stack<double> number;double digit;string str=""for(int i=0;i<int(exp.length();i+)if(isdigit(expi)|expi='.')str=str+expi;else if(expi=' ') const char*p=str.c_str();digi

15、t=atof(p);/string转换为doublenumber.push(digit);str=""else/(expi!='.'&&expi!=' '&&!isdigit(expi)&&number.size()>=2) double result;double right;double left;right=number.top();number.pop();left=number.top();number.pop();switch(expi)case '+':res

16、ult=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;

17、case '':result=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<<"请输入表达式

18、，最后不加等号"<<endl; cin>>str;string exp;int a=examine(str);if(a=2)exp=transform(str); cout<<str<<"="<<calculate(exp)<<endl;cout<<"继续运算请输入Y，否则按任意键退出"<<endl;char ch;cin>>ch;if(ch='Y'|ch='y')x=1;elsex=2;system("pause");六、运行结果：这个是一开始运行的情况。输入完表达式后会判断表达式是否正确，如果