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

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

2、储原来算术表达式stack B存储转换成的后缀表达式stack B1 临时存储后缀表达式（B）stack C表达式转化过程使用的过度栈，存储操作符stack S存储数字（包括输入和计算过程中的数）char ch，QQint d1,d2,d3主程序流程图：开始输入中缀表达式将中缀表达式转换成后缀表达式Transition函数后缀表达式求值Value函数结束输出表达式的值输出后缀表达式文档收集自网络，仅用于个人学习Transition函数流程图：队列A.front（）判断右括号左括号把上一个左括号之前的所有操作符弹出存入B中，再弹出左括号存入C栈中加减号乘除号把上一个左括号之前的所有操作符弹出存入

3、B中，再把+，-存入C中弹出前面紧邻的*、/，再把这个*或/存入C中数字存入B栈中，用空格表示一个数值的结束判断A不空A空将C栈中所有运算符依次弹出存入B栈中文档收集自网络，仅用于个人学习Value函数的流程图:B弹栈判断数字字符运算符求出其数值并存入S栈中从S栈中取出栈顶的两个数，进行相应的运算，并把结果存入S中文档收集自网络，仅用于个人学习B不空判断B空返回S的栈顶元素注：在value函数中还可以判定除数是否为0，为0则输出0 cant be a divisor!，并终止程序。文档收集自网络，仅用于个人学习四、测试结果由测试结果可知，基本完成了实验要求。五、系统不足与经验体会1、该程序只能

4、运算整数，也不能处理输入的负数 2、不能处理非法输入 3、几种线性表（队列、栈、数组、链表）从根本上说可以实现同一个功能，只是难易程度的问题，熟悉各线性表的特点有助于快速选择简单的方法。文档收集自网络，仅用于个人学习4、第一次实验，代码比较乱，可能有些重复的地方六、附录：源代码（带注释）#include#include #include #include using namespace std;void transition(queue &A, stack &B) /将中缀表达式转换成后缀表达式文档收集自网络，仅用于个人学习 stack C; /表达式转化过程使用的过度栈 char ch; w

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

6、.pop(); C.pop(); else if(ch = + | ch = -)/判断为加减号，把上一个左括号之前的所有操作符弹出存入B中，再把+，-存入C中文档收集自网络，仅用于个人学习 while(!C.empty() & C.top() != () B.push(C.top(); C.pop(); C.push(ch); else if (ch = * | ch = /) /判断为乘除号，弹出前面紧邻的*，/，再把这个*或/存入C中文档收集自网络，仅用于个人学习 while(C.top() = * | C.top() = /) B.push(C.top(); C.pop(); C.pu

7、sh(ch); while (!C.empty()/将C栈中所有运算符依次弹出存入B栈中 B.push(C.top(); C.pop(); /下面是将B倒序 while(!B.empty() A.push(B.top();B.pop(); while(!A.empty() B.push(A.front();A.pop(); return ;int value(stack &B) /后缀表达式求值 int d1,d2,d3; stack S; char ch; while(!B.empty() ch = B.top(); B.pop(); if(ch = 0&ch = 9)/将数字字符转换成数字

8、 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) S.push( d3/d2 ); else /0不能做除数 cou

9、t 0 cant be a divisor! endl; exit(0); break; return S.top();int main() char QQ; queue A; /存储原来算术表达式 stack B,B1; /存储转换成的后缀表达式 cout Please input your expession: endl; while( QQ != n) QQ = getchar(); A.push(QQ); ; transition(A,B);/前缀表达式转换成后缀表达式 cout The pofix expession is: endl; while(!B.empty() cout B.top()