2023年顺序栈基本操作实验报告

数据结构实验三课程数据结构实验名称顺序栈基本操作第页专业班级学号姓名实验日期：年月日评分一、实验目的.熟悉并能实现栈的定义和基本操作。.了解和掌握栈的应用。二、实验规定.进行栈的基本操作时要注意栈"后进先出”的特性。.编写完整程序完毕下面的实验内容并上机运营。.整理并上交实验报告。三、实验内容.编写程序任意输入栈长度和栈中的元素值，构造一个顺序栈，对其进行清空、销毁、入栈、出栈以及取栈顶元素操作。.编写程序实现表达式求值，即验证某算术表达式的对的性，若对的，则计算该算术表达式的值。重要功能描述如下：(1)从键盘上输入表达式。。if(s.top==s.base)®returnNO;c=*-s.top;oreturnOK；)Statuspop_nurn(SqStack&sjnt&c)(»if(s.top==s.base)«rcturnNO；3c=*—s.top；。returnOK；}charGetTop(SqStack&s)(«charc;，if(s.top==s.base)»returnN0;。c=*(s.top-1);returnc;)Statuscaculate(inta,SElemTypeoperate,intb)(ints;A『(operate=='+')。。s=a+b;if(operate=='-')os=a-b;if(operate==**')gs=a*b;if(operate=='/')»s=a/b；returns;)StatusIn(SE1emTypec){，if(c==，+'||c==,-'||c=='*'||c=='/'||c=='#'I|c==zCI|c==')')®returnOK；«if(c>='Oz&&c<=9')returnNO;return-1；}charPrccede(SElemTypea,SElemTypeb)(»if(a=='4->||a=--'){。if(b=='+l|b=='-'||b==')/||b==z#•)®return痴f(b=='*'||b==,/'I|b=='C)woreturn'<*；alif(a==,*'||a=='/')°{if<b=='+'|Ib==1-'1Ib==')'||b=='*'||b==7,||b==/#')®returnif(b=='(')»®returnz<';。}if(a=='(')°{(b==y)®rcturn-*;“if(b==，+'||b==,-'|Ib==,*/|Ib==，n。retumz<';if(b==z#')greturn'-if(a=='),)0{qf(b==')')grcturn',；®if(b==，+，||b=='-'|Ib==，*'l|b==7/||b=='('||b=='#')。return'>'；)»if(a=='#'){f(b=='#')return',°if(b=='+，||b=='-，||b=="*'IIb=='/z||b=='(,)return；。if(b==')')。eturn'Ieturn}charOperatecxz()(SqStackOpcratc,Num；acharc,e,x；intnum,a,b,flat=l,sz=0:4nitstack(Operate)；叩ush_operate(Operate,'#');QInitstack(Num)；ac=getcliar()；awhile(c!=,#*||GetTop(Operate)!='#*)(。if(In(c)==—1)0{。。。cout<<"inputerror!,,«end1;41at=0；gbreak;n(c)!=1)if(sz==0)

。num=change(c);00。num=change(c);，。sz=1;。。c=getchar();。continue；0Igif(sz==1)。num=num*1O+change(c);«。c=getchar();^continue;00}。eIseif(sz==1)gpush_num(Num,num);8<>SZ=0；x=GetTop(Operate);。switch(Prcccde(GetTop(Opcrate),c))0o|。case'<'：00{。®push_operate(0perate,c)；。c=getchar()；g。break;0«)case。叩op_operate(Operate,e);c=getchar();greak;°}。«case°{。gpop_num(Num,a);。pop_opcratc(Opcrate,e)；a^Mpop_num(Num,b)；g。。push_num(Num,caculate(b,e,a));g。break;8)00)°)pop_operate(Operate,e);if(e!='#')flat=O;。if(f1at==l){opop_num(Num»a);returna;}f(flat==0)»relurn0;

五.实验结果与讨论(描述最终得到的结果，并进行分析说明，也许的误差因素)第一题:1把主函数中的C1earStack(S);DsetroyStack(S)注释掉的结果:\Docu>entsandSetti输入要压到栈中的元素，65789栈顶元素为：9榜中第远素的值：9装山第\Docu>entsandSetti输入要压到栈中的元素，65789栈顶元素为：9榜中第远素的值：9装山第2元素的

