数据结构 实验3 后缀表达式求值

《算法设计与分析》实验报告-1-1、实验目的（1)掌握栈“后进先出”的特点；（2)掌握栈的典型应用——后缀表达式求值。2、实验内容（1)用键盘输入一个整数后缀表达式（操作数的范围是0～9，运算符只含、、*、/，而且中间不可以有空格），使用循环程序从左向右读入表达式；（2)如果读入的是操作数，直接进入操作数栈；（3)如果读入的是运算符，立即从操作数栈取出所需的操作数，计算操作数运算的值，并将计算结果存回操作数栈；（4)检验程序运行结果。3、实验要求（1)分析后缀表达式求值的算法思想，用C（C++）语言完成程序设计。（2)上机调试通过实验程序。（3)给出具体的算法分析，包括时间复杂度和空间复杂度等。（4)撰写实验报告（把输入实验数据及运行结果用抓图的形式粘贴到实验报告上）。（5)本程序调试通过以后，添加到原教材验证性实验3的菜单中去。4、实验步骤与源程序⑴实验步骤我先从具体的问题中抽象出适当的数学模型，然后设计出相应的算法，其中，需要设计一个函数来求后缀表达式，设计另外一个函数来求后缀表达式的值，最后，编写主函数，串接程序，并调试程序，得出实验结果。⑵源代码#includestdio.h#defineMaxlen88typedefstruct{chardata[Maxlen];inttop;}opstack;typedefstruct{floatdata[Maxlen];inttop;}stack;voidtrans(charstr[],charexp[])//求后缀表达式{opstackop;charch;《算法设计与分析》实验报告-2-inti=0,t=0;op.top=-1;ch=str[i];i++;while(ch!='\0'){switch(ch){case'(':op.top++;op.data[op.top]=ch;break;case')':while(op.data[op.top]!='('){exp[t]=op.data[op.top];op.top--;t++;}op.top--;break;case'+':case'-':while(op.top!=-1&&op.data[op.top]!='('){exp[t]=op.data[op.top];op.top--;t++;}op.top++;op.data[op.top]=ch;break;case'*':case'/':while(op.top=='/'||op.top=='*'){exp[t]=op.data[op.top];《算法设计与分析》实验报告-3-op.top--;t++;}op.top++;op.data[op.top]=ch;break;case''://输入为空格,则跳过break;default:while(ch='0'&&ch='9'){exp[t]=ch;t++;ch=str[i];i++;}i--;exp[t]='';t++;}ch=str[i];i++;}while(op.top!=-1){exp[t]=op.data[op.top];t++;op.top--;}exp[t]='\0';}floatcompvalue(charexp[])//后缀表达式求值{stackst;《算法设计与分析》实验报告-4-floatd;charch;intt=0;st.top=-1;ch=exp[t];t++;while(ch!='\0'){switch(ch){case'+':st.data[st.top-1]=st.data[st.top-1]+st.data[st.top];st.top--;break;case'-':st.data[st.top-1]=st.data[st.top-1]-st.data[st.top];st.top--;break;case'*':st.data[st.top-1]=st.data[st.top-1]*st.data[st.top];st.top--;break;case'/':if(st.data[st.top]!=0){st.data[st.top-1]=st.data[st.top-1]/st.data[st.top];st.top--;}elseprintf(\n\t表达式中有除数为零,本次计算无效!\n);break;default:d=0;while(ch='0'&&ch='9'){d=10*d+ch-'0';《算法设计与分析》实验报告-5-ch=exp[t];t++;}st.top++;st.data[st.top]=d;}ch=exp[t];t++;}returnst.data[st.top];}voidmain(){charstr[Maxlen],exps[Maxlen];printf(\n请输入一个算术表达式:);printf(\n提示：操作数的范围是“0-9”，运算符只含+,-,*,/和括号，中间不可以有空格\n);gets(str);printf(\n原算术表达式为:%s\n,str);trans(str,exps);printf(\n其后缀表达式为:%s\n,exps);printf(\n其运算的结果为:%g\n\n,compvalue(exps));}5、测试数据与实验结果（可以抓图粘贴）《算法设计与分析》实验报告-6-6、结果分析与实验体会本次实验是参考了范例程序，经过自己的改写，从而实现要求。先做简单的输出，一步步的再做其它格式的设置。在实验的过程中，我加深了对后缀表达式算法的理解，读入操作数时，直接输出到后缀表达式，读入运算符，则压入运算符号栈，而且，若后进的运算符优先级高与先进的，则继续进栈，若后进的运算符优先级不高于先进的，则将运算符号栈内高于或等于后进运算符级别的运算符依次弹出并输出到后缀表达式，对于括号，遇到开括号就进栈，遇到闭括号，则把靠近的开括号以及其后进栈的运算符依次弹出，并输出到后缀表达式，不过，开括号和闭括号都不输出，所以在设计算法的时候要注意，这里是用switch语句实现的。因为栈是“后进先出”的线性表，所以，本程序的设计过程也是对前面线性表知识的巩固。最后，我想说，编写程序需要耐心，调试程序更需要耐心，只有认真，细心，不厌其烦的，才可以做好一件事情。