第三章 栈与队列 3.15 typedef struct{ Elemtype *base[2]; Elemtype *top[2]; }BDStacktype; //双向栈类型 Status Init_Stack(BDStacktype &tws,int m)//初始化一个大小为 m 的双向栈tws { tws.base[0]=(Elemtype*)malloc(m*sizeof(Elemtype)); tws.base[1]=tws.base[0]+m; tws.top[0]=tws.base[0]; tws.top[1]=tws.base[1]; return OK; }//Init_Stack Status push(BDStacktype &tws,int i,Elemtype x)//x 入栈,i=0 表示低端栈,i=1 表示高端栈 { if(tws.top[0]>tws.top[1]) return OVERFLOW; //注意此时的栈满条件 if(i==0) *tws.top[0]++=x; else if(i==1) *tws.top[1]--=x; else return ERROR; return OK; }//push Status pop(BDStacktype &tws,int i,Elemtype &x)//x 出栈,i=0 表示低端栈,i=1 表示高端栈 { if(i==0) { if(tws.top[0]==tws.base[0]) return OVERFLOW; x=*--tws.top[0]; } else if(i==1) { if(tws.top[1]==tws.base[1]) return OVERFLOW; x=*++tws.top[1]; } else return ERROR; return OK; }//pop 3.16 void Train_arrange(char *train)//这里用字符串 train 表示火车,'H'表示硬席,'S'表示软席 { p=train;q=train; InitStack(s); while(*p) { if(*p=='H') push(s,*p); //把'H'存入栈中 else *(q++)=*p; //把'S'调到前部 p++; } while(!StackEmpty(s)) { pop(s,c); *(q++)=c; //把'H'接在后部 } }//Train_arrange 3.17 int IsReverse()//判断输入的字符串中'&'前和'&'后部分是否为逆串,是则返回1,否则返回0 { InitStack(s); while((e=getchar())!='&') { if(e==’@’) return 0;//不允许在’&’之前出现’@’ push(s,e); } while( (e=getchar())!='@') { if(StackEmpty(s)) return 0; pop(s,c); if(e!=c) return 0; } if(!StackEmpty(s)) return 0; return 1; }//IsReverse 3.18 Status Bracket_Test(char *str)//判别表达式中小括号是否匹配 { count=0; for(p=str;*p;p++) { if(*p=='(') count++; else if(*p==')') count--; if (count<0) return ERROR; } if(count) return ERROR; //注意括号不匹配的两种情况 return OK; }//Bracket_Test 3.19 Status AllBrackets_Test(char *str)//判别表达式中三种括号是否匹配 { InitStack(s); for(p=str;*p;p++...
