数据结构与算法 -- 栈的应用（进制转换、括号匹配）

cMusketeer

发布于 2018-12-05 10:54:46

2.2K0

发布于 2018-12-05 10:54:46

文章被收录于专栏：Android机器圈

栈的应用

ps：用栈很简单实现的应用有很多，比如说进制转换，括号匹配等。学计算机的都知道，2进制，8进制，10进制，16进制等，进制之间的转换也是需要掌握的，以备不时之需，所以我们可以自己写一段程序如果会android的话，可以直接打包成APK。下面就按照这两个应用稍微写一点C语言的代码。

进制转换
括号匹配

1：进制转换

　　想要自己做一个进制转换的工具，首先我们要知道如何实现进制之间的转换，我们平常用的都是10进制，如果想要转成8进制怎么办，按照方法，如图

可以看到，N是我们输入的10进制数，除以8，余数保留在栈中，得到的168接着与8整除运算，直到N div 8 等于0，最后把栈中数据取出即可，正好用到了栈的规则，先进后出的特性。

1.1：定义栈结构体

typedef struct zhan{
    int data;
    struct zhan *next;
}zhan,*ZhanL;

1.2：初始化栈

/**
 * 初始化栈
 * */
ZhanL initZhan(){
    ZhanL L =(ZhanL)malloc(sizeof(zhan));
    L->next=NULL;
    return L;
}

1.3进栈出栈操作

在pop方法中，把L赋给s，主要是出栈后，把空余的栈位释放掉，push方法用到了尾插法。

/**
 * 进栈操作
 * */
int push(ZhanL &L,int data){
    //创建一个新的结点
    ZhanL p=(ZhanL)malloc(sizeof(zhan));
    p->data=data;
    p->next = L;
    L = p;
    return 0;
}
int pop(ZhanL &L){
    if(L->next){
        ZhanL s=L;//释放空间用
        printf("%d ",s->data);
        L = L->next;
        if(L->next){
//            printf("栈顶%d \n",L->data);
        } else{
            printf("栈空\n");
        }
        free(s);
    }
    return 0;
}

1.4：转换方法

/**
 * 转换方法
 * */
 int zhuanhuan(ZhanL &L,int data,int jz){
     while (data){
         push(L,data%jz);
         data = data/jz;
     }

     while (L){
         pop(L);
     }
    return 0;
 }

1.5：使用

int main(){
    ZhanL L;
    L=initZhan();
    printf("请输入一个十进制数");
    int data,jz;
    scanf("%d",&data);
    printf("请输入转换的进制");
    scanf("%d",&jz);
    zhuanhuan(L,data,jz);
    return 0;
}

结果图：

2：括号匹配

什么是括号匹配？

在编写代码的时候，经常会用到两种括号：圆括号 “()” 和大括号 “{}” 。不管使用哪种括号，程序编译没有问题的其中一个重要因素就是所使用的括号是否能够匹配上. 在编写程序时，括号可以嵌套，即： “({()})” 这种形式，但 “({)” 或者 “({}” 都不符合要求。

思路：

我们可以从键盘录入字符，通过空格分开，在如果是左边括号（ { ），就入栈，如果是右边括号( } )就出栈进行比较，看是否输入一对括号，如果匹配，就进行下一个比较，否则return，就没有再比较的必要了。因为上面有栈的入栈和出栈，这里就不在给出，使用上面即可.

注意：把上面结构体中int型，改成char型。

2.1:括号匹配算法

从控制台正常输入，空格隔开，遇见m结束，在输入期间，检测到左括号，进栈，右括号就要和和左括号比较，如何比较呢，我们可以把右括号翻转，说白了就是遇见右括号就让它变成指定的左括号形式，如：if(ch == '}') 这时就可以把ch改成 { 再和栈中元素进行比较。

int main(){
    ZhanLink zhanLink;
    zhanLink = initLink();
    char ch;
    while(ch != 'm'){
        scanf("输入%c  ",&ch);
        ch = getchar();
        switch (ch){
            case '{':
            case '(':
                push(zhanLink,ch);
                break;
            case '}':
            case ')':
//                printf("      %c\n",ch);
                char e=pop(zhanLink);

                if(ch == '}'){
                    ch='{';
                }else if(ch == ')'){
                    ch = '(';
                }
//                printf("修改后%c\n",ch);
                if(e == ch){
                    if(ch == '{'){
                        ch='}';
                    }else if(ch == '('){
                        ch = ')';
                    }
                    printf("匹配%c %c\n",e,ch);
                }else{
                    printf("括号不匹配\n");
                    return 0;
                }
                break;
        }
    }
    printf("匹配合理");

//    pop(zhanLink);

    return 0;
}