您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 销售管理 > 线性表及其应用-中缀转后缀并计算其值
哈尔滨工业大学计算机科学与技术学院实验报告课程名称:数据结构与算法课程类型:必修实验项目名称:线性表及其应用实验题目:算术表达式求值班级:1003201学号:姓名:设计成绩报告成绩指导老师一、实验目的1.掌握栈的数据结构与基本操作2.了解什么是中缀表达式和后缀表达3.了解并掌握中缀表达式转为后缀表达式的方法4.掌握使用栈结构求解后缀表达式的求值方法5.提高利用计算机分析和解决复杂实际问题的能力二、实验要求及实验环境1.试验要求:(1)从键盘输入任意一个语法正确的(中缀)表达式,显示并保存该表达式。(2)利用栈结构,把上述(中缀)表达式转换成后缀表达式,并显示栈的状态变化过程和所得到的后缀表达式。(3)利用栈结构,对上述后缀表达式进行求值,并显示栈的状态变化过程和最终结果。2.试验环境:Windows7操作系统DevcC++编译器三、设计思想(本程序中的用到的所有数据类型的定义,主程序的流程图及各程序模块之间的调用关系)程序中用到的数据类型的定义:charstring1[100];//存放表达式structStack{//定义一个栈chardata[maxlength];inttop;};typedefstructStackstack1;stack1output1;//存放操作符stackdoubleoutput1;//存放后缀表达式的数字的栈主程序流程图:开始输入一个以字符串形式定义的运算式并保存至数组string1[100]中,声明一个运算符栈用来存放运算符指针遍历字符串数组判断字符串数组每一个单元的内容为)弹出栈内与之匹配的(前的所有运算符并存结尾数组中为(直接压入栈中并在结尾数组中存入空格为数字直接存入结尾数组中为运算符与栈顶运算符比较弹出栈内所有元素存入结尾数组直接压入栈中高低存入空格存入空格将栈内元素全部存至结尾数组中申请一个新的整型栈用于后缀表达式计算遍历结尾数组中的每一个元素判断每一个元素的内容为数字为“”为运算符弹出整型栈中的两个元素进行相应的加减乘除运算,并将运算结果重新压入栈中将空格之前到前一个空格之间的所有存入数字数组中的数字进行位数计算得到一个新的数字压入栈中将字符型转换为整型存入一个数字数组中去将后缀字符串和计算得到的结构输出各程序模块之间的调用关系:intmain(){charqianzhui[100];cout请输入一个语法正确的(中缀)表达式(在此过程不用输入等号):;gets(qianzhui);cout该中缀表达式为:;coutqianzhuiendl;;change(qianzhui);cout转换为后缀表达式为:;coutstring2endl;;jisuan(string2);return0;}四、测试结果.请输入一个语法正确的(中缀)表达式(在此过程不用输入等号):12.3*(12.34+23.54)-23.4/23.45该中缀表达式为:12.3*(12.34+23.54)-23.4/23.45进栈元素为:*进栈元素为:+出栈元素为:+出栈元素为:(出栈元素为:*进栈元素为:-进栈元素为:/出栈元素为:/结束出栈元素为:-转换为后缀表达式为:12.312.3423.54+*23.423.45/-将12.3进栈将12.34进栈将23.54进栈将23.54进栈将23.54出栈将12.34出栈将35.88进栈将35.88进栈将35.88出栈将12.3出栈将441.324进栈将23.4进栈将23.45进栈将23.45进栈将23.45出栈将23.4出栈将23.45进栈将23.45进栈将0.997868出栈将441.324出栈将440.326进栈将0.997868进栈将440.326出栈后缀表达式的值为:440.326五、系统不足与经验体会系统不足:无法处理负数,当输入不正确的表达式时程序会异常终止,没有找到解决的办法。体会:编程过程中遇到问题应该多问问同学,上网查资料,不应该自己死扣,还应该多于同学分享一下自己的编程思想,多吸取一下别的同学的编程思想。由于没有对问题进行深层次的分析思考,编的程序功能实现不完整,存在bug,但是主要功能都能实现。六、附录:源代码(带注释)#includeiostream#includecstring#includestring.h#includestdlib.h#includestackcharstring1[100];charstring2[100];constintmaxlength=100;usingnamespacestd;structStack{//定义一个栈chardata[maxlength];inttop;};typedefstructStackstack1;voidPush(intx,stack1&S)//把x压栈S的栈顶{if(S.top==0)cout栈已满!endl;else{S.top=S.top-1;S.data[S.top]=x;}}voidMakeNull(stack1&S)//把栈S清空{S.top=maxlength;}boolEmpty(stack1&s)//测试栈S是否为空{if(s.topmaxlength-1)returntrue;elsereturnfalse;}charTop(stack1&S)//返回栈S的栈顶元素{inta;if(Empty(S))cout栈是空的!endl;else{a=S.top;S.top=S.top+1;returnS.data[a];}}voidPop(stack1&s)//删除栈S的栈顶元素{if(Empty(s))cout栈是空的!endl;else{s.top=s.top+1;}}boolprir(chara,stack1&S)//判断操作符优先级{if(Empty(S))returntrue;else{charb=S.data[S.top];switch(a){case'-':case'+':switch(b){case'-':case'+':case'*':case'/':returnfalse;break;case'(':returntrue;break;}break;case'*':case'/':switch(b){case'-':case'+':case'(':returntrue;break;case'*':case'/':returnfalse;break;}break;}}}voidchange(charL[])//中缀表达式转后缀表达式{intj=0;//存放后缀表达式stack1output1;//存放操作符MakeNull(output1);intnumber=strlen(L);for(inti=0;inumber;i++){if(L[i]=48&&L[i]=57||L[i]=='.')//如果是数字,直接保存{string1[j]=L[i];j++;}else//不是数字{switch(L[i]){case'+':case'-':case'*':case'/':string1[j]='';j++;if(prir(L[i],output1))//比栈顶优先级高,直接进栈{Push(L[i],output1);cout进栈元素为:L[i]endl;}elseif(output1.data[output1.top]!='(')//比栈顶优先级低,先出栈,L[i]进栈{string1[j]=Top(output1);cout出栈元素为:string1[j]endl;j++;Push(L[i],output1);cout进栈元素为:L[i]endl;}break;case'('://直接进栈Push(L[i],output1);break;case')'://匹配栈内的(,并删除'('string1[j]='';j++;do{chara=Top(output1);cout出栈元素为:aendl;if(a!='('){string1[j]=a;j++;}elsebreak;}while(1);break;}}}string1[j]='';j++;while(!Empty(output1)){string1[j]=Top(output1);cout出栈元素为:string1[j]endl;j++;}char*li=string1;char*ni=string2;while(*li!='\0')//调整后缀表达式,以便计算后缀表达式的值{if((*li='0'&&*li='9')||*li=='.')*ni++=*li++;else{*ni++=*li++;if(*li==''){*li++;}}}}voidjisuan(charL[]){charn[100];intj=0;doublem,k,b;stackdoubleoutput1;//存放后缀表达式的数字intnumber=strlen(string1);for(inti=0;inumber;i++){if(L[i]=48&&L[i]=57||L[i]=='.')//如果是数字,直接保存{n[j]=L[i];j++;}elseif(L[i]==''){m=atof(n);output1.push(m);memset(n,'',j);j=0;cout将m进栈endl;}else//不是数字{cout将m进栈endl;switch(L[i]){case'+':{m=output1.top();output1.pop();cout将m出栈endl;k=output1.top();output1.pop();cout将k出栈endl;m+=k;output1.push(m);cout将m进栈endl;}break;case'-':{b=0;m=output1.top();output1.pop();cout将m出栈endl;k=output1.top();output1.pop();cout将k出栈endl;b=k-m;;output1.push(b);cout将b进栈endl;}break;case'*':{m=output1.top();output1.pop();cout将m出栈endl;k=output1.top();output1.pop();cout将k出栈endl;m*=k;output1.push(m);cout将m进栈endl;}break;case'/':{b=0;m=output1.top();output1.pop();cout将m出栈endl;k=output1.top();output1.pop();cout将k出栈endl;b=k/m;output1.push(b);cout将m进栈endl;}break;}}}m=output1.top();cout将m出栈endl;cout后缀表达式的值为:mendl;}intmain(){charqianzhui[100];cout请输入一个语法正确的(中缀)表达式(在此过程不用输入等号):;gets(qianzhui);cout该中缀表达式为:;coutqianzhuiendl;;change(qianzhui);cout转换为后缀表达式为:;coutstring2endl;;jisuan(string2);return0;}
本文标题:线性表及其应用-中缀转后缀并计算其值
链接地址:https://www.777doc.com/doc-4849202 .html