算术表达式--数据结构实验报告

个人收集整理仅供参考学习1/8哈尔滨工业大学计算机科学与技术学院实验报告课程名称：数据结构与算法课程类型：必修实验项目名称：线性表及应用实验题目：表达式中缀转后缀并求值班级：0903301学号：1090330117姓名：李清一、实验目的掌握线性表的使用，能用栈将中缀表达式转换成后缀表达式并求值。二、实验要求及实验环境实验要求：1、使用栈来进行操作2、能输出后缀表达式3、正确求出表达式的值并输出该值实验环境：NetBeansIDE6.7.1/win7系统三、设计思想（本程序中的用到的所有数据类型的定义，主程序的流程图及各程序模块之间的调用关系，自己扩展内容的等）文档收集自网络，仅用于个人学习主要数据类型：设计成绩报告成绩指导老师个人收集整理仅供参考学习2/8queuecharA存储原来算术表达式stackcharB存储转换成的后缀表达式stackcharB1临时存储后缀表达式（B）stackcharC表达式转化过程使用的过度栈，存储操作符stackintS存储数字（包括输入和计算过程中的数）charch，QQintd1,d2,d3主程序流程图：文档收集自网络，仅用于个人学习输入中缀表达式将中缀表达式转换成后缀表达式Transition函数后缀表达式求值Value函数结束输出表达式的值输出后缀表达式开始个人收集整理仅供参考学习3/8Transition函数流程图：文档收集自网络，仅用于个人学习Value函数的流程图:乘除号把上一个左括号之前的所有操作符弹出存入B中，再把+，-存入C中弹出前面紧邻的*、/，再把这个*或/存入C中数字存入B栈中，用空格表示一个数值的结束判断A不空A空将C栈中所有运算符依次弹出存入B栈中队列A.front（）判断左括号右括号加减号存入C栈中把上一个左括号之前的所有操作符弹出存入B中，再弹出左括号个人收集整理仅供参考学习4/8文档收集自网络，仅用于个人学习注：在value函数中还可以判定除数是否为0，为0则输出0can'tbeadivisor!，并终止程序。文档收集自网络，仅用于个人学习四、测试结果B弹栈判断数字字符运算符求出其数值并存入S栈中从S栈中取出栈顶的两个数，进行相应的运算，并把结果存入S中B空返回S的栈顶元素判断B不空个人收集整理仅供参考学习5/8由测试结果可知，基本完成了实验要求。五、系统不足与经验体会1、该程序只能运算整数，也不能处理输入的负数2、不能处理非法输入3、几种线性表（队列、栈、数组、链表）从根本上说可以实现同一个功能，只是难易程度的问题，熟悉各线性表的特点有助于快速选择简单的方法。文档收集自网络，仅用于个人学习4、第一次实验，代码比较乱，可能有些重复的地方六、附录：源代码（带注释）#includeiostream#includestring#includestack#includequeueusingnamespacestd;voidtransition(queuechar&A,stackchar&B)//将中缀表达式转换成后缀表达式文档收集自网络，仅用于个人学习{stackcharC;//表达式转化过程使用的过度栈charch;while(!A.empty()){ch=A.front();A.pop();if(ch='0'&&ch='9')//判断数字{B.push(ch);//压栈while(!A.empty()&&A.front()='0'&&A.front()='9')文档收集自网络，仅用于个人学习个人收集整理仅供参考学习6/8{B.push(A.front());//其它位依次入栈至该数字结束A.pop();}B.push('');//用空格表示一个数字的结束}elseif(ch=='(')C.push(ch);//判断为左括号elseif(ch==')')//判断为右括号，把上一个左括号之前的所有操作符弹出存入B中，再弹出左括号文档收集自网络，仅用于个人学习{while(C.top()!='('){B.push(C.top());C.pop();}C.pop();}elseif(ch=='+'||ch=='-')//判断为加减号，把上一个左括号之前的所有操作符弹出存入B中，再把+，-存入C中文档收集自网络，仅用于个人学习{while(!C.empty()&&C.top()!='('){B.push(C.top());C.pop();}C.push(ch);}elseif(ch=='*'||ch=='/')//判断为乘除号，弹出前面紧邻的*，/，再把这个*或/存入C中文档收集自网络，仅用于个人学习{while(C.top()=='*'||C.top()=='/'){B.push(C.top());C.pop();}C.push(ch);}}while(!C.empty())//将C栈中所有运算符依次弹出存入B栈中{B.push(C.top());C.pop();}//下面是将B倒序个人收集整理仅供参考学习7/8while(!B.empty()){A.push(B.top());B.pop();}while(!A.empty()){B.push(A.front());A.pop();}return;}intvalue(stackchar&B)//后缀表达式求值{intd1,d2,d3;stackintS;charch;while(!B.empty()){ch=B.top();B.pop();if(ch='0'&&ch='9')//将数字字符转换成数字{d1=0;while(ch!=''){d1=10*d1+ch-'0';//求出一个数字的数值ch=B.top();B.pop();}S.push(d1);}else{d2=S.top();S.pop();d3=S.top();S.pop();switch(ch)//运算符操作{case'+':S.push(d3+d2);break;case'-':S.push(d3-d2);break;case'*':S.push(d3*d2);break;case'/':if(d2!=0){个人收集整理仅供参考学习8/8S.push(d3/d2);}else//0不能做除数{cout0can'tbeadivisor!endl;exit(0);}break;}}}returnS.top();}intmain(){charQQ;queuecharA;//存储原来算术表达式stackcharB,B1;//存储转换成的后缀表达式coutPleaseinputyourexpession:endl;while(QQ!='\n'){QQ=getchar();A.push(QQ);};transition(A,B);//前缀表达式转换成后缀表达式coutThepofixexpessionis:endl;while(!B.empty()){coutB.top();B1.push(B.top());B.pop();//将B栈数据转移到B1}coutendl;while(!B1.empty())//数据返还给B{B.push(B1.top());B1.pop();}coutValue:endlvalue(B)endl;return0;}