顺序栈基本操作实验报告

数据结构实验三课程数据结构实验名称顺序栈基本操作第页专业班级学号姓名实验日期：年月日评分一、实验目的1．熟悉并能实现栈的定义和基本操作。2．了解和掌握栈的应用。二、实验要求1．进行栈的基本操作时要注意栈后进先出的特性。2．编写完整程序完成下面的实验内容并上机运行。3．整理并上交实验报告。三、实验内容1．编写程序任意输入栈长度和栈中的元素值，构造一个顺序栈，对其进行清空、销毁、入栈、出栈以及取栈顶元素操作。2．编写程序实现表达式求值，即验证某算术表达式的正确性，若正确，则计算该算术表达式的值。主要功能描述如下：（1）从键盘上输入表达式。（2）分析该表达式是否合法：a)是数字，则判断该数字的合法性。若合法，则压入数据到堆栈中。b)是规定的运算符，则根据规则进行处理。在处理过程中，将计算该表达式的值。c)若是其它字符，则返回错误信息。（3）若上述处理过程中没有发现错误，则认为该表达式合法，并打印处理结果。程序中应主要包含下面几个功能函数：lvoidinitstack()：初始化堆栈lintMake_str()：语法检查并计算lintpush_operate(intoperate)：将操作码压入堆栈lintpush_num(doublenum)：将操作数压入堆栈lintprocede(intoperate)：处理操作码lintchange_opnd(intoperate)：将字符型操作码转换成优先级lintpush_opnd(intoperate)：将操作码压入堆栈lintpop_opnd()：将操作码弹出堆栈lintcaculate(intcur_opnd)：简单计算+，-，*，/ldoublepop_num()：弹出操作数四、实验步骤（描述实验步骤及中间的结果或现象。在实验中做了什么事情，怎么做的，发生的现象和中间结果）第一题：#includeiostreamusingnamespacestd;#defineSTACK_INIT_SIZE100//存储空间初始分配量#defineSTACKINCREMENT10//存储空间分配增量#defineOVERFLOW-1#defineOK1#defineNO-1#defineNULL0typedefintStatus;typedefcharSElemType;typedefstruct{SElemType*base;//在栈构造之前和销毁之后，base的值为NULLSElemType*top;//栈顶指针intstacksize;//当前已分配的存储空间，以元素为单位}SqStack;StatusInitstack(SqStack&S)//构造一个空栈S{S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}//InitStackStatusStackEmpty(SqStack&S){if(S.base==S.top)returnOK;elsereturnNO;}StatusClearStack(SqStack&S)//把S置为空{if(S.base=S.top);returnOK;}StatusDsetroyStack(SqStack&S)//销毁栈S{S.base=NULL;returnOK;}StatusPush(SqStack&S,SElemTypee)//插入元素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;returnOK;}//PushStatusPop(SqStack&S,SElemType&c)//若栈不空，则删除S的栈顶元素，用c返回其值，并返回OK；否则返回ERROR{if(S.top==S.base)returnNO;c=*--S.top;returnOK;}//PopStatusGetTop(SqStack&S,SElemType&e){if(S.top==S.base)returnNO;e=*(S.top-1);returnOK;}//GetTopintmain(){SqStackS;Initstack(S);cout输入要压到栈中的元素!endl;charc;while((c=getchar())!='\n'){Push(S,c);}GetTop(S,c);cout栈顶元素为：cendl;//ClearStack(S);//DsetroyStack(S);for(inti=0;S.top!=S.base;i++){Pop(S,c);cout栈中第i+1元素的值:;coutcendl;}return0;}第二题：#includeiostreamusingnamespacestd;#defineSTACK_SIZE100#defineSTACKINCREMENT10#defineOVERFLOW-1#defineOK1#defineNO0typedefintStatus;typedefcharSElemType;typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;intmain(){charGetTop(SqStack&s);StatusInitstack(SqStack&s);Statuspush_operate(SqStack&s,SElemTypee);Statuspush_num(SqStack&s,inte);StatusStackempty(SqStack&s);Statuspop_num(SqStack&s,int&c);Statuspushoperate(SElemTypeoperate);Statuspushnum(SElemTypenum);Statuscaculate(SElemTypea,SElemTypeoperate,SElemTypeb);Statuspop_operate(SqStack&s,SElemType&c);Statuschange(SElemTypee);charPrecede(SElemTypea,SElemTypeb);charOperatecxz();intm;m=Operatecxz();coutmendl;return0;}Statuschange(SElemTypee){intm;m=e-48;returnm;}StatusInitstack(SqStack&s){s.base=(SElemType*)malloc(STACK_SIZE*sizeof(SElemType));if(!s.base)exit(OVERFLOW);s.top=s.base;s.stacksize=STACK_SIZE;returnOK;}StatusStackempty(SqStack&s){if(s.base==s.top)returnOK;elsereturnNO;}Statuspush_num(SqStack&s,inte){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;returnOK;}Statuspush_operate(SqStack&s,SElemTypee){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;returnOK;}Statuspop_operate(SqStack&s,SElemType&c){if(s.top==s.base)returnNO;c=*--s.top;returnOK;}Statuspop_num(SqStack&s,int&c){if(s.top==s.base)returnNO;c=*--s.top;returnOK;}charGetTop(SqStack&s){charc;if(s.top==s.base)returnNO;c=*(s.top-1);returnc;}Statuscaculate(inta,SElemTypeoperate,intb){ints;if(operate=='+')s=a+b;if(operate=='-')s=a-b;if(operate=='*')s=a*b;if(operate=='/')s=a/b;returns;}StatusIn(SElemTypec){if(c=='+'||c=='-'||c=='*'||c=='/'||c=='#'||c=='('||c==')')returnOK;if(c='0'&&c='9')returnNO;return-1;}charPrecede(SElemTypea,SElemTypeb){if(a=='+'||a=='-'){if(b=='+'||b=='-'||b==')'||b=='#')return'';if(b=='*'||b=='/'||b=='(')return'';}if(a=='*'||a=='/'){if(b=='+'||b=='-'||b==')'||b=='*'||b=='/'||b=='#')return'';if(b=='(')return'';}if(a=='('){if(b==')')return'=';if(b=='+'||b=='-'||b=='*'||b=='/')return'';if(b=='#')return'';}if(a==')'){if(b==')')return'';if(b=='+'||b=='-'||b=='*'||b=='/'||b=='('||b=='#')return'';}if(a=='#'){if(b=='#')return'=';if(b=='+'||b=='-'||b=='*'||b=='/'||b=='(')return'';if(b==')')return'';}return'';}charOperatecxz(){SqStackOperate,Num;charc,e,x;intnum,a,b,flat=1,sz=0;Initstack(Operate);push_operate(Operate,'#');Initstack(Num);c=getchar();while(c!='#'||GetTop(Operate)!='#'){if(In(c)==-1){coutinputerror!endl;flat=0;break;}if(In(c)!=1){if(sz==0){num=change(c);sz=1;c=getchar(