栈的应用

 学习数据结构一年了，现在才有点时间开始慢慢总结之前学过的一些东西，数据结构的好坏体现的 是一个程序员的基本功。数据结构和算法是一体的，当我们研究数据结构时，通常也涉及到算法。平时没有养成一个好的习惯，将很多东西都忘记了，以后努力将每天所学到的知识进行一个总结。闲话不多说。
   栈，是一种在表尾进行插入或者删除的线性表。其特点为后进先出(LIFO)，存储结构分为顺序存储或者链式存储。具体的概念性的东西可以参照一下严蔚敏版数据结构。下面就谈一下栈的三个有意思的应用:括号匹配，迷宫求解，表达式求值。
     括号匹配算法：

        括号匹配算法的思想非常简单，遍历输入的字符串，如果开始输入的是右括号)或者]，则不能够匹配。其他情况下首先将左括号压入栈(或者[，然后在访问下一个字符，若还是左括号，继续入栈。当遇到有括号的时候，判断一下是否与前面一个符号相匹配，若匹配，则进行出栈操作。然后访问下一个符号，重复上面的操作。

#include<iostream>
using namespace std;
#define ERROR 0
#define OK 1
#define STACK_INIT_SIZZE 100
#define STACKINCREMENT 10
#define SElemType char 

typedef struct SqStack{

	SElemType *base;//栈底指针
	SElemType *top;//栈顶指针
	int size;
}SqStack;

//初始化一个栈
int InitStack( SqStack &s)
{
	s.base=(SElemType*)malloc(STACK_INIT_SIZZE*sizeof(SElemType));
	if(s.base==NULL)return ERROR;

	s.top=s.base;//设置栈表为空
	s.size=STACK_INIT_SIZZE;//当前栈的长度
	return OK;	
}

int StackEmpty(SqStack s)
{
	if(s.base==s.top)//当栈顶等于栈底的时候说明栈为空
		return OK;
	return ERROR;
}

//入栈
int Push(SqStack &s, SElemType e)
{
	if(s.top-s.base>STACK_INIT_SIZZE)
	{
		s.base=(SElemType*)realloc(s.base,(s.size+STACKINCREMENT)*sizeof(SElemType));//如果内存满了重新分配内存空间
		if(!s.base)exit(ERROR);//内存分配失败
		s.top=s.base+STACK_INIT_SIZZE;
		s.size+=STACKINCREMENT;//将容量扩大

	}
	*(s.top++)=e;

	return OK;	
}

	//如果栈表不为空，则删除s的栈顶元素，并用e将其值返回回来
int Pop(SqStack &s,SElemType &e)
{
	if(s.base==s.top)return ERROR;
	e=*(--s.top);
	return OK;
	
}

void DestoryStack(SqStack &s)
{
	free(s.base);
}

int StackLength(SqStack s)
{
	int i=0;
	while(s.base!=s.top)
	{
		i++;
		s.top--;
	}

	return i;
}


//判断输入的数据是否匹配
int Match(char s[],SqStack &l)
{
	printf("%s
",s);
	int i,j=0;
	int length=strlen(s);
	char *a=new char[];
	for(i=0;i<length;i++)
	{
		if(StackEmpty(l))
		{
			if(s[i]==')'||s[i]==']')
				return ERROR;
			else if(s[i]=='('||s[i]=='[')
				Push(l,s[i]);
		}
		else if(!StackEmpty(l))
		{
			if(s[i]==')')
				if(*(l.top-1)=='(')
					Pop(l,a[j++]);//将该括号弹出栈
			if(s[i]==']')
				if(*(l.top-1)=='[')
					Pop(l,a[j++]);
			if(s[i]=='('||s[i]=='[')
				Push(l,s[i]);
		}
	}
	if(StackEmpty(l))
		return OK;
	return ERROR;
	
}

int main()
{
	SqStack l;
	char s[100];
	scanf("%s",&s);
	InitStack(l);
	if(Match(s,l))
		printf("括号是匹配的!
");
	else
		printf("括号不匹配!
");
	if(l.top==l.base)
		printf("栈已经被清空!
");
	return 0;
}

  迷宫求解:

    迷宫求解问题是一个经典的程序设计问题，计算机在解决此类问题的时候通常使用的穷举法，具体思想是:从入口出发，沿着某一特定的方向向前进行探索，若走得通，就继续向前走；否则原路退回，换一个方向再继续探索。直到将所有可能的路径都探索到为止。为了保证任何路径都能沿原路返回，就需要一个后进先出的结构来保存路径，所以就要用到栈。

   其描述如下:

        设置当前位置的初值为栈的入口位置；

        do{

                若当前位置可通      //将当前位置纳入路径

               则{

                    将当前位置进行入栈处理，并将当前位置标记下来

                    若当前位置为出口位置，则结束

                    否则将当前位置东边的邻块设置为新的当前位置

              } 

          否则

        {

              若栈不为空，且栈顶元素还有其他位置方向没有探索

              则设定新的当前位置为沿顺时针方向找到栈顶位置的下一个相邻块

              若栈不为空，当时栈顶位置的四周都不通

              则{

                      删除栈顶元素

                      若栈还不为空则重新测试新的栈顶位置

                          直到找到一个可通的相邻块或者或者栈为空

              }

       }

       }while(栈不为空)

  可通是指当前未曾走到的通道块。不然会形成循环。

#include<iostream>
using namespace std;
#define Status int 
#define OK 1
#define ERROR 0
#define STACK_SIZE 100
#define INCREMENT_SIZE 10

int MAZE[10][10]=
{
	{0,0,0,0,0,0,0,0,0,0},
	{0,1,1,0,1,1,1,0,1,0},
	{0,1,1,0,1,1,1,0,1,0},
	{0,1,1,1,1,0,0,1,1,0},
	{0,1,0,0,0,1,1,1,1,0},
	{0,1,1,1,0,1,1,1,1,0},
	{0,1,0,1,1,1,0,1,1,0},
	{0,1,0,0,1,1,1,0,1,0},
	{0,0,1,1,1,1,1,1,1,0},
	{0,0,0,0,0,0,0,0,0,0}
};

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

typedef struct{

	int ord;//通道块路径上面的序号
	PosType seat;//通道块在迷宫当中的坐标
	int di;//从此通道块向下一通道块所走的方向;
}SElemType;

typedef struct{

	SElemType *top;//栈顶元素
	SElemType *base;//栈底元素
	int size;	
}SqStack;

Status InitStack(SqStack &S);
void Push(SqStack &S,SElemType e);
void Pop(SqStack &S,SElemType &e);
Status StackEmpty(SqStack S);

//地图探索的操作
int Pass(PosType pos);
void FootPrint(PosType pos);
void MarkPrint(PosType pos);
PosType NextPos(PosType curpos,int di);
Status MazePath(PosType start,PosType end);
int Equals(PosType p1,PosType p2);


int main()
{
	int i,j;
	PosType start,end;
	start.x=start.y=1;
	end.x=end.y=8;

	for(i=0;i<10;i++)
	{
		for(j=0;j<10;j++)
			printf("%d ",MAZE[i][j]);
		printf("
");
	}

	if(MazePath(start,end))
		printf("该迷宫存在解
");
	else
		printf("该迷宫不存在解
");

	for(i=0;i<10;i++)
	{
		for(j=0;j<10;j++)
			printf("%d ",MAZE[i][j]);
		printf("
");
	}
	return 0;
}


Status InitStack(SqStack &S)
{
	S.base=(SElemType*)malloc(STACK_SIZE*sizeof(SElemType));
	if(!S.base)return ERROR;
	S.top=S.base;
	S.size=STACK_SIZE;
	return OK;
}

void Push(SqStack &S,SElemType e)
{
	if(S.top-S.base>=STACK_SIZE)
	{
		S.base=(SElemType*)realloc(S.base,(S.size+INCREMENT_SIZE)*sizeof(SElemType));
		S.top=S.base+S.size;
		S.size+=INCREMENT_SIZE;
	}
	*S.top++=e;
}

void Pop(SqStack &S,SElemType &e)
{
	if(S.base==S.top)exit(0);
	e=*(--S.top);
}

Status StackEmpty(SqStack S)
{
	if(S.base==S.top)
		return OK;
	else
		return ERROR;
}


int Pass(PosType pos)
{
	if(MAZE[pos.y][pos.x]==1)
		return OK;
	return ERROR;
}

void FootPrint(PosType pos)//留下足迹
{
	MAZE[pos.y][pos.x]=2;
}

void MarkPrint(PosType pos)
{ 
//	printf("(%d,%d)
走不通
",pos.y,pos.x);
	MAZE[pos.y][pos.x]=0;
}

PosType NextPos(PosType Curpos,int di)
{
	switch(di)
	{
	case 1:Curpos.x++;	break;//向东探索		
	case 2:Curpos.y++;break;
	case 3:Curpos.y--;break;	
	case 4:Curpos.x--;break;
	}
	return Curpos;
}

int Equals(PosType p1,PosType p2)
{
	if(p1.x==p2.x&&p1.y==p2.y)
		return OK;
	else
		return ERROR;
}

Status MazePath(PosType start,PosType end)
{
	SqStack S;
	PosType curpos;
	SElemType e;
	int curstep=1;
	curpos=start;
	InitStack(S);
	do{
		if(Pass(curpos))//当前位置可通
		{
			FootPrint(curpos);
			e.ord=curstep;
			e.seat=curpos;
			e.di=1;
			Push(S,e);
			if(Equals(curpos,end))return OK;
			curpos=NextPos(curpos,1);
			curstep++;
		}else//如果当前位置不可通
		{
			if(!StackEmpty(S))
			{
				Pop(S,e);
				while(e.di==4&&!StackEmpty(S))//留下不能通过的标记，并且退回一格
				{
					MarkPrint(e.seat);
					Pop(S,e);
				}
				if(e.di<4)
				{
					e.di++;
					Push(S,e);//换下一个方向进行探索
					curpos=NextPos(e.seat,e.di);
				}
			}
		}
	}while(!StackEmpty(S));
	return ERROR;;
}

表达式求值算:

       表达式求值是程序设计语言编译中一个基本的问题，他是实现栈的又一个经典的例子。通常使用的方法称作"算符优先法"

       要对表达式进行求值，首先要正确理解表达式，即要了解他的运算规则，下面以简单的加减乘除四则运算为例:

主要有下面几条规则：

   (1)先乘除，后加减

   (2)从左算到右

   (3)先括号内后括号外

算符的对应的优先关系有以下三中:

  a>b  a的优先权高于b

 a=b  a的优先权等于b

 a<b  a的优先权小于b

根据上面的三种有限规则，构造下面的算符有限表

  

由规则3可知 a为+.-.*./时的优先性低于"("但高于")"，由规则2可知，当a，b为相同的算符时，a>b。"#"是表达式结束符。为了算符简洁，在表达式的最左边也虚设一个"#"，使后面的算符有比较的对象，并且能够正常进入栈中。表中的"("=")"表示当左右括号相遇的时候，括号内的运算完成，然后进行去括号操作，一些算符之间没有优先关系是因为他们两两之间并不能够相邻。一旦出现相邻的情况，则认为语法错误。

      为了实现算符优先运算，可以使用两个工作栈。一个称作oprt，用以寄存运算符，另一个称作opnd，用以存储操作数或者运算结果。

      算法思想:

       （1）首先将操作数栈设置为空栈，表达式起始符"#"为运算符栈的栈底元素

        （2）一次读入表达式中的每一个字符，若是操作数，则进入操作数栈，若是运算f符，则和栈顶算符比较优先权既然后在进行相应的操作。假设a为栈顶运算符，b为读入的运算符，若若a>b，则在操作数栈中弹出两个操作数，然后将栈顶运算符弹出，进行对应的运算，再将结果压入操作数栈。若a<b，则将b压入运算符栈。若a=b则进行去括号处理。直到读入的字符为"#"或者栈顶元素为"#"

源代码:

  

#include<iostream>
using namespace std;

#define OK 1
#define ERROR -1
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define Status int
#define ElemType char
#define OPSETSIZE 8

typedef struct Operand{//操作数

	double *base;//栈底指针
	double *top;//栈顶指针
	int size;
}Operand;

typedef struct Operator{

	char *base;//栈底指针
	char *top;//栈顶指针
	int size;
}Operator;

Status InitOprd(Operand &oprd)
{
	oprd.base=(double*)malloc(STACK_INIT_SIZE*sizeof(double));
	if(oprd.base==NULL)return ERROR;
	oprd.top=oprd.base;
	oprd.size=STACK_INIT_SIZE;
	return OK;
}

Status InitOprt(Operator &oprt)
{
	oprt.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));
	if(oprt.base==NULL)return ERROR;
	oprt.top=oprt.base;
	oprt.size=STACK_INIT_SIZE;
	return OK;
}

Status PushOprd(Operand &oprd,double e)
{
	if(oprd.top-oprd.base>STACK_INIT_SIZE)
	{
		oprd.base=(double*)realloc(oprd.base,(oprd.size+STACKINCREMENT)*sizeof(double));
		if(oprd.base==NULL)exit(0);
		oprd.top=oprd.base+STACK_INIT_SIZE;
		oprd.size+=STACKINCREMENT;
	}
	*oprd.top=e;
	oprd.top++;
	return OK;
}

Status PushOprt(Operator &oprt,ElemType e)
{
	if(oprt.top-oprt.base>STACK_INIT_SIZE)
	{
		oprt.base=(char*)realloc(oprt.base,(oprt.size+STACKINCREMENT)*sizeof(char));
		oprt.top=oprt.base+STACK_INIT_SIZE;
		oprt.size+=STACKINCREMENT;
	}
	*(oprt.top)=e;
	oprt.top++;
	return OK;
}


Status PopOprd(Operand &oprd,double &e)
{
	if(oprd.base==oprd.top)return ERROR;
	e=*(--oprd.top);
	return OK;
}

Status PopOprt(Operator &oprt,ElemType &e)
{
	if(oprt.base==oprt.top)return ERROR;
	e=*(--oprt.top);
	return OK;
}

char getOprdTop(Operand oprd)
{
	ElemType e;
	if(oprd.base==oprd.top)return ERROR;
	e=*(--oprd.top);
	return e;

}


char getOprtTop(Operator oprt)
{
	ElemType e;
	if(oprt.base==oprt.top)return ERROR;
	e=*(--oprt.top);
	return e;
}

char getOprtBase(Operator oprt)
{
	ElemType e;
	if(oprt.base==oprt.top) return ERROR;
	e=*(oprt.base);
	return e;
}

int getOprtSize(Operator oprt)
{
	int i=0;
	if(oprt.base==oprt.top)return 0;

	while(oprt.base!=oprt.top)
	{
		oprt.base++;
		i++;
	}

	return i;
}

int getOprdSize(Operand oprd)
{
	int i=0;
	if(oprd.base==oprd.top)return 0;

	while(oprd.base!=oprd.top)
	{
		oprd.base++;
		i++;
	}

	return i;
}


unsigned char Prior[8][8] = {   //运算符优先级表
  	  '>','>','<','<','<','>','>','>',
	  '>','>','<','<','<','>','>','>',
	  '>','>','>','>','<','>','>','>',
	  '>','>','>','>','<','>','>','>',
	  '<','<','<','<','<','=',' ','>',
	  '>','>','>','>',' ','>','>','>',
	  '<','<','<','<','<',' ','=','>',
	  '<','<','<','<','<','<','<','='
};	

char OPSET[OPSETSIZE]={'+' , '-' , '*' , '/' ,'(' , ')' , '#','
'};

int ReturnOpOrd(char op,char* TestOp)
{
	for(int i=0;i<OPSETSIZE;i++)
		if(op==TestOp[i])
			return i;
	return 0;
}

int In(char op,char* TestOp)
{
	int find=0;
	for(int i=0;i<OPSETSIZE;i++)
		if(op==TestOp[i])
			find=1;

	return find;
}

char Precede(char op1,char op2)//比较运算符的优先级
{
	return Prior[ReturnOpOrd(op1,OPSET)][ReturnOpOrd(op2,OPSET)];
}

double Operate(double a,char op,double b)
{
	switch(op){
	case '+':return a+b;break;
	case '-':return a-b;break;
	case '*':return a*b;break;
	case '/':return a/b;break;
		
	}
}

double EvaluateExpression(Operand &oprd,Operator &oprt)
{
	char c;
	c=getchar();

	while(c!='
'||getOprtSize(oprt)!=0)//执行到最后操作符栈只剩下换行符
	{
		if(!In(c,OPSET))
		{
			c=c-'0';
			PushOprd(oprd,c);
			c=getchar();
		}
		else//如果是操作符
		{
			if(getOprtSize(oprt)==0)//判断栈是否为空
			{
				PushOprt(oprt,c);
				c=getchar();
			}
			else
			{
				switch(Precede(getOprtTop(oprt),c)){
				case '>':
					double a,b;
					if(PopOprd(oprd,a))
						if(PopOprd(oprd,b))
						{
							char operate;
							PopOprt(oprt,operate);
							PushOprd(oprd,Operate(b,operate,a));
						}
				break;
				case '=':
					char ss;
					PopOprt(oprt,ss);
					c=getchar();
					break;
				case '<':
					PushOprt(oprt,c);
					c=getchar();
					break;
				}
			}
		}
	}
	double result;
	PopOprd(oprd,result);
	printf("%lf
",result);
	return result;
}

main()
{
	Operand oprd;
	Operator oprt;
	InitOprt(oprt);
	InitOprd(oprd);
	EvaluateExpression(oprd,oprt);
	return 0;	
}

   

版权声明：本文为博主原创文章，未经博主允许不得转载。