后缀表达式求值.docx

电子信息学院实验报告书课程名： 数据结构 题 目： 实验三 后缀表达式求值 实验类别 设计 班 级： 软件1412 学 号： 141003600245 姓 名： 阿妹 评语：实验态度：认真（ ） 一般（ ） 差（ ）实验结果：正确（ ） 部分正确（ ）错（ ）实验理论：掌握（ ） 熟悉（ ） 了解（ ） 不懂（ ）操作技能：强（ ） 一般（ ） 差（ ）实验报告：好（ ） 一般（ ） 差（ ）成绩： 指导教师： 批阅时间： 年 月 日 数据结构 实验报告 - 4 -1、 实验内容或题目1、 用键盘输入一个整数后缀表达式（操作数的范围是09，运算符只含+、-、*、/，而且中间不可以有空格），使用循环程序从左向右读入表达式。2、 如果读入的是操作数，直接进入操作数栈。3、 如果读入的是运算符，立即从操作数栈取出所需的操作数，计算操作数运算的值，计算操作数运算的值，并将计算结果存回操作数栈。4、 检验程序运行结果。实验目的与要求目的：1、 掌握栈“后进先出”的特点。2、 掌握栈的典型应用后缀表达式求值。要求：1、 分析后缀表达式求值的算法思想，用c（c+）语言设计程序。2、 上机调试通过实验程序。3、 给出具体的算法分析，包括时间复杂度和空间复杂度等。4、 撰写实验报告。5、 本程序调试通过以后，添加到原教材验证性实验3的菜单中。2、实验步骤与源程序 实验步骤首先进行栈的存储结构生命，再定义指向栈的指针，然后依次进行进栈操作、开辟空间、构造结点、入栈和修改栈顶指针。再用void main()函数来求逆波兰式，char stackSTACKMAX表示存储算术表达式，char expSTACKMAX表示运算符号栈。用while(stri!=#&i!=STACKMAX);来接受输入表达式，用sum记录输入表达式总的字符个数。 源代码#include#define Maxlen 20typedef struct char dataMaxlen; int top; opstack; typedef struct float dataMaxlen; int top;stack;float compvalue(char exp) stack st; float d; char ch; int t=0; st.top=-1; ch=expt+; while(ch!=0) switch(ch) case+: st.datast.top-1=st.datast.top-1+st.datast.top; st.top-; break; case-: st.datast.top-1=st.datast.top-1-st.datast.top; st.top-; break; case*: st.datast.top-1=st.datast.top-1*st.datast.top; st.top-; break; case/: if(st.datast.top!=0) st.datast.top-1=st.datast.top-1/st.datast.top; st.top-; else printf(nt 表达式中有除数为零,本次计算无效!n ); break; default: if(ch=0 & ch=9) d=ch-0; st.top+; st.datast.top=d; ch=expt+; return st.datast.top; int main() char strMaxlen,expsMaxlen; printf(n请输入一个整数后缀表达式: );gets(str); printf(n其运算的结果为: %gnn,compvalue(exps);3、 测试数据与实验结果（可以抓图粘贴） 4、 结果分析与实验体会程序可以运行，但是我觉得在设计一个程序时看清题目的目的和要求很重要，我一开始没看清要求，开始在考虑怎么把算术表达式转化为后缀表达式，但后来再次理解了一下题目，才发现理解错了。然后参考了一下书上的程序，幸好题目要求不是很难，只是要求计算09中的数进行相关计算，在这几个函数中，我觉得要考虑到使用switch（）有点难度，开始没有显得用这个函数。这个函数中最难的就是对各个函数的调用，特别是计算后缀表达式的函数，与进栈，出栈联系到一起，真麻烦，但是经过不断得调试以及请教学霸，最后终于解