データ構造学習ノート---スタックの応用例

1.引用
本文は主にスタックのいくつかの応用を説明する:(1)迷宮解(2)式の評価(3)スタックと再帰--hanoi塔(4)括弧のマッチング
2.迷宮解
2.1解法1

#include <stdio.h>

// test 
#if 0

#define 	MAZE_COLUMN			7		//      
#define 	MAZE_ROW			7		//      

//        2      ，  0          
int m[MAZE_ROW][MAZE_COLUMN] = {
									{2, 2, 2, 2, 2, 2, 2}, 
									{2, 0, 0, 0, 0, 0, 2}, 
									{2, 0, 2, 0, 2, 0, 2}, 
									{2, 0, 0, 2, 0, 2, 2}, 
									{2, 2, 0, 2, 0, 2, 2}, 
									{2, 0, 0, 0, 0, 0, 2}, 
									{2, 2, 2, 2, 2, 2, 2}	
				  			    };
#else
	
#define 	MAZE_COLUMN			5		//      
#define 	MAZE_ROW			5		//      

//        2      ，  0          
int m[MAZE_ROW][MAZE_COLUMN] = {
									{2, 2, 2, 2, 2}, 
									{2, 0, 0, 0, 2}, 
									{2, 0, 2, 0, 2}, 
									{2, 0, 0, 0, 2}, 
									{2, 2, 2, 2, 2}	
				  			    };
#endif

struct PosType //         
{
   	int x; //   
   	int y; //   
};

 

PosType 	begin,end;  //        ,    
int 		curstep=1; 	//     ，  (    ) 1

