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

电子信息学院 实验报告书 课程名： 数据结构 题 目： 后缀表达式求值 实验类别 设计 班 级： 学 号： 姓 名： 2011年10 《算法设计与分析 》实验报告 - PAGE 5 - 实验题目 掌握栈“后进先出”的特点； 掌握栈的典型应用——后缀表达式求值。 实验内容 用键盘输入一个整数后缀表达式（操作数的范围是0~9，运算符只含+，-，*，、，而且中间不可以有空格），使用循环程序从左向右读入表达式。 如果读入的是操作数，直接进入操作数栈。 如果读入的是运算符，立即从操作数栈取出所需的操作数，计算操作数运算的值，并将计算结果存回操作数栈。 检验程序运行结果。 实验要求 分析后缀表达式求值的算法思想，用C(或C++)语言设计程序。 上机调试通过实验程序。 给出具体的算法分析，包括时间复杂度和空间复杂度等。 撰写实验报告。 本程序调试通过以后，添加到原教材验证性实验3的菜单中去。 实验步骤与源程序 = 1 \* GB2 ⑴ 实验步骤 首先进行栈结构声明，其中包括指针域和数据域。下面是为了实现题目中的要求，定义几个函数，分别是进栈、出栈、判断栈空、判断运算符、折合计算表达式函数，最后是主函数对这几个函数的调用。进栈函数主要是创建新节点，并使新结点成为栈顶元素。出栈是通过栈顶元素的下移，回收出栈元素实现。判断是否是运算符通过一个switch ()函数的选择语句，不用break语句来实现。计算表达式也是switch ()函数的选择语句来实现的。主函数是运用循环语句和对各个函数的调用来完成的。 = 2 \* GB2 ⑵ 源代码 #includestdlib.h #includestdio.h struct 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) // 判栈空 {