【数据结构与算法】 栈——栈的应用举例(3例)

  • Post author:
  • Post category:其他




根据“后进先出”特性,生活中的例子比比皆是。






1数制转换



假设要讲十进制转换为二进制。以 52 为例,如图:





在上述

计算过程中,第一次求出的X值为最低位,最后一次求出的X值为最高位。而打印时应从高位到低位进行,恰好与计算过程相反。根据这个特点,我们可以通过入栈出栈来实现,即将计算过程中依次得到的二进制数码按顺序进栈,计算结束后,再顺序出栈,并按出栈顺序打印输出。即可得到给定的二进制数。这是利用栈后进先出特性的最简单例子。


void Conversion(int N){
    /*对于任意的一个非负十进制数N,打印出与其对应的二进制数*/
    Stack S;
    int x;
    InitStack(&S);
    while (N>0) {
        x=N%2;
        Push(&S,x); //将余数压入栈S
        N=N/2;
    }
    while (!IsEmpty(&S)) {
        Pop(&S,&X);
        printf("%d",x);
    }
}





2括号匹配问题



假设表达式有三种括号:圆括号“()”,花括号“{}”,方括号“[]”。它们可互相嵌套,如{([])}或{([])()[]}均为正确格式。而{)),{[()]均为不正确格式。如何检测其正确性?可以应用栈。



我们以“{[()]}”为例,依次读取括号,如图:




注意,上面写的双双出栈其实是,左括号出栈。


void BrackerMatch(char *str){
    Stack S;
    int i;
    char ch;
    InitStack(&S);
    for (i=0;str[i]!='/0';i++)
    {
        switch (str[i]) {
            case '(':
            case '[':
            case '{':
                Push(&S,str[i]);
                break;
            case ']':
            case '}':
            case ')':
                if (IsEmpty(&S)) {
                    printf("\n 右括号多余!");
                    return;
                }else{
                    GetTop(&S,&ch);
                    if(Match(ch,str[i])) //用 Match 判断两个括号是否匹配
                        Pop(&S,&ch);     //已匹配的左括号出栈
                    else{
                        printf("\n对应的左右括号不同类");
                        return;
                    }
                }
            default:
                break;
        }
        if (IsEmpty(&S))
            printf("\n括号匹配!");
        else
            printf("\n左括号多余!");
    }
}






3



表达式求值



表达式求值是高级语言编译中的一个基本问题,是栈的典型应用实例。



1+2*3/(1+5)=2



任何一个表达式都是由数(操作数)和符号(运算符+-*/,界限符())组成。



而符号又有优先级,优先计算得到的值再作为数继续运算,当符号用尽后,值即为所得。


1+2*3/(1+5)   –>   1+6/(1+5)   –>   1+6/6   –>   1+1   –>   2




优先级规则:



(1)先左后右



(2)先乘除,后加减



(3)先括号内,后括号外




此时需要两个栈,一个称作operator,用以存放符号。一个称作operand,用于存放操作数或中间结果。下图,为即将要用到的算符之间的优先关系。




算法的基本过程如下:



初始化两个栈,然后讲表达式起始符“#”压入operator栈。



输入表达式,以“#”结尾。



依次读取表达式,读取过程中,若是操作数,直接入栈operand。若是符号,则与operator栈顶运算符进行比较。



(1)若 栈顶符<刚读运算符 : 刚读运算符 进栈;



(2)若 栈顶符>刚读运算符 : 进行计算,operator栈顶符退栈,送入x,同时将operand栈退栈两次,得到a,b,对a,b,x进行运算后,将结果作为中间结果推入operand栈;



(3)若 栈顶符=刚读运算符 : 说明是左右括号相遇,栈顶符退栈即可;



当operator栈的栈顶符和当前符都为“#”时,说明求值完毕。

以(10+2)*3# 为例,如图:


当栈顶符和当前符都是“#”,计算结束

int ExpEvaluation(){
    /*operator为符栈,operand为数栈,OPS为运算符集合*/
    InitStack(&operand);
    InitStack(&operator);
    Push(&operator,'#');
    printf("\n输入一个表达式(以#结束)");
    ch=getchar();
    while(ch!='#'||GetTop(operator)!='#'){ //GetTop 取栈顶
        if (!In(ch,OPS)) {                  //不是操作符,是操作数
            int temp;
            temp=ch-'0';                //数的临时变量,并转换为十进制
            ch=getchar();
            while (!In(ch,OPS)) {        //数可能不只有一位,如100就要读三次
                temp=temp+10+ch-'0';
                ch=getchar();
            }
            Push(&operand,temp);
        }
        else
            switch (Compare(GetTop(operator),ch)) {
                case '<':
                    Push(&operator,ch);
                    ch=getchar();
                    break;
                case '=':
                    Pop(&operator,&x);
                    ch=getchar();
                    break;
                case '>':
                    Pop(&operator,&op);
                    Pop(&operand,&b);
                    Pop(&operand,&a);
                    v=Execute(a,op,b);   //对a和b进行op运算
                    Push(&operand,v);    //注意这里没有 ch=getchar()
                    break;
            }
    }
    v=GetTop(&operand);
    return v;
}

以上均为学习耿国华的《数据结构-c语言》笔记





版权声明:本文为TW_345原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。