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

《算术表达式--数据结构实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、哈尔滨工业大学计算机科学与技术学院实验报告课程名称：数据结构与算法课程类型：必修实验项目名称：线性表及应用实验题目：表达式中缀转后缀并求值班级：学号：姓名：李清设计成绩报告成绩指导老师一、实验目的掌握线性表的使用，能用栈将中缀表达式转换成后缀表达式并求值。二、实验要求及实验环境实验要求：1、使用栈来进行操作2、能输出后缀表达式3、正确求出表达式的值并输出该值实验环境：NetBeansIDE6.7.1/win7系统三、设计思想（本程序中的用到的所有数据类型的定义，主程序的流程图及各程序模块之间的调用关系，自己扩展内容的等）文

2、档收集自网络，仅用于个人学习主要数据类型：queueA存储原来算术表达式stackB存储转换成的后缀表达式stackB1临时存储后缀表达式（B）stackC表达式转化过程使用的过度栈，存储操作符stackS存储数字（包括输入和计算过程中的数）charch，QQintd1,d2,d3主程序流程图：开始输入中缀表达式将中缀表达式转换成后缀表达式Transition函数后缀表达式求值Value函数结束输出表达式的值输出后缀表达式文档收集自网络，仅用于个人学习Transit

3、ion函数流程图：队列A.front（）判断右括号左括号把上一个左括号之前的所有操作符弹出存入B中，再弹出左括号存入C栈中加减号乘除号把上一个左括号之前的所有操作符弹出存入B中，再把+，-存入C中弹出前面紧邻的*、/，再把这个*或/存入C中数字存入B栈中，用空格表示一个数值的结束判断A不空A空将C栈中所有运算符依次弹出存入B栈中文档收集自网络，仅用于个人学习Value函数的流程图:B弹栈判断数字字符运算符求出其数值并存入S栈中从S栈中取出栈顶的两个数，进行相应的运算，并把结果存入S中文档收集自网络，仅用于个人学习B不空判断

4、B空返回S的栈顶元素注：在value函数中还可以判定除数是否为0，为0则输出"0can'tbeadivisor!"，并终止程序。文档收集自网络，仅用于个人学习四、测试结果由测试结果可知，基本完成了实验要求。五、系统不足与经验体会1、该程序只能运算整数，也不能处理输入的负数2、不能处理非法输入3、几种线性表（队列、栈、数组、链表）从根本上说可以实现同一个功能，只是难易程度的问题，熟悉各线性表的特点有助于快速选择简单的方法。文档收集自网络，仅用于个人学习4、第一次实验，代码比较乱，可能有些重复的地方六、附录：源代码（带注释）#

5、include#include#include#includeusingnamespacestd;voidtransition(queue&A,stack&B)//将中缀表达式转换成后缀表达式文档收集自网络，仅用于个人学习{stackC;//表达式转化过程使用的过度栈charch;while(!A.empty()){ch=A.front();A.pop();if(ch>='0'&&ch<='9')//判断数字{B.push(

6、ch);//压栈while(!A.empty()&&A.front()>='0'&&A.front()<='9')文档收集自网络，仅用于个人学习{B.push(A.front());//其它位依次入栈至该数字结束A.pop();}B.push('');//用空格表示一个数字的结束}elseif(ch=='(')C.push(ch);//判断为左括号elseif(ch==')')//判断为右括号，把上一个左括号之前的所有操作符弹出存入B中，再弹出左括号文档收集自网络，仅用于个人学习{while(C.top()!='('){B

7、.push(C.top());C.pop();}C.pop();}elseif(ch=='+'

8、

9、ch=='-')//判断为加减号，把上一个左括号之前的所有操作符弹出存入B中，再把+，-存入C中文档收集自网络，仅用于个人学习{while(!C.empty()&&C.top()!='('){B.push(C.top());C.pop();}C.push(ch);}elseif(ch=='*'

10、

11、ch=='/')//判断为乘除号，弹出前面紧邻的*，/，再把这个*或/存入C中文档收集自网络，仅用于个人学习{while(C.top

12、()=='*'

13、

14、C.top()=='/'){B.push(C.top());C.pop();}C.push(ch);}}while(!C.empty())//将C栈中所有运算符依次弹出存入B栈中{B.push(C.top());C.pop();}//下面是将B倒序while(!B.empty()){A