//       (m  )
void Print()
{ 
  	int i, j;
  	for(i=0; i<MAZE_ROW; i++)
  	{
    	for(j=0; j<MAZE_COLUMN; j++)
      	printf("%3d", m[i][j]);
    	printf("
");
  	}
}


//      cur，    curstep     
void try_path(PosType cur, int curstep)
{
	int i;
	PosType next; 	//      
	PosType direc[4] = {{0,1}, {1,0}, {0,-1}, {-1,0}};  // {   ，   }，            
	
	//              
	for (i = 0; i <= 3; i++)  
	{
		//       ，       
		next.x = cur.x + direc[i].x;
		next.y = cur.y + direc[i].y;

		if (m[next.x][next.y] == 0)  //         
		{
			m[next.x][next.y] = ++curstep;
			if (next.x != end.x || next.y != end.y) //       
				try_path(next, curstep);
			else //     
			{
				Print(); //     (  ，      )
				printf("
");
			}
			
			m[next.x][next.y] = 0; //      ，              
			curstep--;
		}
	}
}

int main()
{
	printf("        ,  ：");
  	scanf("%d,%d",&begin.x,&begin.y);
  	printf("        ,  ：");
  	scanf("%d,%d",&end.x,&end.y);
  	
  	
	printf("              :
");
	m[begin.x][begin.y] = 1; //       1
	try_path(begin, 1);
  	return 0;
 }

2.2解法2

#include "ds.h"

#define 	STACK_INIT_SIZE 	10		//           
#define 	STACK_INCREMENT 	2		//          
#define 	MAZE_COLUMN			7		//      
#define 	MAZE_ROW			7		//      


struct PosType //         
{
   	int x; //   
   	int y; //   
};

struct SElemType 		//       
{
   	int ord; 			//         ＂  ＂
   	PosType seat; 		//         ＂    ＂
   	int di; 			//              ＂  ＂(0～3   ～ )
};

typedef struct SqStack
{
	SElemType 		*base;				//            ，base   NULL
	SElemType 		*top;				//     
	int 			stacksize;			//           ，      
}SqStack;

//        2      ，  0          
int m[MAZE_ROW][MAZE_COLUMN] = {
									{2, 2, 2, 2, 2, 2, 2}, 
									{2, 0, 0, 0, 0, 0, 2}, 
									{2, 0, 2, 0, 2, 0, 2}, 
									{2, 0, 0, 2, 0, 2, 2}, 
									{2, 2, 0, 2, 0, 2, 2}, 
									{2, 0, 0, 0, 0, 0, 2}, 
									{2, 2, 2, 2, 2, 2, 2}	
				  				   }; 

PosType 	begin,end;  //        ,    
SqStack 	S; 			//    
int 		curstep=1; 	//     ，  (    ) 1

//       S
void InitStack(SqStack &S)
{
	S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
	if (!S.base) exit(OVERFLOW);
	
	S.top = S.base;
	S.stacksize = STACK_INIT_SIZE;
}

//   S   ，   TRUE，    FALSE
Status StackEmpty(SqStack S)
{
	if (S.top == S.base)
		return TRUE;
	else
		return FALSE;
}


//     e       
void Push(SqStack &S, SElemType e)
{
	if (S.top - S.base >= S.stacksize)
	{
		S.base = (SElemType*)realloc(S.base, (S.stacksize + STACK_INCREMENT) * sizeof(SElemType));
		if (!S.base) exit(OVERFLOW);
		
		S.top = S.base + S.stacksize;
		S.stacksize += STACK_INCREMENT;
	}
	
	memcpy(S.top, &e, sizeof(SElemType));
	S.top++;
}

//     ，   S     ， e    ，   OK；    ERROR
Status Pop(SqStack &S, SElemType &e)
{
	if (S.top == S.base)
		return ERROR;
	
	memcpy(&e, --S.top, sizeof(SElemType));
	return OK;
}

//                    visit()
void StackTraverse(SqStack S, void(* visit)(SElemType))
{
	SElemType *p = S.base;
	
	while(p < S.top)
	{
		visit(*p++);
		printf("
");
	}
	
	printf("
");
}


	
void print(SElemType e)
{
	printf("  :%d \t",e.ord);
	printf("    :(%d, %d) \t",e.seat.x, e.seat.y);
	printf("  (0～3   ～ ): %d
", e.di);
}


void Print()
{ //       (m  )
  int i, j;
  for(i=0; i<MAZE_ROW; i++)
  {
    for(j=0;j<MAZE_COLUMN;j++)
      printf("%3d",m[i][j]);
    printf("
");
  }
}

int Pass(PosType b)
{ 
	//    m b     0(     )，  1；  ，  0
  	if(m[b.x][b.y] == 0)
    	return 1;
  	else
   	 	return 0;
}

void FootPrint(PosType a)
{ 
	//    m a       (curstep)
  	m[a.x][a.y] = curstep;
}

void NextPos(PosType &c, int di)
{ 
	//            ，      
  	PosType direc[4] = {{0,1}, {1,0}, {0,-1}, {-1,0}}; // {   ,   },    ,       
  	c.x += direc[di].x;
  	c.y += direc[di].y;
}

void MarkPrint(PosType b)
{ 
	//    m b      -1(       )
  	m[b.x][b.y] = -1;
}

Status MazePath(PosType start,PosType end) //   3.3
{ //    m      start   end   ，     
  //      (      )，   TRUE；    FALSE

  	PosType 	curpos; //     
  	SElemType 	e; 		//    
  	InitStack(S); 		//     
  	curpos = start; 	//        
  	do
  	{ 
  		//         ，           
    	if(Pass(curpos))
    	{
      		FootPrint(curpos); //     
      		e.ord  = curstep;
      		e.seat = curpos;
      		e.di   = 0;
      		Push(S,e); //          
      		curstep++; //    1
      		if(curpos.x == end.x && curpos.y == end.y) //     (  )
        		return TRUE;
      		NextPos(curpos,e.di); //           ，         
    	}
    	else
    	{ 
    		//         
      		if(!StackEmpty(S)) //    
      		{
        		Pop(S,e); //        
        		curstep--; //    1
        		while(e.di==3&&!StackEmpty(S)) //             ( )
        		{
          			MarkPrint(e.seat); //               (-1)
          			Pop(S,e); //      
          			curstep--; //     1
        		}
        		if(e.di<3) //         ( )
        		{
          			e.di++; //         
          			Push(S,e); //            
          			curstep++; //    1
          			curpos=e.seat; //       
          			NextPos(curpos,e.di); //                    
        		}
      		}
    	}
  }while(!StackEmpty(S));
  
  return FALSE;
}

int main()
{
	printf("        ,  ：");
  	scanf("%d,%d",&begin.x,&begin.y);
  	printf("        ,  ：");
  	scanf("%d,%d",&end.x,&end.y);
  	
  	if (MazePath(begin, end))
	{
		printf("                 
");
		Print(); //      
	}
	else
	{
		printf("               
");
	}
	printf("         ： 
");
	StackTraverse(S, print);
}

3.式評価

#include "ds.h"

#define 	STACK_INIT_SIZE 	10		//          
#define 	STACK_INCREMENT 	2		//         


typedef 	char 	SElemType;

typedef struct SqStack
{
	SElemType 		*base;				//            ，base   NULL
	SElemType 		*top;				//     
	int 			stacksize;			//           ，      
}SqStack;

void InitStack(SqStack &S);
void DestroyStack(SqStack &S); 
void ClearStack(SqStack &S);
Status StackEmpty(SqStack S);
int StackLength(SqStack S);
Status GetTop(SqStack S, SElemType &e);
void Push(SqStack &S, SElemType e);
Status Pop(SqStack &S, SElemType &e);
void StackTraverse(SqStack S, void(* visit)(SElemType));

//       S
void InitStack(SqStack &S)
{
	S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
	if (!S.base) exit(OVERFLOW);
	
	S.top = S.base;
	S.stacksize = STACK_INIT_SIZE;
}

//    S，S    
void DestroyStack(SqStack &S)
{
	free(S.base);
	S.base = NULL;
	S.top = NULL;
	S.stacksize = 0;
}

//  S    
void ClearStack(SqStack &S)
{
	S.top = S.base;
}

//   S   ，   TRUE，    FALSE
Status StackEmpty(SqStack S)
{
	if (S.top == S.base)
		return TRUE;
	else
		return FALSE;
}

//   S     ，     
int StackLength(SqStack S)
{
	return S.top - S.base;  // not return S.stacksize;
}

//     ，  e  S     ，   OK；    ERROR
Status GetTop(SqStack S, SElemType &e)
{
	if (S.top > S.base)
	{
		memcpy(&e, S.top - 1, sizeof(SElemType));
		return OK;
	}
	else
	{
		return ERROR;
	}
}

//     e       
void Push(SqStack &S, SElemType e)
{
	if (S.top - S.base >= S.stacksize)
	{
		S.base = (SElemType*)realloc(S.base, (S.stacksize + STACK_INCREMENT) * sizeof(SElemType));
		if (!S.base) exit(OVERFLOW);
		
		S.top = S.base + S.stacksize;
		S.stacksize += STACK_INCREMENT;
	}
	
	memcpy(S.top, &e, sizeof(SElemType));
	S.top++;
}

//     ，   S     ， e    ，   OK；    ERROR
Status Pop(SqStack &S, SElemType &e)
{
	if (S.top == S.base)
		return ERROR;
	
	memcpy(&e, --S.top, sizeof(SElemType));
	return OK;
}

//                    visit()
void StackTraverse(SqStack S, void(* visit)(SElemType))
{
	SElemType *p = S.base;
	
	while(p < S.top)
	{
		visit(*p++);
	}
	printf("
");
}

void print(SElemType c)
{
	printf("%c ",c);
}


char Precede(SElemType t1, SElemType t2)
{
	char ret;
	switch (t2)
	{
		case '+':
		case '-':
			if (t1 == '(' || t1 == '
')
				ret = '<';	// t1 < t2
			else
				ret = '>';	// t1 > t2
			break;
		
		case '*':
		case '/':
			if (t1 == '*' || t1 == '/' || t1 == ')')
				ret = '>'; 	// t1 > t2
			else
				ret = '<';	// t1 < t2
			break;
		
		case '(':
				if (t1 == ')')
				{
					printf("      
");
					exit(ERROR);
				}
				else
					ret = '<';	// t1 < t2
				break;
			
		case ')':
				switch (t1)
				{
					case '(':
							ret = '='; 	// t1 = t2
						break;
					case '
':
							printf("      
");
							exit(ERROR);
					default:
							ret = '>';	// t1 > t2
				}
				break;
		case '
':
				switch (t1)
				{
					case '
': 
							ret = '='; // t1 = t2
							break;
					case '(':
							printf("     
");
							exit(ERROR);
					default:
							ret = '>';	// t1 > t2
				}
	}
	
	return ret;
}

Status In(SElemType c)
{
	switch (c)
	{
		case '+':
		case '-':
		case '*':
		case '/':
		case '(':
		case ')':
		case '
':
				return TRUE;
		default: 
				return FALSE;
	}
}

SElemType Operate(SElemType a, SElemType theta, SElemType b)
{
	switch (theta)
	{
		case '+':	return a+b;
		case '-':	return a-b;
		case '*':	return a*b;
	}
	
	return a/b;
}

//               。 OPTR OPND            
SElemType EvaluateExpression()
{
   SqStack OPTR,OPND;
   SElemType a,b,d,x; 
   char c; //           ，
   char z[11]; //        ，
   int i; 
   InitStack(OPTR); //        OPTR     OPND
   InitStack(OPND);
   Push(OPTR,'
'); //           OPTR   ( )
   c=getchar(); //      1    c
   GetTop(OPTR,x); //      OPTR       x
   while(c!='
'||x!='
') // c x      
   {
     if(In(c)) // c 7      
       switch(Precede(x,c)) //   x c    
       {
         case'<' :Push(OPTR,c); //     x     ，  c
                  c=getchar();  //            c
                  break;
         case'=' :Pop(OPTR,x); // x='(' c=')'  ，  '(' x(    )
                  c=getchar(); //            c(  ')')
                  break;
         case'>' :Pop(OPTR,x); //     x     ，      OPTR      x( )
                  Pop(OPND,b); //         OPND      b，a
                  Pop(OPND,a);
                  Push(OPND,Operate(a,x,b)); //    a x b，           
       }
     else if(c>='0'&&c<='9') // c    ，    
     {
       i=0;
       while(c>='0'&&c<='9') //      
       {
         z[i++]=c;
         c=getchar();
       }
       z[i]=0; //       
       d=atoi(z); //  z                d
       Push(OPND,d); //  d      OPND
     }
     else // c     ，   
     {
       printf("      
");
       exit(ERROR);
     }
     GetTop(OPTR,x); //      OPTR       x
   }
   Pop(OPND,x); //       OPND     (    ) x(   )
   if(!StackEmpty(OPND)) //     OPND  (    OPTR  '
')
   {
     printf("      
");
     exit(ERROR);
   }
   return x;
 }

 int main()
 {
   printf("        ,    (0-  )  
");
   printf("%d
",EvaluateExpression());
 }

4.スタックと再帰——hanoi塔

#include <stdio.h>

int move_times = 0; 	//     ，     

//  n      x     z
void move(char x, int n, char z)
{
	printf(" %i :  %i    %c  %c
", ++move_times, n, x, z);
}

//    x                1 n n   
//        z ，y       
void hanoi(int n, char x, char y, char z)
{
	//   
	if (1 == n)
	{
		move(x, 1, z);
	}
	else
	{
		hanoi(n-1, x, z, y);	//  x    1 n-1     y ，z     (      )
		move(x, n, z);			//     n    x  z 
		hanoi(n-1, y, x, z);	//  y    1 n-1     x ，x     (      )
	}
}

int main()
{
	int n;
	printf("3    x，y，z，     x ，  y   z 。      ：");
	scanf("%d", &n);
	hanoi(n, 'x', 'y', 'z');
	return 0;
}

5.かっこの一致

#include "ds.h"

typedef char SElemType;


#define STACK_INIT_SIZE 100
#define STACK_INCREMENT  10

typedef struct {
	SElemType 		*base;
	SElemType 		*top;
	int 	  		stacksize;
}SqStack;


void InitStack(SqStack &S);
Status StackEmpty(SqStack S);
int StackLength(SqStack S);
Status GetTop(SqStack S, SElemType &e);
void Push(SqStack &S, SElemType e);
Status Pop(SqStack &S, SElemType &e);
void StackTraverse(SqStack S, void(* visit)(SElemType));


//       S
void InitStack(SqStack &S)
{
	S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
	if (!S.base) exit(OVERFLOW);
	
	S.top = S.base;
	S.stacksize = STACK_INIT_SIZE;
}

//   S   ，   TRUE，    FALSE
Status StackEmpty(SqStack S)
{
	if (S.top == S.base)
		return TRUE;
	else
		return FALSE;
}

//   S     ，     
int StackLength(SqStack S)
{
	return S.top - S.base;  // not return S.stacksize;
}

//     ，  e  S     ，   OK；    ERROR
Status GetTop(SqStack S, SElemType &e)
{
	if (S.top > S.base)
	{
		memcpy(&e, S.top - 1, sizeof(SElemType));
		return OK;
	}
	else
	{
		return ERROR;
	}
}

//     e       
void Push(SqStack &S, SElemType e)
{
	if (S.top - S.base >= S.stacksize)
	{
		S.base = (SElemType*)realloc(S.base, (S.stacksize + STACK_INCREMENT) * sizeof(SElemType));
		if (!S.base) exit(OVERFLOW);
		
		S.top = S.base + S.stacksize;
		S.stacksize += STACK_INCREMENT;
	}
	
	memcpy(S.top, &e, sizeof(SElemType));
	S.top++;
}

//     ，   S     ， e    ，   OK；    ERROR
Status Pop(SqStack &S, SElemType &e)
{
	if (S.top == S.base)
		return ERROR;
	
	memcpy(&e, --S.top, sizeof(SElemType));
	return OK;
}

//                    visit()
void StackTraverse(SqStack S, void(* visit)(SElemType))
{
	SElemType *p = S.base;
	
	while(p < S.top)
	{
		visit(*p++);
	}
	printf("
");
}

void print(SElemType c)
{
	printf("%d ",c);
}

//         
void bracketcheck()
{
	SqStack S;
	SElemType str[80], *p, e;
	InitStack(S);
	printf("      （()、[]   {}）    
");
	gets(str);
	p = str;
	while (*p)
	{
		switch (*p)
		{
			case '(':
			case '[':
			case '{':
				Push(S, *p++);
				break;
				
			case ')':
			case ']':
			case '}':
				if (!StackEmpty(S))
				{
					Pop(S, e);
					if ( !(( '(' == e && ')'== *p )
						 ||( '[' == e && ']'== *p )
						 ||( '{' == e && '}'== *p ))
						)
					{
						//    3       
						printf("NO        
");
						exit(ERROR);
					}
				}
				else //   
				{
					printf("miss (      
");
					exit(ERROR);
				}
			default:
				p++; //        ，    
		}
	}
	
	if (StackEmpty(S))
		printf("yes     
");
	else
		printf("no      
");
}

int main()
{
	bracketcheck();
}