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