数据结构之栈的应用_栈在计算机科学领域有着广泛的应用。比如在编译和运行计算机程序的过程中,就需要

4、栈的应用

栈在计算机科学领域具有广泛地应用。如，在编译和运行计算机语言程序的过程中，就需要利用栈进行语法检查（如｛和｝是否配对）、计算表达式的值、实现递归过程和函数的都要用等。

4.1、将一个十进制数转换为二进制

注：以下程序在VC6.0+WIN98下测试通过

把十进制正整数转换为对应的二进制整数采用逐次除以2取余法，即用基数2不断的去除被转换的正整数，直到商为0。则第一次相除所得余数就是二进制整数的最低位，最后一次相除所得余数就是二进制的最高位。

#include <stdio.h>

 

/*将一个十进制转换为二进制数*/

void transfer(int n)

{

    int k;

    k=n%2;

    n=n/2;

    if (n!=0) transfer(n);

    printf("%d",k);

}

 

int main()

{

    int n;

    printf("请输入十进制数:");

    scanf("%d",&n);

    printf("十进制%d的相应二进制为:",n);

    transfer(n);

    printf("/n");

    return 1;

}

计算机执行递归算法时，是通过栈来实现的。具体来说，在运行开始时，首先为递归调用建立一个栈，该栈的成分类型包括值参域、局部变量域和返回地址域；在每次执行递归调用语句之前，自动把本算法中所使用的值参和局部变量的当前值以及调用后的返回地址压入栈；在每次递归调用语句结束后，又自动把栈顶各域的值分别赋给相应的值参和局部变量，以便使他们恢复为调用前的值，接着无条件传向（即返回）由返回地址域所指定的位置执行。

对于上面的递归过程来说，调用开始时，系统首先为后面的递归调用建立其成分类型包含值参n的域、局部变量k的域和返回地址的域的一个栈；在每次执行transfer(n)语句递归调用前，自动把n和k的当前值以及printf语句的开始位置（即调用后的返回地址）压入栈；在每次执行到最后的“｝”（即一次递归调用结束）后，又自动把栈顶的与n和k对应域的值分别赋给n和k，接着无条件传向printf语句的开始位置，继续向下执行。

    上面分析的是系统是如何利用堆栈技术来进行递归处理的。我们也可以模拟系统处理递归的方法把一个递归算法改写成一个非递归算法，从而进一步加深对堆栈和递归这两个重要概念的认识。

    设p是一个递归算法，假定p中共有m个值参和局部变量，共有t处递归调用p的过程语句或函数引用，则把p改写为一个非递归算法的一般规则为：

(1)定义一个栈，用来保存每次递归调用当前值和局部变量的当前值以及调用后的返回地址，S栈中的成份类型应包含m+1个域，其中前m个域为值参和局部变量而设，后一个域为返回地址而设，S栈的深度应足够大，使得在递归调用中不会发生溢出；

(2)定义t+2个语句标号，其中用一个标号标在原算法中的第一条语句上，用另一个标号标在作返回处理的第一条语句上，其余t个标号作为t处递归调用的返回地址，分别标在相应的语句上；

(3)把第一个递归调用的语句或函数改写为

(i)            把值参和局部变量的当前值以及调用后的返回地址压入栈；

(ii)        把值参所对应的实参表达式的值赋给值参变量；

(iii)    无条件转向原算法的第一条语句；

(4)在算法结尾之前增加返回处理，当栈非空时做：

(i)            退栈

(ii)        把原栈顶中前m个域的值分别赋给各对应的值参和局部变量；

(iii)    无条件转向由本次返回地址所指定的位置；

(5)增设一个同S栈的成分类型相同的变量，作为进出栈的缓冲变量，对于递归函数，还需要再增设一个保存函数值中间结果的临时变量，用这个变量替换函数体中的所有函数名，待函数过程结束之前，再把这个变量的值赋给函数名返回；

(6)在原算法的第一条语句之前，增加一条置栈空的语句；

(7)对于递归函数而言，若某条赋值语句中包含有两处或多处(假定为n处，n>=2)递归调用，则应首选抒它拆成n条赋值语句，使得每条赋值语句中只包含一处递归调用，同时对增加的n-1条赋值语句，要增设n-1个局部变量，然后再按照以上六条规则转换成非递归函数。

