顺序栈基本操作实验报告记录

1、顺序栈基本操作实验报告记录作者:日期:数据结构实验三课程数据结构实验名称 顺序栈基本操作 第 页专业 班级 学号姓名实验日期： 年 月日评分一、实验目的1 .熟悉并能实现栈的定义和基本操作。2 . 了解和掌握栈的应用。二、实验要求1 .进行栈的基本操作时要注意栈 "后进先出"的特性。2 .编写完整程序完成下面的实验内容并上机运行。3 .整理并上交实验报告。三、实验内容1 .编写程序任意输入栈长度和栈中的元素值，构造一个顺序栈，对其进行清空、销毁、入栈、出栈 以及取栈顶元素操作。2 .编写程序实现表达式求值，即验证某算术表达式的正确性，若正确，则计算该算术表达式的值。主要功能

2、描述如下：(1)从键盘上输入表达式。(2)分析该表达式是否合法：? a)是数字，则判断该数字的合法性。若合法，则压入数据到堆栈中。? b)是规定的运算符，则根据规则进行处理。在处理过程中，将计算该表达式的值。? c)若是其它字符，则返回错误信息。(3)若上述处理过程中没有发现错误，则认为该表达式合法，并打印处理结果。程序中应主要包含下面几个功能函数：? l void initstack():初始化堆栈? l int Make_str():语法检查并计算? l int push_operate(int operate):将操作码压入堆栈? l int push_num(double num):将

3、操作数压入堆栈? l int procede(int operate) : 处理操作码? l int change_opnd(int operate):将字符型操作码转换成优先级? l int push_opnd(int operate):将操作码压入堆栈? l int pop_opnd():将操作码弹出堆栈? l int caculate(intcur_opnd):简单计算 +, -, *, /? l double pop_num():弹出操作数四、实验步骤发生的现象和中(描述实验步骤及中间的结果或现象。在实验中做了什么事情， 怎么做的,间结果)第一题：#include <iostre

4、am>using namespace std;#define STACK_INIT_SIZE 100存储空间初始分配量#define STACKINCREMENT 10存储空间分配增量#define OVERFLOW -1#define OK 1#define NO -1#define NULL 0typedef int Status;typedef char SElemType;typedef structSElemType *base; /在栈构造之前和销毁之后，base的值为NULLSElemType *top;栈顶指针int stacksize;当前已分配的存储空间，以元素为单位

