实验3 后缀表达式求值.doc

电子信息学院实验报告书课程名： 数据结构 题 目： 后缀表达式求值 实验类别 设计 班 级： 学 号： 姓 名： 2011年10 月 10 日 算法设计与分析 实验报告 - 5 -1、 实验题目（1) 掌握栈“后进先出”的特点；（2) 掌握栈的典型应用后缀表达式求值。2、 实验内容（1） 用键盘输入一个整数后缀表达式（操作数的范围是09，运算符只含+，-，*，、，而且中间不可以有空格），使用循环程序从左向右读入表达式。（2） 如果读入的是操作数，直接进入操作数栈。（3） 如果读入的是运算符，立即从操作数栈取出所需的操作数，计算操作数运算的值，并将计算结果存回操作数栈。（4） 检验程序运行结果。3、 实验要求（1） 分析后缀表达式求值的算法思想，用C(或C+)语言设计程序。（2） 上机调试通过实验程序。（3） 给出具体的算法分析，包括时间复杂度和空间复杂度等。（4） 撰写实验报告。（5） 本程序调试通过以后，添加到原教材验证性实验3的菜单中去。4、 实验步骤与源程序 实验步骤 首先进行栈结构声明，其中包括指针域和数据域。下面是为了实现题目中的要求，定义几个函数，分别是进栈、出栈、判断栈空、判断运算符、折合计算表达式函数，最后是主函数对这几个函数的调用。进栈函数主要是创建新节点，并使新结点成为栈顶元素。出栈是通过栈顶元素的下移，回收出栈元素实现。判断是否是运算符通过一个switch ()函数的选择语句，不用break语句来实现。计算表达式也是switch ()函数的选择语句来实现的。主函数是运用循环语句和对各个函数的调用来完成的。 源代码#include#includestruct node / 栈结构声明int data; / 数据域 struct node *next; / 指针域;typedef struct node stacklist; / 链表类型typedef stacklist *link; / 链表指针类型link operand=NULL; / 操作数栈指针link push(link stack,int x) / 进栈 link newnode; / 新结点指针 newnode=new stacklist; / 分配新结点if (!newnode) printf(分配失败！); return NULL; newnode-data=x; / 创建结点的内容 newnode-next=stack; stack=newnode; / 新结点成为栈顶元素return stack;link pop(link stack,int *x) / 出栈 link top; / 指向栈顶 if (stack !=NULL) top=stack; / 指向栈顶 stack=stack-next; / 移动栈顶指针 *x=top-data; / 取数据 delete top; / 吸收结点 return stack; / 返回栈顶指针 else *x=-1;int empty(link stack) / 判栈空 if (stack!=NULL) return 1; else return 0;int panduan(char op) / 判断运算符 switch (op) case+: case-: case*:return 1; / 是运算符,返回1 case/:return 0; / 不是运算符,返回0 int jisuan(int op,int operand1,int operand2) / 计算表达式值 switch(char)op) case*:return(operand1*operand2); case/:return(operand1/operand2); case+:return(operand1+operand2); case-:return(operand1-operand2); void main() / 主函数 char a100; int operand1=0,operand2=0; / 定义操作数1,2 int result=0; / 定义操作结果 int i=0; printf(tn 请输入后缀表达式：); gets(a); / 读取表达式 printf(tnn 后缀表达式%s的计算结果是：,a); while (ai !=0 & ai !=n) / 分析表达式字符串 if (panduan(ai) / 是运算符，取两个操作数 operand=pop(operand,&operand1); operand=pop(operand,&operand2); operand=push(operand,jisuan(ai,operand1,operand2);/ 计算结果入栈 else operand=push(operand,ai-48); / 是操作数，压入操作数栈 i+; / 移到下一个字符串位置 operand=pop(operand,&result); / 弹出结果 printf(%dn,result); / 输出5、 测试数据与实验结果（可以抓图粘贴）6、 结果分析与实验体会程序可以运行，结果准确。我觉得在设计一个程序时看清题目的目的和要求很重要，我就是没有看清要求，开始一直在考虑怎么把算术表达式转化成后缀表达式，但后来跟同学讨论了一下，我才发现题目看错了。后来就是看书上后缀表达式是怎么来的，幸好题目要求不是很难，只是要求计算09中的数进行相关计算。在5个函数中，我觉得要考虑到使用switch()有点难度，开始没有想到用这个函数。还有定义操作数operand，我也有点困惑，网上进行相关搜索才会用的。整个函数中最难