按照以上规则，把transfer递归过程改写成非递归过程的算法如下：

#include <stdio.h>

#define StackSize 6/*栈的容量*/

typedef struct {     /*定义S栈的成份类型*/

       int n; /*值参n的域*/

       int k; /*局部变量k的域*/

       int r; /*返回地址的域*/

    }node;

 

typedef struct{      /*定义S栈的类型*/

       node data[StackSize];   

       int top;

    }stack1;

 

int push(stack1 *s,node *e)

{

    if(s->top<StackSize-1)

    {

       s->top=s->top+1;    

       s->data[s->top].k=e->k;

       s->data[s->top].n=e->n;

       s->data[s->top].r=e->r;

       return 0;

    }

    else

    {

       printf("overflow!/n");

       return 1;

    }

}

 

/*出栈*/

int pop(stack1 *s,node *e)

{

    if(0==s->top)

    {

       printf("underflow/n");

       return 1;

    }

    else

    {

       e->k=s->data[s->top].k;

       e->n=s->data[s->top].n;

       e->r=s->data[s->top].r;

       (s->top)--;

       return 0;

    }

}

 

void transfer1(int n)

{

    stack1 S;

    node x;    /*x作为进出栈的缓冲变量*/

    int k; /*原局部变量*/

   

    S.top=0;   /*置栈空*/

A:  k=n%8;

    n=n/8;

    if (n!=0)     /*按第(3)条规则处理，因实参仍为n，所以可省去把它赋给值参语句*/

    {

       x.n=n;

       x.k=k;

       x.r=2;

       push(&S,&x);

       goto A;

    }

B:

    printf("%d",k);

C:

    if(S.top>0)

    {

       pop(&S,&x);

       n=x.n;

       k=x.k;

       if (x.r==2)

           goto B;

    }  

}

int main()

{

    transfer1(65533);

    printf("/n");

    return 0;

}

4.2、后缀表达式求值

把中缀算术表达式转换成对应的后缀表达式的规则是：把每个运算符都移到它的两个运算对象的后而，然后删除掉算术表达式。

中缀表达式3/5+6=>后缀表达式3 5 / 6 +

中缀表达式16-9*(4+3)后缀表达式16 9 4 3 + * -

中缀表达式2*(x+y)/(1-x)后缀表达式2 x y + * 1 x - /

中缀表达式(25+x)*(a*(a+b)+b)后缀表达式25 x + a a b + * b + *

假定算术表达式中的每个操作数都是大于等于0的整数，并且算术表达式的语法都是正确的，因而不需要在算法进行语法检查。

后缀算术表达式求值的算法

设定一个栈S，类型为stack，用它来存贮运算的操作数、中间结果以及最后结果。作为此算法的输入，假定在一个字符型数组A中已存放着一个以@字符作为结束符的后缀算术表达，并且该表达式中的每个操作数都是以空格字符结束的。此法的基本思路是：从数组A中的第一个字符起扫描，若遇到的是数字字符，则就把以它开头的一组数字字符(直到遇到空格字符为止)转换成对应的数值(即一个操作数)后压入S栈，若遇到的是运算符，则就从栈顶依次弹出两个操作数，进行相应的运算后，再把结果压入S栈，继续扫描下一个字符，直到遇到@字符为止。算法结束后，S栈顶的值是数组A中后缀算术表达式的计算结果。

#include <stdio.h>

#define StackSize 100/*栈的容量*/

typedef int ElemType;

typedef struct{

            ElemType  data[StackSize];

            int top;

}SqStack;

 

/*初始化*/

void  InitStack(SqStack *s)

{

  s->top=-1;

}

 

/*压栈*/

int push(SqStack *s,ElemType e)

{

  if(s->top<StackSize-1)

  {

     s->top=s->top+1;

     s->data[s->top]=e;

     return 1;

  }

  else

  {

     printf("overflow!/n");

     return 0;

  }

}

 

/*出栈*/

ElemType pop(SqStack *s)

{

  ElemType e;

  if(-1==s->top)

  {

     printf("underflow/n");

     return 1;

  }

  else

  {

     e=s->data[s->top];

     (s->top)--;

     return e;

  }

}

 

 