5、 SqStack;Status Initstack(SqStack &S)/ 构造一个空栈 SS.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize= STACK_INIT_SIZE;return OK;/InitStackStatus StackEmpty(SqStack &S)if(S.base=S.top)return OK;elsereturn NO; Status ClearStack (SqStack

6、 &S)把 S 置为空 if(S.base=S.top);return OK;Status DsetroyStack (SqStack &S)/ 销毁栈 S S.base=NULL;return OK; Status Push(SqStack &S,SElemType e)插入元素e为新的栈顶元素 if (S.top-S.base>=S.stacksize)S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base) 存储分配失败exit(

7、OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;PushStatus Pop(SqStack &S,SElemType &c)若栈不空，则删除 S的栈顶元素，用c返回其值，并返回 OK;否则返回ERROR if(S.top=S.base)return NO;c=*-S.top;return OK;/PopStatus GetTop(SqStack &S,SElemType &e) if (S.top=S.base)return NO;e=*(S.

8、top-1); return OK;/GetTop int main() SqStack S;Initstack(S);cout<<"输入要压到栈中的元素 ！"<<endl;char c;while(c=getchar()!='n')Push(S,c);GetTop(S,c);cout<<"栈顶元素为："<<c<<endl;/ClearStack (S);DsetroyStack(S);for(int i=0;S.top!=S.base;i+)Pop(S,c);cout<&

9、lt;"栈中第"<<i+1<<"元素的值:" cout<<c<<endl; return 0;第二题：#include<iostream>using namespace std;#define STACK_SIZE 100#define STACKINCREMENT 10#define OVERFLOW -1#define OK 1#define NO 0typedef int Status;typedef char SElemType;typedef struct SElemType *bas

10、e;SElemType *top;int stacksize;SqStack; int main() char GetTop(SqStack &s);Status Initstack(SqStack &s);Status push_operate(SqStack &s,SElemType e);Status push_num(SqStack &s,int e);Status Stackempty(SqStack &s);Status pop_num(SqStack &s,int &c);Status pushoperate(SElemTy

11、pe operate);Status pushnum(SElemType num);Status caculate(SElemType a,SElemType operate,SElemType b);Status pop_operate(SqStack &s,SElemType &c);Status change(SElemType e);char Precede(SElemType a,SElemType b);char Operatecxz();int m;m=Operatecxz();cout<<m<<endl;return 0;Status c

12、hange(SElemType e)int m;m=e-48;return m;Status Initstack(SqStack &s)s.base=(SElemType *)malloc(STACK_SIZE*sizeof(SElemType);if(!s.base)exit(OVERFLOW);s.top=s.base;s.stacksize=STACK_SIZE;return OK;Status Stackempty(SqStack &s)if(s.base=s.top)return OK;elsereturn NO;Status push_num(SqStack &am

13、p;s,int e)if(s.top-s.base>=s.stacksize)s.base=(SElemType*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!s.base)exit(OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;*s.top+=e;return OK;Status push_operate(SqStack &s,SElemType e)if(s.top-s.base>=s.stacksize

14、)s.base=(SElemType*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!s.base)exit(OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;*s.top+=e;return OK;Status pop_operate(SqStack &s,SElemType &c)if(s.top=s.base)return NO;c=*-s.top;return OK;Status pop_num(SqStack

15、 &s,int &c)if(s.top=s.base)return NO;c=*-s.top;return OK;char GetTop(SqStack &s)char c;if(s.top=s.base)return NO;c=*(s.top-1);return c;)Status caculate(int a,SElemType operate,int b)(int s;if(operate='+')s=a+b;if(operate='-')s=a-b;if(operate='*')s=a*b;if(operate=&

16、#39;/')s=a/b;return s;)Status In(SElemType c)(if(c='+'|c='-'|c='*'11c='/'11c='#'|c='('|c=')') return OK;if(c>='0'&&c<='9')return NO;return -1;)char Precede(SElemType a,SElemType b)(if(a='+'|a='-'

17、;)(if(b='+'|b='-'|b=')'|b='#')return '>'if(b='*'|b=7'|b='(') return '<')if(a='*'11a='/')(if(b='+'|b='-'|b=')'|b='*'|b='/'|b='#') return '>'if(b='(&

18、#39;)return '<')if(a='(')(if(b=')')return '='if(b='+'|b='-'|b='*'|b='/')return '<'if(b='#') return '')if(a=')')(if(b=')')return ''if(b='+'|b='-'|b='*'11b='

19、;/'|b='('|b='#') return '>')if(a='#')(if(b='#')return '='if(b='+'|b='-'|b='*'|b='/'|b='(')return '<'if(b=')') return '')return '')char Operatecxz()(SqStack Operate,Num;ch

20、ar c,e,x;int num,a,b,flat=1,sz=0;Initstack(Operate);push_operate(Operate,'#');Initstack(Num);c=getchar();while(c!='#'|GetTop(Operate)!='#')(if(In(c)=-1)(cout<<"input error!"<<endl;flat=0;break;)if(In(c)!=1)(if(sz=0)(num=change(c);sz=1;c=getchar();continu

21、e;if(sz=1)num=num*10+change(c);c=getchar();continue;elseif(sz=1)push_num(Num,num);sz=0;x=GetTop(Operate);switch(Precede(GetTop(Operate),c)case '<':push_operate(Operate,c);c=getchar();break;case '=':pop_operate(Operate,e);c=getchar();break;case '>':pop_num(Num,a);pop_ope

22、rate(Operate,e);pop_num(Num,b);push_num(Num,caculate(b,e,a); break;pop_operate(Operate,e);if(e!='#')flat=0;if(flat=1)pop_num(Num,a);return a;if(flat=0)return 0;五.实验结果与讨论(描述最终得到的结果，并进行分析说明，可能的误差原因)第一题：1把主函数中的 ClearStack (S);DsetroyStack(S)注释掉的结果:3 *C: XDocniaeiit s and Sett!f-兀mite< : '

23、; 口一 山B宣言 j1B喧iMt 3 y Jp T J&n TTe2J-/I I元元元元元”要23元 WWW 入却顶口 口口 口口口 1 8殳生,岩4m 一 : 口 一1KF.M值道宜七 JJ J-3- e黎元元元一要L兀ww- 入7S顶口出口口口"C:Docu»ents and Setti4502150族顶元素为, 0nJr*esG ani/ key to c n t in ub2不把ClearStack (S)注释掉，把栈清空:翁入要压到栈中的元素？ I&54218 戋顶元素为；a>eszs any key to continue3不把DsetroyStack(S)注释掉，即销毁栈:Cpp2. MB元兀JL元元击H元元元元元元兀元元兀元元元元一7r -67v¥Hl234 5K?B»Hl234s&7B9 百鬻M皿嚏的嚣得F嚷必06北曹h.2 墓方当，M梵W.U或力 力RH&-a1*磬q21, rrUHUJ口