你所能用到的数据结构(八)

十一、不能被应用的理论不是好研究

前面介绍了堆栈的一些小小的理论模型,那么这样一个东西有什么作用呢?实际中不可能有那么一辆停在站台前方堵死的火车的,即使有,也不需要用什么计算机的数据结构模拟。如果一个理论没有其运用价值那么它的归宿只能是慢慢被人淡忘,但是也有个别例外的,比如线性代数在发明之时被认为毫无用武之地,但是在很多年后线性代数成为了量子力学的数学技术,乃至现在信息科学的数学基础,相比这个例子,没有找到用武之地而最终被人遗忘与沙海的理论还是占了绝大多数,所以,说了这么多,在编码这种实际操作性强的事物上你能学到的大部分理论模型能展现在你的面前,都说明这些理论在实践中已经有了很广泛的应用,并且大多数都是可行的应用。这句话反过来也可以理解为,如果你在看一些经典的算法和数据结构书的时候不能实现其中的一些算法,大部分情况下应该思索我哪里弄错了,不应该思考是不是算法有问题,还有我觉得就是无论多小的一个程序,都应该动手试试,如果程序简单,花不了多少时间,如果难,花了很多时间理解了个算法,还是非常值得了,毕竟,这世界上,能完全理解的事情不多,而且我的感触就是很多的时候困难就像是你走大道走多了突然碰见一个小道,走完这个小路,往往真有豁然开朗的感觉。

       好了,废话不多说了,堆栈作为一个最简单的数据结构,其纯应用不多,但是堆栈作为一种基础的数据结构是实现复杂数据结构和复杂算法的必备产品,这也让堆栈非常有可能成为数组之后最基本数据结构,这句话你可以理解为以后的C++或者什么语言编程里面,不需要引用什么头文件就可以像声明数组一样声明一个堆栈,然后很方便的就可以使用这个结构。这里我要介绍的两个堆栈的应用都和编译有关系,或者说和编译原理有关系,这也印证了一个道理,最基础的东西往往能在很复杂的程序系统中发挥最坚实的作用,所以真的不可以小看任何一个不起眼的事物。因为堆栈本身很简单,很基本,所以两个应用也很简单,但是还是包含了编程的一些知识的,动手还是值得的。

      第一个,是检测括号的匹配,在你用VS编程,写完一点程序,点debug的时候,你的IDE可以准确的找出你的括号有没有匹配,如果没有,那么一定会给出提示,然后编译不通过,这个功能就是由堆栈实现的,一个大的IDE也是由一点一点的小功能模块组合起来的,这也是编译的第一步,那么这个问题的解决方法其实是很简单的,我们考虑三种括号:大括号,中括号和小括号。先是有一个空的堆栈,我们采用文件流的方式读入一段程序,忽略除了这三种括号以外的其他字符,怎么检查是不是匹配的呢?因为括号都是成对出现的,但是在一个程序中就括号而言完全可能出现{()}这样的顺序,先观察一下,发现如果括号是匹配的,无论的括号之间的包含关系是什么,那么当出现右括号时,它的前一个不是对应的左括号,那么一定是不匹配的,比如{{)},所以从观察中我们可以整理出思路,当遇到左括号时,我们将符号压栈,如果读到一个右括号,那么去查看栈顶的元素(因为栈顶元素一定是这个符号的前一个元素),如果匹配,那么弹出栈顶元素,如果不匹配,那么什么也不做(当然,这里可以优化成为如果不匹配直接结束),这样,最终完全匹配的条件就是在程序将符号全部读完之后,堆栈是空的,不然都为不匹配。我复制了一段程序作为测验数据。

     按照上面的思路,我们可以写出下面这样的代码:

