数据结构实验 栈的应用.doc

课程题目：数据结构试验学院：班级：姓名：学号:实验题目：栈的应用实验内容：算术表达式求值实验目的：掌握栈和队列的概念及工作原理，运用其原理完成实验题目中的内容。实验要求：为了使学生更好的掌握与理解课堂上老师所讲的概念与原理，实验前每个学生要认真预习所做的实验内容及编写源程序伪码（写在纸上及盘中均可）实验学时：4学时设计原理：任何一个表达式都是有操作数、运算符和界限符组成的。我们把运算符和界限符统称为算符，它们构成的集合命名为OP。根据简单算术表达式的运算规则，在运算的每一步中，任意两个相继出现的算符a和b之间的优先关系至多是下面三种关系之一：ab a的优先权大于b为实现算符优先算法，可以使用两个工作栈。一个为，用以寄存预算符；另一个为，用以寄存操作数或运算结果。算法基本思想：首先置操作数栈为空栈，表达式起始运算符“”为运算符栈的基本元素；依次读入表达式中每个字符，若是操作数则进栈，若是运算符则和栈的栈顶运算符比较优先权执行相应操作，直至整个表达式求值完毕（即栈的栈顶元素和当前读入的字符均为“”）。详细程序清单及注释说明：#include #include #include #include #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define STACK_INIT_SIZE 100/初始量分配#define STACKINCREMENT 10/存储空间的分配增量typedef structchar *base;char *top;int stacksize;sqstack;int initstack(sqstack &s)/创造一个空栈s.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char);if(!s.base) exit(OVERFLOW);s.top=s.base;s.stacksize=STACK_INIT_SIZE;return OK;int push(sqstack &s, char e)/插入为新的栈顶元素if(s.top-s.base=s.stacksize)s.base=(char *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(char);if(!s.base) exit(OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;*s.top+=e;return OK;int pop(sqstack &s,char &e)/若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORif(s.top=s.base) return ERROR;e=*-s.top;return OK;int gettop(sqstack s)char e;if(s.top=s.base) return ERROR;e=*(s.top-1);return e;char in(char getchar)if(getchar=# & getchar;break;case -:return ;break;case *:return ;break;case /:return ;break;case (:return ;break;case #:return ;break;if(optrchar=-)switch(getchar1)case +:return ;break;case -:return ;break;case *:return ;break;case /:return ;break;case (:return ;break;case #:return ;break;if(optrchar=*)switch(getchar1)case +:return ;break;case -:return ;break;case *:return ;break;case /:return ;break;case (:return ;break;case #:return ;break;if(optrchar=/)switch(getchar1)case +:return ;break;case -:return ;break;case *:return ;break;case /:return ;break;case (:return ;break;case #:return ;break;if(optrchar=()switch(getchar1)case +:return ;break;case -:return ;break;case *:return ;break;case /:return ;break;case (:return ;break;case -:return ;break;case *:return ;break;case /:return ;break;case ):return ;break;case #:return ;break;if(optrchar=#)switch(getchar1)case +:return ;break;case -:return ;break;case *:return ;break;case /:return ;break;case (:return 47) x=atoi(&x); if(z47) z=atoi(&z); switch(y) case +: return x+z; break; case -: return x-z;break; case *: return x*z;break; case /: return x/z;break; char EvaluateExpression()char theta;char a,b,c;sqstack OPTR;sqstack OPND;initstack(OPTR);push(OPTR,#);initstack(OPND);c=getchar();while(c!=# | gettop(OPTR)!=#)if(!in(c)push(OPND,c);c=getchar();elseswitch(precede(gettop(OPTR),c)case :pop(OPTR,theta);pop(OPND,b);pop(OPND,a);push(OPND,operate(a,theta,b);break;return gettop(OPND);main()loop:char a;printf(输入算式：(输入#结束)n);int value;value=(int)EvaluateExpression();printf(计算结果为：%dn,value);printf(继续计算？ (输入1继续/输入0结束);scanf(%d,&a);if(a=1)goto loop;elsereturn ERROR;运行与测试及结果：试验中所遇到的问题及解决办法：实验当中遇到了程序显示结果和实际运算结果不相符的情况。