栈的简单应用：数制转换·括号的匹配检验·行编辑·迷宫求解·表达式求值·递归调用

柔情只为你懂 2023-07-09 14:27 54阅读 0赞

**ps：所用代码为伪代码**

顺序栈：

#define STACK_INIT_SIZE 100
    #define STACKINCREMENT 10
    typedef struct{
    	SElemType *base;
    	SElemType *top;
    	int stacksize;
    }SqStack;

1.数制转换（10进制→8进制）  
问题本身（保留数据）就有后进先出的特点，所以用栈；抓住本质选择算法，这若使用数组则是很复杂了

void conversion(){
    	InitStack(S);
    	scanf(N);
    	while(N){
    		Push(S,N%8,);
    		N/=8;
    	}
    	while(!StackEmpty){
    		Pop(S,e);
    		printf(e);
    	}
    }

2.括号的匹配检验  
最后一个左括号的期待最急迫，率先匹配右括弧，符合栈后进先出的特性  
先让一群左括号都进栈，再用右括号一个一个判断，匹配成功则出栈；要是栈空了则说明成功，否则匹配失败

Status matching(string &exp){
    	int state=1; //状态参量，为1成功，为0错误
    	while(i<=Length(exp)&&state){
    		switch of exp[i]{
    		case 左括弧：{Push(S,exp[i]);i++;break; }
    		case 右括弧：{if(NOT StackEmpty(S)&&GetTop(S)=左括弧) {Pop(S,e);i++;}
    		else{state=0;}
    		break;
    		}
    		 if(StackEmpty(S)&&state) return OK;
    }

3.行编辑程序  
每行一个缓冲区，用一个栈

while(!EOF&&ch!='\n') //EOF为全文结束符
    { switch(ch){
    	case'#':Pop(S,e);break;
    	case'@':ClearStack(S);break;
    	default:Push(S,e);break;
    }
       ch=getchar();
    } 
        ClearStack(S);

4.计算机的迷宫求解  
探索东南西北能否走，可行则纳入路径，不可行则一步步返回，push；符合栈特性，保存的最后一个元素，最先出来，后入先出

typedef struct{
    	int ord;//通道块在路径上的序号
    	PoseType seat;// 通单块在迷宫中的坐标
    	int di;//下一步的方向 
    }SElemType;
    Status MazePath(MazeType maze,PosType start,PosType end){
    	InitStack(S);
    	curpos=start;
    	curstep=1;
    	do{
    		if(pass(curpos)) //如果当前位置可通过
    		{FootPrint(curpos);//留下足迹
    		e=(curstep,curpos,1);
    		Push(S,e);//加入路径
    		if(curpos== end) return (TURE); //到达终点
    		curpos=NextPos(curpos,1);
    		curstep++;//探索下一步 
    	}
    	else if(!StackEmpty(S)){ //若不为空栈，即前面还有足迹 
    		Pop(S,e);
    		while(e.di== 4&&!StackEmpty(S)){
    		MakePrint(e.seat);Pop(S,e); 
    	}
    	if(e.di<4){
    		e.di++; Push(S,e);//换个方向探索 
    		curpos=NextPos(e.seat e.di)
    	}
    	while(!StackEmpty(S));
    	return (FALSE);
    }

5.表达式求值  
建立运算符栈，\#压在栈底，如果进来操作数，直接发给后缀式；如果进来运算符，如果进来的运算符优先级低（小），则让底下大的那个运算符出去，进入后缀式，否则继续压入栈；当两个括弧都入栈时，表示表达式完成，先入后出，出去到后缀式；由此组成后缀式

Operand EvaluateExpression(){
    	InitStack(OPND);//操作数
    	c=getchar();
    	InitStack(SIGN);//运算符
    	Push(S,'#');
    	while(c!='#')//以第二个#为结束符
    	{if(Is(C,OPND)) { //如果是操作数 
    	Push(OPND,c);
    	c=getchar();
    	}//if
    	else
    	switch(Precede(GetTop(SIGN,c))){
    		case '<': //新进来的元素c的优先级高
    		case '=':
    		case '(':Push(SIGN,c);c=getchar();break;  
    		case ')':Pop(SIGN,x); Push(OPND,x);c=getchar();break; //脱括号,把两个括号中间的一串x放进操作数的栈 
    		case '>':Pop(SIGN,former);Push(SIGN,c);Pop(SIGN,latter);c=getchar();break; 
    		}//switch
    	}//while 
    }

6.递归调用  
递归函数单独成栈，每一次的递归信息参数为一条工作记录仪，当前活动情况在栈顶，当前环境指针为栈顶指针  
汉诺塔问题

void Hanoi(int n,char x,char y,char z){
    	if(n==1) Move(x,1,z);
    	else {
    		Hanoi(n-1,x,z,y);
    		Move(x,n,z);
    		Hanoi(n-1,y,x,z);
    	}
    }