数据结构实验三课程数据结构实验名称顺序栈基本操作第页专业班级学号姓名实验日期：年月日评分一、实验目的1．熟悉并能实现栈的定义和基本操作。
2．了解和掌握栈的应用。
二、实验要求1．进行栈的基本操作时要注意栈"后进先出"的特性。
2．编写完整程序完成下面的实验内容并上机运行。
3．整理并上交实验报告。
三、实验内容1．编写程序任意输入栈长度和栈中的元素值，构造一个顺序栈，对其进行清空、销毁、入栈、出栈以及取栈顶元素操作。
2．编写程序实现表达式求值，即验证某算术表达式的正确性，若正确，则计算该算术表达式的值。
主要功能描述如下：（1）从键盘上输入表达式。
（2）分析该表达式是否合法：v1.0 可编辑可修改a) 是数字，则判断该数字的合法性。
若合法，则压入数据到堆栈中。
b) 是规定的运算符，则根据规则进行处理。
在处理过程中，将计算该表达式的值。
c) 若是其它字符，则返回错误信息。
（3）若上述处理过程中没有发现错误，则认为该表达式合法，并打印处理结果。
程序中应主要包含下面几个功能函数：l void initstack()：初始化堆栈l int Make_str()：语法检查并计算l int push_operate(int operate)：将操作码压入堆栈l int push_num(double num)：将操作数压入堆栈l int procede(int operate)：处理操作码l int change_opnd(int operate)：将字符型操作码转换成优先级l int push_opnd(int operate)：将操作码压入堆栈l int pop_opnd()：将操作码弹出堆栈l int caculate(int cur_opnd)：简单计算+，-，*，/l double pop_num()：弹出操作数四、实验步骤（描述实验步骤及中间的结果或现象。
在实验中做了什么事情，怎么做的，发生的现象和中间结果）第一题：#include <iostream>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 struct{SElemType *base; //在栈构造之前和销毁之后，base的值为NULL SElemType *top; //栈顶指针int stacksize; //当前已分配的存储空间，以元素为单位} SqStack;Status Initstack(SqStack &S)//构造一个空栈S{=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!exit(OVERFLOW);=;= STACK_INIT_SIZE;return OK;}//InitStackStatus StackEmpty(SqStack &S){if==return OK;elsereturn NO;}Status ClearStack (SqStack &S)//把S置为空{if=;return OK;}Status DsetroyStack (SqStack &S)//销毁栈S {=NULL;return OK;}Status Push(SqStack &S,SElemType e)//插入元素e为新的栈顶元素{if {=(SElemType *)realloc,+STACKINCREMENT)*sizeof(SElemType)); if(! //存储分配失败exit(OVERFLOW);=+;+=STACKINCREMENT;}*++=e;return OK;}//PushStatus Pop(SqStack &S,SElemType &c)//若栈不空，则删除S的栈顶元素，用c返回其值，并返回OK；否则返回ERROR {if==return NO;c=*;return OK;}//PopStatus GetTop(SqStack &S,SElemType &e){if ==return NO;e=*;return OK;}//GetTopint 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;!=;i++){Pop(S,c);cout<<"栈中第"<<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 *base;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(SElemType 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 change(SElemType e){int m;m=e-48;return m;}Status Initstack(SqStack &s){=(SElemType *)malloc(STACK_SIZE*sizeof(SElemType));if(!exit(OVERFLOW);=;=STACK_SIZE;return OK;}Status Stackempty(SqStack &s){if==return OK;elsereturn NO;}Status push_num(SqStack &s,int e){if {=(SElemType *)realloc,+STACKINCREMENT)*sizeof(SElemType));if(!exit(OVERFLOW);=+;+=STACKINCREMENT;}*++=e;return OK;}Status push_operate(SqStack &s,SElemType e){if {=(SElemType *)realloc,+STACKINCREMENT)*sizeof(SElemType));if(!exit(OVERFLOW);=+;+=STACKINCREMENT;}*++=e;return OK;}Status pop_operate(SqStack &s,SElemType &c){if==return NO;c=*;return OK;}Status pop_num(SqStack &s,int &c){if==return NO;c=*;return OK;}char GetTop(SqStack &s){char c;if==return NO;c=*;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=='/')s=a/b;return s;}Status In(SElemType c){if(c=='+'||c=='-'||c=='*'||c=='/'||c=='#'||c=='('||c==')') return OK;if(c>='0'&&c<='9')return NO;return -1;}char Precede(SElemType a,SElemType b){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 ' ';}char Operatecxz(){SqStack Operate,Num;char 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();continue;}if(sz==1)num=num*10+change(c);c=getchar();continue;}else{if(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_operate(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)注释掉的结果：2 不把ClearStack (S)注释掉，把栈清空：3 不把DsetroyStack(S)注释掉，即销毁栈：出现一堆乱码，说明销毁成功。