int comp(char arr[])

{

  SqStack s;

  int i=0;

  char ch;

  int x=0;

  InitStack(&s);

  ch=arr[i];

  while(ch!='@')

  {

     switch(ch)

     {

         case '0':

         case '1':

         case '2':

         case '3':

         case '4':

         case '5':

         case '6':

         case '7':

         case '8':

         case '9':

            while(ch!=' ')

            {

                x=x*10+(ch-'0');

                i=i+1;

                ch=arr[i];

            }

            break;

         case '+':

            x=pop(&s)+pop(&s);

            break;

         case '-':

            x=pop(&s);

            x=pop(&s)-x;

            break;

         case '*':

            x=pop(&s)*pop(&s);

            break;

         case '/':

            x=pop(&s);

            x=pop(&s)/x;

            break;

     }

     push(&s,x);

     x=0;

     i=i+1;

     ch=arr[i];

  }

  return pop(&s);

}

 

int main()

{

  char arr[100];

  printf("请输入您要计算的后缀表达式:");

  gets(arr);

  printf("后缀表达式的计算结果为：%d/n",comp(arr));

  return 0;

}

此算法的运行时间主要花在它从头到尾扫描并处理数组A中的每一个字符，若后缀算术表达式由n个字符组成，则此算法的时间复杂度为O(n)。此算法在运行时所占用的临时空间主要取决于S栈的大小，显然，它的最大深度不会超过表达式中操作数的个数。若操作数的个数为m，则此算法的空间复杂度为O(m)。

4.3、将中缀算术表达式转换成后缀算术表达式

设以@字符结束的一个中缀算术表达式存放在字符型数组E中，而转换后生成的后缀算术表达式用字符型数组A来存放。在转换过程中需要使用一个栈，假定用S2表示，类型为stack，用它来暂存不能立即送入数组A中的算符(其中包括运算符、左右圆括号和表达式结束符)，因此，S2栈的成分类型应为字符型，S2栈的最大深度不会超过中缀算术表达式中算符的个数。

    在中缀算术表达式中，设P1和P2分别表示前后相邻出现的两个算符，那么P1和P2之间的优先关系只能是下列两种情况之一：

    P1<P2  表示P2优先于P1运算或者说P1落后于P2运算

    P2>P2  表示P1优先于P2运算或者说P2落后于P2运算

    根据中缀算术表达式运算的三条规则，相邻算符之间的优先关系如下表所示：

 

 

    当把中缀算术表达式转换成后缀算术表达式时，为了堆栈处理的方便，往往在栈底首选放入一个表达式结束符@，并令它具有最低的优先级，当堆栈处理结束时，会出现表达式最后的@字符同栈底的@字符相遇的情况，此时表明中缀表达式已经转换完毕，所以在表中把它定义为‘=’关系。在表达式处理中，有时还可能遇到右括号与栈顶的左括号比较优先关系的情况，所以也必须对它们给予定义。由于它们在算术表达式中只能同时存在和消失，所以在表中也把它们定义为‘=’关系。在表中还有三处空白，这是P1和P2算符不应该相遇的情况，若发生这种情况，则表明中缀算术表达式中有语法错误。

    把中缀算术表达式转换成对应的后缀算术表达式的算法的基本思路是：从数组E的第一个字符起扫描，当遇到的是数字字符时，就把以它开始的一组数字字符(直到非数字字符为止)和附加的一个空格字符依次送入数组A。当遇到的是算符时，首先检查它是否落后于栈顶算符的运算，若是则表明栈顶算符的两个运算对象已经被送入到数组A中，应将栈顶算符退栈并送入数组A，以此反复进行，直到不落后于栈顶算符为止，接着检查它是否优先于栈顶算符，若是，则表明它的第二个运算对象还没有被送入数组A中，所以应把它进栈，否则表明该算符必然是右括号，栈顶算符必然是左括号。因该括号内的算符已处理完毕，所以应把左括号从栈顶退出；继续扫描下一个字符，直到遇到结束符@后，再做必要的结束处理即可。

    #include <stdio.h>

#define StackSize 100/*栈的容量*/

