由于栈结构具有“先进后出”的固有特点,以至于栈成为了程序设计中的有用工具,在许多实际问题中都利用栈做一个辅助的数据结构来进行求解。
栈在计算机中应用得非常广泛,例如,在编译和运行程序的过程中,需要利用堆栈进行语法检查(如检查括号是否配对)、表达式求值、实现递归算法与函数调用等。
这一节将通过几个简单的例子来说明栈的具体应用。
编写算法将非负的十进制整数转换为其他进制的数输出,10及其以上的数字用从'A'开始的字母表示。
十进制整数转换为其他进制整数通常采用“除以基数取余数”方法,依次对除以基数得到的商再次求余数,这样得到的为待转换进制数从低位到高位的值,当商为0时转换完毕。
具体实现时使用栈暂时存放每次计算得到的余数,当算法结束时(也就是商为0时),从栈顶到栈底就是转换后从高位到低位的数值。
相应的算法如下:
static char pszResult[100]; /*用于存放转换后的进制的字符串*/
void Transform(int nDecimal,int nBase)
{ /*将nDecimal的十进制数转换为nBase(2~36)进制数*/
SqStack st;
char ch; int i=0;
if (nBase<=1 || nBase>36 || nBase==10) /*待转换的进制不合适*/
{
printf("待转换的进制错误!\n");
exit (1);
}
InitStack(st);
while (nDecimal!=0)
{
ch=(char)(nDecimal%nBase); /*求余数并转换为字符*/
ch=ch+(ch<10?48:65–10); /*对转换得到的字符做修正*/
/*在0…9中间直接用'0'…'9'表示,48为'0' 的ASCII码;大于9则采用'A'…'Z'表示,65为'A' 的ASCII码*/
Push(st,ch); /*进栈*/
nDecimal/=nBase; /*继续求更高位*/
}
while (!StackEmpty(st))
{
Pop(st,ch); /*出栈时存放在数组中*/
pszResult[i++]=e;
}
pszResult[i]='\0'; /*加入字符串结束标志*/
}
假设表达式中包含3种括号:圆括号、方括号和花括号,其嵌套顺序随意,即“{([]())}”等为正确的格式,“[()]”、“([()]”或“(())”均为不正确的格式。检验括号是否匹配可以用栈来实现:当遇到“(”、“[”或“{”时进栈,遇到“}”、“]”或“)”时出栈并进行匹配检验,如果出现不匹配的情况立即结束,否则继续取下一个字符。如果没有遇到不匹配的情况,最后判断栈是否为空:栈为空,括号匹配;否则不匹配。在算法的开始和结束时,栈都应该是空的。算法如下:
#define Max 100 /*栈的最大尺寸*/
int match(char *exps)
{
char st[Max],top=-1,i=0;
int nomatch=0;
while (exps[i]!='\0' && nomatch==0)
{
switch(exps[i])
{
case '(': st[top]=exps[i];top++;break;
case '[': st[top]=exps[i];top++;break;
case '{': st[top]=exps[i];top++;break;
case ')': if (exps[top]=='(') top--;
else nomatch=1;
break;
case ']': if (exps[top]=='[') top--;
else nomatch=1;
break;
case '}': if (exps[top]=='{'} top--;
else nomatch=1;
break;
}
i++;
}
if(nomatch==0 && top==-1) /*栈空且符号匹配则返回1*/
return 1;
else
return 0; /*否则返回0*/
}
一个简单的行编辑程序的功能是:接受用户从终端输入的程序或数据,并存入用户的数据区。由于用户在终端上进行输入时,不能保证不出现差错,因此,在编辑程序中,“每接受一个字符即存入用户数据区”的做法显然不是最恰当的。较好的做法是:设立一个输入缓冲区,用以接受用户输入的一行字符,然后逐行存入用户数据区,允许用户输入出错时可以及时发现并更正。可以约定:“#”为退格符,表示前一个字符无效;“@”为退行符,表示当前行所有字符均无效。
在终端上用户输入的whli##ilr#e(s#*s)应为while(*s)。
为此,可设这个输入缓冲区为一个栈结构,每当从终端接受了一个字符之后,先做如下判别:如果它既不是退格符也不是退行符,则将该字符压入栈;如果是一个退格符,则从栈顶删去一个字符;如果是一个退行符,则将字符栈清为空栈。
上述处理过程对应算法如下:
void LineEdit()
{
pSqStack S,T; char str[1000];
int strlen=0;
char e;
char ch;
InitStack(&S);
InitStack(&T);
ch=getchar();
while(ch!=EOFILE)
{
while(ch!=EOFILE&&ch!='\n')
{
switch(ch)
{
case '#': Pop(S,&ch);break; /*仅当栈非空时退栈*/
case '@': ClearStack(S);break; /*重置S为空栈*/
default: Push(S,ch); break; /*有效字符进栈,未考虑栈满情形*/
}
ch=getchar(); /*从终端接收下一个字符*/
}
if(ch=='\n') Push(S,ch);
while(!StackEmpty(*S)) { Pop(S,&e);Push(T,e); }
while(!StackEmpty(*T)) { Pop(T,&e);str[strlen++]=e; }
if(ch!=EOFILE) ch=getchar();
}
str[strlen]='\0';
printf("\n%s",str);
DestroyStack(S); /*销毁栈S*/
DestroyStack(T); /*销毁栈T*/
}
求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解决迷宫时,通常用的是“穷举求解”的方法,即从入口出发,顺某一个方向向前探索,若能走通,则继续往前走;否则沿原路退回,换另一个方向再继续探索,直至所有可能的通路都探索完为止。为了保证在任何位置上都能沿原路退回,显然需要一个后进先出的结构来保存入口到当前位置的路径。因此,在求迷宫通路的算法中应用“栈”也就是自然而然的事了。
在计算机中可以用方块图表示迷宫。每个方块或为通道(以空白方块表示),或为墙(以带阴影线的方块表示)。所求路径必须是简单路径,即在求得的路径上不能重复出现同一通道块。
求迷宫中一条从入口到出口的路径的算法可简单描述如下(从入口开始):
do
{
if(当前位置可通)
{
当前位置入栈
if(当前位置是出口)
{
结束
}
else
{
取得当前位置当前方向上的下一位置为当前位置
将新当前位置入栈
}
}
else
{
从栈中弹出栈顶元素为当前位置
while(当前位置已无下一有效位置&& 栈不为空)
{
将当前位置标记为无效
弹出栈顶元素为当前位置
}
if(当前位置还有下一有效位置时)
{
当前位置方向调整
当前位置进栈
取得当前位置当前方向上的下一位置为当前位置
}
}
}while(栈不为空时);
上述算法的C语言形式化描述如下:
typedef struct
{
int ord; /*通关节点在路径上的“序号”*/
PosType 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(TRUE); /*到达终点(出口)*/
cotpos=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(FALSE);
}
表达式求值是程序设计语言编译中的一个最基本的问题。它的实现是栈应用的又一个典型例子。这里介绍一种简单直观、广为使用的算法,通常称为“算符优先法”。
一个程序设计语言应该允许设计者根据需要用表达式描述计算过程,编译器则应该能分析表达式并计算出结果。表达式的要素是运算符、操作数、界定符、算符优先级关系。例如,1+2*3有“+”、“*”两个运算符,“*”的优先级高,1、2、3是操作数。界定符有括号和表达式结束符等。
为了实现算符优先算法,可以使用两个工作栈。一个称做OPTR,用以寄存运算符;另一个称做OPND,用以寄存操作数或运算结果。算法的基本思路是:
(1)首先置操作数栈为空栈,表达式起始符#为运算符栈的栈底元素。
(2)依次将表达式中的每个字符进栈,若是操作数则进OPND栈;若是运算符,则和OPTR栈的栈顶运算符比较优先级后作相应操作,直至整个表达式求值完毕(即OPTR栈的栈顶元素和当前读入的字符均为“#”)。
对应算法如下:
char EvaluateExpression()
{
SqStack *OPND,*OPTR;
char c,x,theta;
char a,b;
InitStack(&OPTR);
Push(OPTR,'#');
InitStack(&OPND);
c=getchar();
while(c!='#'||GetTop(*OPTR)!='#')
{
if(!In(c,OP)) {Push(OPND,c);c=getchar();} /*不是运算符则进栈*/
else
switch(Precede(GetTop(*OPTR),c))
{
case '<': Push(OPTR,c); c=getchar(); break; /*栈顶优先级别低*/
case '=': Pop(OPTR,&x); c=getchar(); break; /*脱去括号并接收下一字符*/
case '>': Pop(OPTR,&theta); /*退栈并将运算结果入栈*/
Pop(OPND,&b); Pop(OPND,&a);
Push(OPND,Operate(a,theta,b));
break;
}
}
c=GetTop(*OPND);
DestroyStack(OPTR); /*销毁栈*/
DestroyStack(OPND); /*销毁栈*/
return c;
}