北理工数据结构实验报告

专业资料整理分享

typedef struct{ int *base; int *top; int stacksize;

}SqStack2; //定义操作数栈数据类型 SqStack1 OPTR; //声明运算符栈 SqStack2 OPND; //声明操作数栈 (2)、操作算法设计

Status InitStack1(SqStack1 &S){ //构造运算符栈 S.base=(char

*)malloc(STACK_INIT_SIZE*sizeof(char));

//申请空间

if(!S.base)exit(OVERFLOW); //存储分配失败 S.top=S.base;

S.stacksize=STACK_INIT_SIZE; return OK; }//InitStack1

Status InitStack2(SqStack2 &S){ //构造操作数栈

S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int)); //申请空间

完美WORD格式编辑

专业资料整理分享

if(!S.base)exit(OVERFLOW); //存储分配失败 S.top=S.base;

S.stacksize=STACK_INIT_SIZE; return OK; }//InitStack2

char GetTop1(SqStack1 S){ //取得运算符栈的栈顶元素 char e;

if(S.top==S.base) return ERROR; //栈空 e=*(S.top-1); return e; }//GetTop1

int GetTop2(SqStack2 S){ //取得操作数栈的栈顶元素 int e;

if(S.top==S.base) return ERROR; //栈空 e=*(S.top-1); return e; }//GetTop2

Status Push1(SqStack1 &S,char e){ //插入元素e为运算符栈的栈顶元素

if(S.top-S.base>=S.stacksize){//栈满，追加存储空间

完美WORD格式编辑

专业资料整理分享

S.base=(char*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char));

if(!S.base) exit(OVERFLOW);//存储分配失败 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; }

*S.top++=e; return OK; }//Push1

Status Push2(SqStack2 &S,int e){ //插入元素e为操作数栈的栈顶元素

if(S.top-S.base>=S.stacksize){ //栈满，追加存储空间

S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int));

if(!S.base) exit(OVERFLOW); //存储分配失败 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; }

*S.top++=e; return OK; }//Push2

完美WORD格式编辑

专业资料整理分享

Status Pop1(SqStack1 &S,char &e){ //删除表达式栈的栈顶元素并用e返回 if(S.top==S.base) return ERROR; //栈空 e=*--S.top; return OK; }//Pop1

Status Pop2(SqStack2 &S,int &e){ //删除表达式栈的栈顶元素并用e返回 if(S.top==S.base) return ERROR; //栈空 e=*--S.top; return OK; }//Pop2

Status In(int m,char a[]){

//判断m若是运算符，返回TRUE，否则返回FALSE for(int n=0;a[n]!='\\0';n++) if(m==a[n]) return TRUE; return FALSE; }//In

char Precede(char m,char n){ //判断m与n的优先级 switch(m){ case'+':

完美WORD格式编辑

专业资料整理分享

case'-':

if(n=='+'||n=='-'||n==')'||n=='=') return '>';

else return '<';break; case'*': case'/': case'^': case'%': if(n=='(') return '<';

else return '>';break; case'(': if(n==')') return '='; else if(n=='=') return ERROR; else return '<';break; case')': if(n=='(') return ERROR; else return '>';break; case'=':

完美WORD格式编辑