typedef char ElemType;

typedef struct{

                ElemType  data[StackSize];

                int top;

}SqStack;

 

struct tb1{

        char oper1;

        char oper2;

        char pri;

}opchtb1[49]={{'+','+','>'},{'+','-','>'},{'+','*','<'},{'+','/','<'},{'+','(','<'},{'+',')','>'},{'+','@','>'},

            {'-','+','>'},{'-','-','>'},{'-','*','<'},{'-','/','<'},{'-','(','<'},{'-',')','>'},{'-','@','>'},

            {'*','+','>'},{'*','-','>'},{'*','*','>'},{'*','/','>'},{'*','(','<'},{'*',')','>'},{'*','@','>'},

            {'/','+','>'},{'/','-','>'},{'/','*','>'},{'/','/','>'},{'/','(','<'},{'/',')','>'},{'/','@','>'},

            {'(','+','<'},{'(','-','<'},{'(','*','<'},{'(','/','<'},{'(','(','<'},{'(',')','='},{'(','@','x'},

            {')','+','>'},{')','-','>'},{')','*','>'},{')','/','>'},{')','(','x'},{')',')','>'},{')','@','>'},

            {'@','+','<'},{'@','-','<'},{'@','*','<'},{'@','/','<'},{'@','(','<'},{'@',')','x'},{'@','@','='},};

 

/*初始化*/

void  InitStack(SqStack *s)

{

    s->top=-1;

}

 

/*压栈*/

int push(SqStack *s,ElemType e)

{

    if(s->top<StackSize-1)

    {

        s->top=s->top+1;

        s->data[s->top]=e;

        return 1;

    }

    else

    {

        printf("overflow!/n");

        return 0;

    }

}

 

/*出栈*/

ElemType pop(SqStack *s)

{

    ElemType e;

    if(-1==s->top)

    {

        printf("underflow/n");

        return 1;

    }

    else

    {

        e=s->data[s->top];

        (s->top)--;

        return e;

    }

}

 

//取栈顶

 

int GetTop(SqStack s,ElemType *e)

{

    if (-1==s.top)

    {

        printf("underflow/n");

        return 0;

    }

    else

    {

        *e=s.data[s.top];

        return 1;

    }

}

 

char precede(char w,char ch)

{

    int i=0;

    while(i<49)

    {   if(w==opchtb1[i].oper1 && ch==opchtb1[i].oper2)

            return opchtb1[i].pri;

        i++;

    }

    return 'x';

}

 

void change(char E[],char A[])

{

    SqStack S2;

    InitStack(&S2);

    push(&S2,'@');

    int i=0;    /*i作为扫描数组E的指针*/

    int j=0;    /*j用来指示数组A中待写入字符的位置*/

    char ch=E[i];   /*E中第一个字符送给ch*/

    char w;

    while (ch!='@')

    {

        if(ch>='0' && ch<='9')

        {

            while(ch>='0' && ch<='9')

            {

                A[j]=ch;

                j++;

                i++;

                ch=E[i];

            }

            A[j]=' ';

            j++;    /*给A中的每个操作数后附加一个空格*/

        }

        if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='@')

        {

            GetTop(S2,&w);

            while (precede(w,ch)=='>')

            {

                A[j]=w;

                j=j+1;

                pop(&S2);

                GetTop(S2,&w);

            }

            if (precede(w,ch)=='<')

                push(&S2,ch);

 

            else

                w=pop(&S2);

        }

        if(E[i]!='@')

            i++;

        ch=E[i];       

    }

    while(w!='@')

    {

        A[j]=w;

        j++;

        w=pop(&S2);

    }

    A[j]='@';

    A[++j]='/0';

    printf("后缀表达式为：%s/n",A);

}

 

int main()

{

    char E[100];

    char A[180];

    printf("请输入中缀表达式:");

    gets(E);

    change(E,A);

    return 0;

}

 

从上面算术表达式的计算过程可以看出，利用后缀表示和堆栈技术只需两遍扫描即可完成，其中第一遍是把算术表达式的中缀表示转换成对应的后缀表示，第二遍是根据后缀表示进行求值。显然它比直接利用中缀算术表达式进行计算的扫描次数要少得多