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

栈的应用

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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏前端进阶之路

JavaScript数据结构02 - 栈

通过前面一节《JavaScript数据结构01 - 数组》我们知道,可以在数组的任意位置上删除或添加元素。然而,有时候我们还需要一种在添加或删除元素时有更多控制...

10320
来自专栏java一日一条

Java 动态代理深入解析

要想了解Java动态代理,首先要了解什么叫做代理,熟悉设计模式的朋友一定知道在Gof总结的23种设计模式中,有一种叫做代理(Proxy)的对象结构型模式,动态代...

10350
来自专栏沈唁志

PHP中系统函数http_build_query系统函数使用方法

17940
来自专栏java达人

设计模式之代理模式(二)CGLIB动态代理实现

像上一篇所说的代理模式其实是静态代理,在实际开发中其实应用不大,因为他需要事先知道被代理对象是谁,而且被代理对象和代理对象实现了公共的接口。实际情况往往并不能满...

206100
来自专栏令仔很忙

新手学JAVA(二)----String类与StringBuffer类的区别

在Java中有两种字符串的操作:String类和StringBuffer类(缓冲字符串处理类)。 下面先简单的说一下两者的区别。 String类和St...

13020
来自专栏Java进阶之路

Java8新特性实践

19400
来自专栏小樱的经验随笔

isdigit函数

isdigit是计算机应用C语言中的一个函数,主要用于检查参数c是否为阿拉伯数字0到9。 相关函数 isdigit 表头文件 #i...

31180
来自专栏项勇

笔记29 | 整理Java的容器类

20340
来自专栏林冠宏的技术文章

Deque的部分成员函数 解析,关于这个类,百度有很多解析,唯独没有其函数介绍

函数 描述 c.assign(beg,end) c.assign(n,elem) 将[beg; end)区间中的数据赋值给c。 ...

19580
来自专栏赵俊的Java专栏

最大子数组

14750

扫码关注云+社区

领取腾讯云代金券