你所能用到的数据结构（八）

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

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

好了，废话不多说了，堆栈作为一个最简单的数据结构，其纯应用不多，但是堆栈作为一种基础的数据结构是实现复杂数据结构和复杂算法的必备产品，这也让堆栈非常有可能成为数组之后最基本数据结构，这句话你可以理解为以后的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+22+1,如何让计算机知道优先级是什么概念？让计算机在看到这个算式的时候不是得出7而是得出6，再通俗一点怎样让计算机从普通计算器进化到科学计算器？当然方法很多，最简单的，维护一个表用来说明好了，但是这个方法耗费的资源太大，但是这位伟大的逻辑学家的方法却很巧妙的解决了这个问题（当然，这个解法最开始不是为了计算机设计的，因为1929年，计算机还没有造出来），怎样通过重新排列这些数来使得优先级本身就蕴含在算式之中呢？我们可以尝试着在计算一个算式的时候先不进行计算，只有确认没有优先级更高的运算符的时候再进行计算，怎样从这种普通的表达式转换成为后缀表达式我在后面会进行说明，现在按照某种我已经知道的方法（可能你也知道）这个算式的后缀表达式是122+1+，这虽然看起来很变扭，但这也是一种表达式，其计算方式就是从左往右扫描，如果遇到一个运算符就把前面两个操作数按照此运算符的方式运算直至最右边。比如这个算式，从左开始依次读入1,2,2，2的后面是一个乘号，那么计算22=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++的时候就这么干的）。运行结果如下：

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

原文链接: https://www.cnblogs.com/ZXYloveFR/archive/2012/10/10/2718518.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