《2022年算术表达式--数据结构实验报告》由会员分享，可在线阅读，更多相关《2022年算术表达式--数据结构实验报告（8页珍藏版）》请在金锄头文库上搜索。
1、个人收集整理仅供参考学习1 / 8 哈尔滨工业大学计算机科学与技术学院实验报告课程名称：数据结构与算法课程类型：必修实验项目名称：线性表及应用实验题目：表达式中缀转后缀并求值班级： 0903301 学号： 1090330117 姓名：李清一、实验目的掌握线性表的使用，能用栈将中缀表达式转换成后缀表达式并求值。二、实验要求及实验环境实验要求： 1、使用栈来进行操作2、能输出后缀表达式3、正确求出表达式的值并输出该值实验环境： NetBeans IDE 6.7.1 / win 7系统三、设计思想（本程序中的用到的所有数据类型的定义，主程序的流程图及各程序模块之间的调用关系，自己扩展内容的等）文档收
2、集自网络，仅用于个人学习主要数据类型：设计成绩报告成绩指导老师精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 8 页个人收集整理仅供参考学习2 / 8 queue A 存储原来算术表达式stack B存储转换成的后缀表达式stack B1 临时存储后缀表达式（ B）stack C 表达式转化过程使用的过度栈， 存储操作符stack S 存储数字（包括输入和计算过程中的数）char ch，QQ int d1,d2,d3 主程序流程图：文档收集自网络，仅用于个人学习输入 中 缀 表将中缀表达式转换成后缀表达式Transition 函数后缀表
3、达式求值Value函数结束输出表达式的值输出后缀表达式开始精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 8 页个人收集整理仅供参考学习3 / 8 Transition 函数流程图：文档收集自网络，仅用于个人学习Value 函数的流程图 : 乘除号把 上 一 个左 括 号 之前 的 所 有操 作 符 弹出 存 入B中 ， 再 把+，-存入 C中弹出前面紧邻的 * 、/ ， 再把这个* 或 /存入 C 中数字存入 B 栈中，用空格表示一个数值的结束判断A 不空A 空将 C 栈中所有运算符依次弹出存入B栈中队列A.front判断左括号右括号
4、加减号存 入C栈中把上一个左括号之前的所有操作符弹出存入 B 中，再弹出左括号精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 8 页个人收集整理仅供参考学习4 / 8 文档收集自网络，仅用于个人学习注：在 value 函数中还可以判定除数是否为0，为 0 则输出 0 cant be a divisor!，并终止程序。文档收集自网络，仅用于个人学习四、测试结果B弹栈判断数字字符运算符求出其数值并存入 S 栈中从 S 栈中取出栈顶的两个数，进行相应的运算，并把结果存入S 中B 空返回 S 的栈顶元素判断B 不空精选学习资料 - - - -
5、- - - - - 名师归纳总结 - - - - - - -第 4 页，共 8 页个人收集整理仅供参考学习5 / 8 由测试结果可知，基本完成了实验要求。五、系统不足与经验体会1、该程序只能运算整数，也不能处理输入的负数 2 、不能处理非法输入 3 、几种线性表（队列、栈、数组、链表）从根本上说可以实现同一个功能，只是难易程度的问题， 熟悉各线性表的特点有助于快速选择简单的方法。文档收集自网络，仅用于个人学习4、第一次实验，代码比较乱，可能有些重复的地方六、附录：源代码（带注释）#include #include #include #include using namespace std; v
6、oid transition(queue &A, stack &B) /将中缀表达式转换成后缀表达式文档收集自网络，仅用于个人学习 stack C; /表达式转化过程使用的过度栈 char ch; while(!A.empty() ch = A.front(); A.pop(); if(ch = 0 & ch = 0 & A.front() = 9)文档收集自网络，仅用于个人学习精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 8 页个人收集整理仅供参考学习6 / 8 B.push(A.front(); /其它位依次入栈至该数字结束 A.
7、pop(); B.push( ); /用空格表示一个数字的结束 else if(ch = () C.push(ch) ;/判断为左括号 else if(ch = ) /判断为右括号，把上一个左括号之前的所有操作符弹出存入 B中，再弹出左括号文档收集自网络，仅用于个人学习 while (C.top() != () B.push(C.top(); C.pop(); C.pop(); else if(ch = + | ch = -)/判断为加减号，把上一个左括号之前的所有操作符弹出存入B中，再把 +，- 存入 C中文档收集自网络，仅用于个人学习 while(!C.empty() & C.top()
8、!= () 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.push(ch); while (!C.empty()/将 C栈中所有运算符依次弹出存入B栈中 B.push(C.top(); C.pop(); /下面是将 B 倒序精选学习资料 - - - - - - - - - 名师归纳总结 - - -
9、- - - -第 6 页，共 8 页个人收集整理仅供参考学习7 / 8 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)/将数字字符转换成数字 d1 = 0; while(ch != ) d1 = 10*d1 + ch - 0
10、;/求出一个数字的数值 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) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 8 页个人收集整理仅供参考学习8 / 8 S
11、.push( d3/d2 ); else /0不能做除数 cout 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(); B1.push(B.top();B.pop();/将 B栈数据转移到 B1 cout endl ; while(!B1.empty()/数据返还给 B B.push(B1.top();B1.pop(); cout Value: endl value(B) endl; return 0; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 8 页
