Application of stack

1、 Maze solution

typedef struct{
    
	int ord;		// Channel block on path ‘ Serial number ’ 
	PosType seat;	// Channel block in maze ‘ coordinates ’ 
	int di;			// From this channel block to the next channel block “ Direction  ” 
}SElemType;			// Element type of stack  
 Status MazePath(MazeType maze,PosType start,PosType end)
{
    
 // If labyrinth maze From entry in start Export to end The passage of , Find a stack （ From the bottom of the stack to the top of the stack ）, And back to TRUE, Otherwise return to FALSE 
	InitStack(S);curpos=start;// Set up ' The current position ' by ‘ Entrance location ’ 
	curstep=1;		// The first step of exploration  
	do{
    
		if(Pass(curpos)){
    	// The current position can be through , That is, the passage you have never been to  
			FootPrint(curpos);// Leaving footprints  
			e=(curstep,curpos,1);
			Push(S,e);// Join the path  
			if(curpos==end) return (TRUE);// Reach the end point  
			curpos=NextPos(curpos,1);// The next location is the East neighbor of the current location  
			curstep++;// Explore the next step  
		}
		else{
    
			if(!StackEmpty(S)){
    
				Pop(S,e);
				while(e.di==4&&!StackEmpty(S)){
    
					MarkPrint(e.seat);Pop(S,e);// Leave a mark that cannot be passed , And take a step back  
				}
				if(e.di<4){
    
					e.di++;Push(S,e);// Explore in another direction  
					curPos=NextPos(e.seat,e.di);// Set the current position as an adjacent block in the new direction  
				}
			}
		}
	}while(!StackEmpty(S));
	return(FALSE);  
} 
  

2、 Expression evaluation

OperandType EvaluateExpression(){
    
// Operator first algorithm for evaluating arithmetic expressions .OPTR and OPND They are operator stack and operand stack 
//OP Operator set  
	InitStack(OPTR);Push(OPTR,'#');
	InitStack(OPND);c=getchar();
	while(c!='#'||GetTop(OPTR)!='#'){
    
		if(!In(c,OP)){
    
			Push(OPND,c);
			c=getchar();// If it's not an operator, it's on the stack  
		}
		else
			switch(Precede(GetTop(OPTR),c)){
    
				case '<':// Stack top element has low priority  
					Push(OPTR,c);c=getchar();
					break;
				case '=':// Remove parentheses and receive the next character  
					Pop(OPTR,x);c=getchar();
					break;
				case '>':// Back off the stack and put the operation result on the stack  
					Pop(OPTR,theta);
					Pop(OPND,b);Pop(OPND,a);
					Push(OPND,Operate(a,theta,b));
					break;
			}
	} 
} 
return GetTop(OPND);

3、Hanoi problem

void hanoi(int n,char x,char y,char z)
{
    // Put the tower x The upper diameter is numbered from small to large and from top to bottom 1 to n Of n A disc is moved to the tower according to the rules z On ,y It can be used as an auxiliary tower  
// Moving operation move(x,n,z) Can be defined as (c Yes, the initial value is 0 Global variable of , Count the movement ) 
	if(n==1)
		move(x,1,z);// Will be numbered as 1 The disc from x Move to z 
	else{
    
		hanoi(n-1,x,z,y);// take x The above number is 1 to n-1 Move your disc to y,z As an auxiliary tower  
		move(x,n,z);// Will be numbered as n The disc from x Move to z 
		hanoi(n-1,y,x,z);// take y The above number is 1 to n-1 Move your disc to z,x As an auxiliary tower  
	}
 }