数据结构后缀表达式的计算.doc

深 圳 大 学实 验 报 告课程名称： 数据结构 实验名称： 后缀表达式的计算 班 级： 1 姓 名： 同 组 人： 无 实验日期： 2011 年 10 月 11 日 教师签字： 一、实验目的熟悉栈的使用。掌握如何使用C语言实现栈的说明、创建以及进栈和出栈等操作。二、实验要求熟悉C语言编程。三、实验内容编写单独的初始化栈、判空、入栈和出栈以及取得栈顶元素的函数编写compute()函数，实现后缀表达式的计算，在该函数中对第一步实现的栈函数进行调用以完成计算四、实验步骤（算法）实现后缀表达式423*+42/-#的运算1.依次读入数字和运算符当读入的是数字时进栈，当读入的是运算符时出栈两次并把两个出栈的数据进行运算符所实现的运算，一直这样的操作直到所读的数据为#时，输出栈底元素即为所要计算的结果。五、程序代码#include #define error 0#define ok 1#define TRUE 1#define FALSE 0#define STACK_INIT_SIZE 100#define OVERFLOW -2#define STACKINCREMENT 10#include typedef int elemtype;#include#include#includetypedef structelemtype *base; elemtype *top;int stacksize;bds_stack;int pop(bds_stack &S,int &e)if(S.top=S.base) return error;e= * -S.top;return ok;int InitStack (bds_stack &S) S.base = (elemtype *) malloc(STACK_INIT_SIZE *sizeof(elemtype); if (!S.base) exit(OVERFLOW); S.top =S.base; S.stacksize = STACK_INIT_SIZE; return ok; int GetTop(bds_stack S,elemtype&e) if(S.top=S.base) return error; return e=*(S.top-1); /GetTopint push(bds_stack &S,int e)if(S.top-S.base=S.stacksize)S.base=(elemtype*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(elemtype);if(!S.base) exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+ = e;return ok;int compute (char A, int &k)int i=0;int x1,x2,temp, e;bds_stack bds; /定义一个栈 InitStack (bds); /初始化栈while (Ai!=#) /依次取得后缀表达式中的字符判断并操作if (0=Ai)&(Ai=9) )push(bds,Ai-0); /如果是操作数，压栈else/如果是操作符pop(bds,x2); /操作数2，出栈 pop(bds,x1); /操作数1，出栈 /计算switch (Ai)case +: temp=x1+x2;break;case -: temp=x1-x2;break;case *: temp=x1*x2;break;case /: temp=x1/x2;break;push(bds,temp); /计算结果压栈i+; /指针后移GetTop(bds,e);return k=e;int StackEmpty(bds_stack s)if(s.top=s.base)return TRUE;elsereturn FALSE;void main()char bds_hz=423*+42/-#;/后缀表达式int j;compute (bds_hz,j);coutjendl; /输出表达式结果六、实验结果（屏幕截图）七、心得体会本次实验的要求有多个，但我只做了其中的一小部分，为后缀表达式的求值。其中的中缀表达式（就是我们通常所见的）转换为后缀表达式，经过多次的实验因为不会比较运算符的优先级无法做到。我想这是因为我的动手能力还不是很好吧，还需要以后多编一些程序来锻炼自己的实