void main()
{
  
    char input;
    ifstream fin("input.txt");
    Stack s;
    char top;
    while(!fin.eof())
    {
 
        fin>>input;
        if(fin.fail())
             break;
        switch(input)
        {
        case '{':
        case '(':
        case '[':
            s.Push(input);
            break;
        case '}':
            top=s.Top();
            if(top=='{')
                s.Pop();
            break;
        case ')':
            top=s.Top();
            if(top=='(')
                s.Pop();
            break;
        case ']':
            top=s.Top();
            if(top=='[')
                s.Pop();
            break;
        } 

    }

    if(s.CheckEmpty())
        cout<<"match"<<endl;
    else
        cout<<"not match"<<endl;
}

    按照测试文件,结果是match,你也可以找一个不匹配的输入文件试试看。

     第一个应用很简单,第二个应用也是每本书上都会用的逆波兰表达式,为什么我还是觉得应该举这个例子呢?因为到后面进行树的遍历的时候你就会明白我的意思了,哈哈,那先介绍一下什么叫逆波兰表达式吧,先看看官方解释 “逆波兰表达式又叫做后缀表达式。在通常的表达式中,二元运算符总是置于与之相关的两个运算对象之间,所以,这种表示法也称为中缀表示。波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法。按此方法,每一运算符都置于其运算对象之后,故称为后缀表示。”其实可以理解为把符号卸载数字的后面,虽然很变扭,但不得不说对于计算机它解决了一个很重要的问题,比如对于一个算式1+2*2+1,如何让计算机知道优先级是什么概念?让计算机在看到这个算式的时候不是得出7而是得出6,再通俗一点怎样让计算机从普通计算器进化到科学计算器?当然方法很多,最简单的,维护一个表用来说明好了,但是这个方法耗费的资源太大,但是这位伟大的逻辑学家的方法却很巧妙的解决了这个问题(当然,这个解法最开始不是为了计算机设计的,因为1929年,计算机还没有造出来),怎样通过重新排列这些数来使得优先级本身就蕴含在算式之中呢?我们可以尝试着在计算一个算式的时候先不进行计算,只有确认没有优先级更高的运算符的时候再进行计算,怎样从这种普通的表达式转换成为后缀表达式我在后面会进行说明,现在按照某种我已经知道的方法(可能你也知道)这个算式的后缀表达式是122*+1+,这虽然看起来很变扭,但这也是一种表达式,其计算方式就是从左往右扫描,如果遇到一个运算符就把前面两个操作数按照此运算符的方式运算直至最右边。比如这个算式,从左开始依次读入1,2,2,2的后面是一个乘号,那么计算2*2=4,接着读到一个加号,那么计算1+4=5,继续读是1,然后又是加号,计算出正确结果为6。对比上面的应用,堆栈也是这个算法所实行的一个载体(不要以为简单就不能叫算法),只要不是运算符,我们就一直读数字,遇到运算符将栈顶数字相加再压回堆栈中,最后得到就是结果。这里为了简单,我所采用的例子只有加法和乘法,而且一定是10以内的,因为这些都不是重点,如果你有兴趣扩展的话,我相信一定是很简单的。我模拟的是一个(1+2)*(2+1)的算式,这个转换成为后缀表达式是12+21+*,因为括号拥有最高的优先级,那就先看看代码:

 1 void main()
 2 {
 3 string expression="12+21+*";
 4     int count=1;
 5     Stack s;
 6     for(int i=0;i<expression.length();i++)
 7     {
 8          cout<<"round: "<<(i+1)<<endl;
 9         if('0'<=expression[i]&&expression[i]<='9')
10            s.Push(expression[i]);
11         else
12         {
13            
14             int first,second,result;
15             switch(expression[i])
16             {
17             case '+':
18                 first=s.Pop()-'0';
19                 second=s.Pop()-'0';
20                 s.Push(first+second+'0');
21                 break;
22             case '*':
23                 first=s.Pop()-'0';
24                 second=s.Pop()-'0';
25                 s.Push(first*second+'0');
26                 break;
27             }
28           
29            
30         }
31          for(int i=0;i<s.GetCount();i++)
32            printCube(s.GetValue(i));
33     }
34     cout<<(int)(s.Pop()-'0')<<endl;
35 }

      这里一个小小的技巧就是对于一个char型的数字,直接减去'0'就能获得其int值,这个技巧可以省掉很多转换中的麻烦,如果你用switch case进行判断的话,那么就太浪费时间了(我初学c/c++的时候就这么干的)。运行结果如下:

     每一轮的堆栈的造型我都显示出来了,可以看到没遇到一个运算符,堆栈里面的造型就会大变样,我忘了输出每次压入的字符,对照着程序看一下吧,应该不会太费事。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏鹅厂优文

Python 工匠:善用变量来改善代码质量

我一直觉得编程某种意义上是一门『手艺』,因为优雅而高效的代码,就如同完美的手工艺品一样让人赏心悦目。

1K100
来自专栏互联网技术栈

设计模式- 合成/组合原则

上面的问题都来源于对方法的改写动作。如果你在扩展一个类的时候,仅仅是增加新的方法,而不改写已有的方法,你可能会认为这样做是安全的,但是也并不是完全没有风险。

13040
来自专栏编程

Python利器之迭代器

各位小伙伴们 大家周四愉快 今天要和大家探讨一个 Python的特色功能 也是Python有别于其他变成语言的 强大利器 迭代器 迭代这一个词可能有的小伙伴不理...

19870
来自专栏码洞

天下无难试之HashMap面试刁难大全

HashMap的结构无疑是Java面试中出现频率最高的一道题,这个题是如此之常见,应该每个人都会信手拈来。可是就在我经历过的无数【允许我夸张一下】面试当中,能完...

11320
来自专栏JAVA高级架构开发

Java 程序员必须掌握的 8 道数据结构面试题,你会几道?

瑞士计算机科学家Niklaus Wirth在1976年写了一本书,名为《算法+数据结构=编程》。

2.7K00
来自专栏技术墨客

Java函数式开发——优雅的Optional空指针处理

    在Java江湖流传着这样一个传说:直到真正了解了空指针异常,才能算一名合格的Java开发人员。在我们逼格闪闪的java码字符生涯中,每天都会遇到各种nu...

14220
来自专栏我杨某人的青春满是悔恨

《编程的智慧(初稿)》读后感

王垠更新了文章,加入了Optional跟Union比较的内容,所以我也来更新一下。垠神认为Optional并没有什么卵用,Java8的Optional我不是很了...

12920
来自专栏小詹同学

【记录帖】(No.001)从零打卡刷Leetcode

小詹一直觉得自己编程能力不强,想在网上刷题,又怕不能坚持。不知道有木有和小伙伴和小詹一样想找个人一起刷题呢?欢迎和小詹一起定期刷leetcode,每周一周五更新...

13030
来自专栏AI科技大本营的专栏

送书 | 跟我一起学《流畅的Python》

本文引自图灵新书《流畅的Python》的第一章——Python数据模型。本书由奋战在Python开发一线近20年的Luciano Ramalho执笔,Victo...

42840
来自专栏斑斓

深入探索Scala的Option

程序员最深恶痛绝并力求避免的异常是NullPointerException,很不幸,我们往往又会忽略这个错误。不知是谁设计了Null这样的对象。我在文章《并非N...

34370

扫码关注云+社区

领取腾讯云代金券