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

《数据结构与算法分析》课程设计报告课题名称：带括号的算数表达式求值课题设计人（学号）：指导教师：朱宏评阅成绩：评阅意见：提交报告时间：2014年12月9日[键入文字][键入文字][键入文字]-1-带括号的算数表达式求值计算机类专业学生指导老师朱宏[摘要]在平时的生活中，我们可以解决一些简单的算术表达式，如果当我们遇到一些式子较为冗长，运算比较复杂的算术表达式时，我们都会选择计算器。那么，计算器又是通过怎样的原理来进行运算的呢。本程序利用堆栈先进后出的特点，采用操作数和操作符两个堆栈，实现由中缀表达式到后缀表达式的转换并求值的过程。带括号的算术表达式的求值是堆栈的一个典型的应用实例。关键词：计算器堆栈C++[键入文字][键入文字][键入文字]-2-一、实验名称:带括号的算术表达式求值二、实验的目的和要求:1.采用算符优先数算法,能正确求值表达式;2.熟练掌握栈的应用;3.熟练掌握计算机系统的基本操作方法,了解如何编辑、编译、链接和运行一个C++程序;4.上机调试程序,掌握查错、排错使程序能正确运行。三、实验的环境：硬件环境：处理器：Inter(R)Core(TM)i7-4500U内存：8.00GB软件环境：操作系统：Windows8.1编译软件：MicrosoftVisualStudio2012四、算法描述:我设计的带有括号的算术表达式求值的程序中，运算符的优先级是这样子的：1.先乘除，后加减2.同级运算从左到右依次运算。3.先括号内的运算，再括号外的运算。我的设计思路是，先输入一个最后不带等于号的中缀表达式，先对表达式检查是否有错误，如果有将会输出“表达式有错误”，否则通过堆栈方法将这个中缀表达式转化为后缀表达式，然后将后缀表达式求值。[键入文字][键入文字][键入文字]-3-函数清单：transform()——用于将中缀表达式转换为后缀表达式calculate()——将后缀表达式进行求值examine()——检查输入的表达式是否有错误main()——主程序。开始程序输入一个表达式检查表达式是否有错误有错没有错误转化为后缀表达式计算求值输出结果退出程序输出“表达式有错”是否继续否是[键入文字][键入文字][键入文字]-4-五：源程序清单：#includeiostream#includecmath#includestack#includestringusingnamespacestd;stringtransform(stringstr)//转换为后缀表达式{stackcharope;inti;stringexp=;for(i=0;iint(str.size());i++){if(str[i]=='.'||isdigit(str[i])){exp+=str[i];}elseif(str[i]=='+'||str[i]=='-'){[键入文字][键入文字][键入文字]-5-intj=i-1;if(isdigit(str[j])){exp+=;//每个数字的后面都加一个空格加以区分if(ope.empty()||ope.top()=='('){ope.push(str[i]);}else{while(!ope.empty()&&ope.top()!='('){exp+=ope.top();ope.pop();}ope.push(str[i]);}}else{[键入文字][键入文字][键入文字]-6-if(ope.empty()||ope.top()=='('){ope.push(str[i]);}else{while(!ope.empty()&&ope.top()!='('){exp+=ope.top();ope.pop();}ope.push(str[i]);}}}elseif(str[i]=='*'||str[i]=='/'||str[i]=='%'){intj=i-1;if(isdigit(str[j])){[键入文字][键入文字][键入文字]-7-exp+=;if(ope.empty()||ope.top()=='('||ope.top()=='+'||ope.top()=='-'){ope.push(str[i]);}else{while(!ope.empty()&&ope.top()!='('&&ope.top()!='+'&&ope.top()!='-'){exp+=ope.top();ope.pop();}ope.push(str[i]);}}else[键入文字][键入文字][键入文字]-8-{if(ope.empty()||ope.top()=='('||ope.top()=='+'||ope.top()=='-'){ope.push(str[i]);}else{while(!ope.empty()&&ope.top()!='('&&ope.top()!='+'&&ope.top()!='-'){exp+=ope.top();ope.pop();}ope.push(str[i]);}}}[键入文字][键入文字][键入文字]-9-//}elseif(str[i]=='^'){intj=i-1;if(str[j]!=')'){exp+=;}ope.push(str[i]);}elseif(str[i]=='('){ope.push(str[i]);}elseif(str[i]==')'){exp+=;while(ope.top()!='('){[键入文字][键入文字][键入文字]-10-exp+=ope.top();ope.pop();}ope.pop();}else{return有错误;}}while(!ope.empty())//遍历完表达式将堆栈中的所有运算符输出{if(isdigit(exp[exp.length()-1])){exp=exp++ope.top();ope.pop();}else{[键入文字][键入文字][键入文字]-11-exp=exp+ope.top();ope.pop();}}returnexp;}intexamine(stringstr)//检查输入的表达式是否有误{if((isdigit(str[str.length()-1])!=0||str[str.length()-1]==')')&&(isdigit(str[0])!=0||str[0]=='+'||str[0]=='-'||str[0]=='(')){inti;for(i=0;iint(str.length());i++){if(str[i]=='/'||str[i]=='%'||str[i]=='*'||str[i]=='^'){inta=i+1;[键入文字][键入文字][键入文字]-12-if(str[a]=='/'||str[a]=='*'||str[a]=='%'||str[a]==')'||str[a]=='.'){cout表达式有错误endl;return1;break;}}elseif(str[i]=='+'||str[i]=='-'){inta=i+1;if(str[a]=='/'||str[a]=='*'||str[a]=='%'||str[a]==')'||str[a]=='.'||str[a]=='^'){cout表达式有错误endl;return1;break;}}elseif(isdigit(str[i])!=0)[键入文字][键入文字][键入文字]-13-{inta=i+1;if(str[a]=='('){cout表达式有错误endl;return1;break;}}elseif(isdigit(str[i])==0&&str[i]!='+'&&str[i]!='-'&&str[i]!='*'&&str[i]!='/'&&str[i]!='^'&&str[i]!='%'&&str[i]!='('&&str[i]!=')'&&str[i]!='.'){cout表达式有错误endl;return1;break;}elseif(str[i]=='.'){[键入文字][键入文字][键入文字]-14-inta=i+1;if(isdigit(str[a])==0){cout表达式有错误endl;return1;break;}}while(i==str.length()-1){cout表达式正确endl;return2;break;}}}elsecout表达式有错误endl;return1;}[键入文字][键入文字][键入文字]-15-doublecalculate(stringexp){stackdoublenumber;doubledigit;stringstr=;for(inti=0;iint(exp.length());i++){if(isdigit(exp[i])||exp[i]=='.'){str=str+exp[i];}elseif(exp[i]==''){constchar*p=str.c_str();digit=atof(p);//string转换为doublenumber.push(digit);str=;[键入文字][键入文字][键入文字]-16-}else//(exp[i]!='.'&&exp[i]!=''&&!isdigit(exp[i])&&number.size()=2){doubleresult;doubleright;doubleleft;right=number.top();number.pop();left=number.top();number.pop();switch(exp[i]){case'+':result=left+right;number.push(result);break;case'-':result=left-right;number.push(result);break;case'*':result=left*right;number.push(result);break;[键入文字][键入文字][键入文字]-17-case'/':result=left/right;number.push(result);break;case'%':{int(result)=int(left)%int(right);number.push(result);break;}case'^':result=pow(left,right);number.push(result);break;}}}doublefinalresult=number.top();number.pop();returnfinalresult;}voidmain(){intx=1;[键入文字][键入文字][键入文字]-18-cout计算表达式endl;cout支持加+减-乘*除/整数取余%次幂^小括号()endl;while(x==1){stringstr;cout请输入表达式，最后不加等号endl;cinstr;stringexp;inta=examine(str);if(a==2){exp=transform(str);coutstr=calculate(exp)endl;}cout继续运算请输入Y，否则按任意键退出endl;charch;cinch;if(ch=='Y'||ch=='y'){[键入文字][键入文字][键入文字]-19-x=1;}else{x=2;}}system(pause);}六、运行结果：这个是一开始运行的情况。输入完表达式后会判断表达式是否正确，如果正确会输出“表达式正[键入文字][键入文字][键入文字]-20-确”，错误会输出“表达式错误”。正确的情况下会输出结果，选择是否继续计算输入y或者Y都会进行下一次运算[键入文字][键入文字][键入文字]-21-结果仍然正确。接下来测试如果输入错误的表达式会怎么样。输入的表达式