噗匚噫3无案的：8：7Pressanykeytocontinue要23元s八45顶口口口口口口es输68栈栈栈栈磬栈pr厅元元元元元元tyekyna2不把ClearStack(S)注释掉，把栈清空:K-C:\DocuaentsandSetti葩人要压到栈中的元素？K-C:\DocuaentsandSetti葩人要压到栈中的元素？3654218隹顶元素为：8Pressanykeytocontinue软**C:\Docu*entsandSettii畅入要压到彘尾悬?4502150展顶元素为：。pi'essanykeytocontinue3不把DsetroyStack(S)注释掉，即销毁栈:)ocuBentsandSettings\TEBP\臬面\Debug\Cpp2.exe”••«•••>•••>••••••«•«••••••••••>«••:••«•••>•••>••••••«•«••••••••••>«••:>••••«••••••值值jsyffi值值值值值值值®!^值值值值值值值值值值值兀元元元元元元元元元元元元元元元元元元元元元元元SU0000000000SS8000000000444444444444444444444444第奔第一中.聿生量第第第第管童隽隽«%%量第第第弟弟-♦♦♦♦♦-»・♦f.♦一一一一一一-一-•-♦♦♦♦♦♦♦♦・f・♦T一♦一一一一一一一一.戈戋恨戋戈关爱戈戈浅戈戈怪飞戋怪怪弋发注戈浅戈提••«•••>•••>••••••«•«••••••••••>«••:••«•••>•••>••••••«•«••••••••••>«••:>••••«••••••值值jsyffi值值值值值值值®!^值值值值值值值值值值值兀元元元元元元元元元元元元元元元元元元元元元元元SU0000000000SS8000000000444444444444444444444444第奔第一中.聿生量第第第第管童隽隽«%%量第第第弟弟-♦♦♦♦♦-»・♦f.♦一一一一一一-一-•-♦♦♦♦♦♦♦♦・f・♦T一♦一一一一一一一一.戈戋恨戋戈关爱戈戈浅戈戈怪飞戋怪怪弋发注戈浅戈提H；现•堆乱码，说明销毁成功。第二题的输出:1正常输入表达式则输出:前,D:\课件'数据结构\实险2\Debug\shiyancI<12+2>*9#bL26pressanykeytocontinue.2假如输入的表达式犯错则输出:苏，D:\课件'数据结构'实套21Debugr...inputerror?bPressanykeytocontinue.六.实验总结:1在写主函数时，假如是用voidmain的形式，那么可以不用有返【可值，假如是intmain或|statusmain的话，要有返回值，既末尾要有return语句。2有时候写的没有出现问题，但运营的结果是Pressanukeytocontinue。程序肯定有错，但为什么会出现这种问题呢。3分号的忘掉那还是很经常的，要加强注意。4原本把CearStack(S);DsetroyStack(S)放在for循环之后，检查不出C1earStack(S);DsetroyStack(S)的函数是否对的。把它们for循环之前,GetTop(S,c)语句之后，再运用注释等的，就可以很明显的看出栈是否被清空或销毁。5在做表达式的计算的时候一定要注意何时入栈何时出栈。假如如栈与出栈的情况判断不清楚就无法得出答案。6在定义栈的时候Num中的元素最佳使用int类型的而不是char类型的。由于这样会简化char0peratecxz()的计算复杂度。7对于表达式的判错情况，根据题目中的提醒对每次读入的字符进行判断。8对于不是个位数的计算,一方面用了个Statuschange(SEIemTypee)m=e-48；returnm;}把每个字符转化成int型，然后再用sz作为标记直到读入的数不是数字为止。此时再将之前读入的数num压入Num栈中。9对于优先级的判断按照书上给定的表格进行建立关系。注意优先级的判断为这个实验最为关键的，也是最需要细心的地方。只要有一个地方弄错，将导致整个实验都犯错。(2)分析该表达式是否合法:a)是数字，则判断该数字的合法性。若合法，则压入数据到堆栈中。b)是规定的运算符，则根据规则进行解决。在解决过程中，将计算该表达式的值。c)若是其它字符，则返回错误信息。(3)若上述解决过程中没有发现错误，则认为该表达式合法，并打印解决结果。程序中应重要包含下面几个功能函数：Ivoidinitstack()：初始化堆栈IintMake_str()：语法检资并计算Iintpush_operale(int。perate):将操作码压入堆栈Iintpush_num(doubIenum):将操作数压入堆栈Iintprocede(intoperate):解决操作码Iintchange_opnd(intoperate)：将字符型操作码转换成优先级Iintpush_opnd(intoperate)：将操作码压入堆栈Iintpop_opnd()：将操作码弹出堆栈1intcaculate(intcur_opnd)：简朴计算*,/Idoub1epop_num()：弹出操作数四、实验环节(描述实验环节及中间的结果或现象。在实验中做了什么事情，怎么做的，发生的现象和中间结果)第一题：#include<iostream>usingnamespacestd;#defineSTACK_INIT_SIZE100〃存储空间初始分派量#defineSTACKINCREMENT10〃存储空间分派增量#defineOVERFLOW-1defineOK1defineNO-1defineNULL0typedefintStatus;typcdefcharSEIemType;typedefstruct(SEiemType*base;〃在栈构造之前和销毁之后，base的值为NULLSElemType*top;//栈顶指针intstacksize；//当前已分派的存储空间,以元素为单位}SqStack；StatusInitstack(SqStack&S)〃构造一个空栈S(S.base=(SElemType*)malloc(STACK」NIT_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;}StatusC1earStack(SqStack&S)//把S置为空(°if(S.base=S.top);^returnOK；)StatusDsetroyStack(SqStack&S)〃销毁栈S{oS.base=NULL;returnOK;}StatusPush(SqStack&S,SE1emTypee)//插入元素e为新的栈顶元素(if(S.top—S.base>=S.stacksize)(S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemTypc));if(!S.base)//存储分派失败cxit(OVERFLOW);S.top=S.base+S.stacksize；S.stacksize+=STACKINCREMENT;*S.top++=e;returnOK;}//PushStatusPop(SqStack&S,SElemType&c)〃若栈不空，则删除S的栈顶元素用c返回其值,并返回OK：否则返回ERROR(f(S.top==S.base)oreturnN0；c=*-S.top：«return0K;}//PopStatusGetTop(SqStack&S,SElemType&e)(if(S.top==S.base)^returnNO;e=*(S.lop-1);oreturnOK:}//GetToPintmain()(SqStackS；Initstack(S);coul<<"输入要压到栈中的元素厂vvendl;charc;while((c=getchar())!='\n')Push(S,c)；)GetTop(S,c);◎coutvv"栈顶元素为："VvcV«ndl;//C1carStack(S);//DseiroySlack(S);for(inti=0;S.top!=S.base；i++)°{3Pop(S,c);。co栈中第"«i+1元素的值：”；cout<<c<<endl;01return0；}第二题：#include<iostream>usingnamespacestd;#defineSTACK.SIZE100defineSTACKINCREMENT10defineOVERFLOW-1defineOK1#defineNOOtypcdcfintStatus;typedefcharSE1emType；typedefstructSE1emType*base;«SEIemType*top；intstacksize;}SqStack;intmain()(charGctTop(SqStack&s)；aStatusInitstack(SqStack&s)；Statuspush_operate(SqStack&s,SElemTypee)；Statuspush_num(SqStack&$,inte);◎StatusStackempty(SqStack&s);Statuspop_num(SqStack&s,int&c)；§Statuspushoperate(SElemTypeoperate)：^Statuspushnum(SElcmTypcnum);aStatuscacu1ate(SElemTypea,SElemTypeoperate,SEIemTypeb);Statuspop_operatc(SqStack&s,SEiemTypc&c);«Statuschange(SElemTypee);ocharPrecede(SE1emTypea,SE1emTypeb);«charOperatecxz();intm;m=Opcratecxz();acout<<m<<end1;oreturn0;Statuschange(SE1emTypee)intm;m=e—48;returnm：)StatusInitstack(SqStack&s)(s.base=(SElemType*)malloc(STACK_SIZE*sizcof(SE1cmTyp