栈的经典运用

    栈是计算机术语中比较重要的概念，实质上栈就是一段内存区域，但是栈满足一定的特性，那就是只有一个口，具有先入后出的特性，这种特性在计算机中有很广泛的运用。其实在程序员无时无刻不在运用栈，函数的调用是我们间接使用栈的最好例子，因此可以说栈的一个最重要的运用就是函数的调用。但是栈的运用还不止这些，还有很多，其中几个典型的运行如下：判断平衡符号，实现表达式的求值（也就是中缀表达式转后缀表达式的问题以及后缀表达式求值问题），在路劲探索中实现路劲的保存也可以说是栈的经典运用之一。具体的问题具体分析，只要满足先入后出特性的问题都能找到现成的数据结构---栈。

    本文采用C++中的vector实现栈结构，然后利用栈实现判断平衡符号，实现中缀表达式到后缀表达式的转换，并依据栈实现简单的整数加减乘除运算。

   

首先栈的实现，由于在C++中采用了vector来代替原始的数组操作，这种比较方便的容器能较好的实现数组的功能，当然栈也可以采用链表实现，但是我认为链表没有数组直观，而且在实际的计算机里也是采用连续的存储空间作为栈空间的，因此选择Vector。主要实现三个操作，push、pop以及为空判断。基本的形式如下：

#ifndef __MYSTACK_H_H_
#define __MYSTACK_H_H_

#include "myvector.h"

namespace myspace
{
        template<typename Object>
        class Stack
        {
        public:
                Stack(){}
                void push(const Object &x)
                {
                        objects.push_back(x);
                }

                const Object &pop()
                {
                        int len;
                        if(!isempty())
                        {
                                objects.pop_back();
                                len = objects.size();
                                return objects[len];
                        }
                }

                bool isempty()const
                {
                        return (objects.size() == 0);
                }

                int size()
                {
                        return objects.size();
                }
        private:
                Vector<Object> objects;
        };
}

#endif

实现了简单的栈类，接下来采用栈实现一些简单的运用。

 

符号的平衡问题

在语言中往往需要判断一些符号是否是成对出现的，比如<>,{},[],()，通常在C++中也只有这几种对称问题，如何让判断符号的对称也是很多代码判断的首要任务。当然实现的方式是多种多样的，采用栈的实现会相对更加简单。基本的实现思路如下：

假设在读入一串字符串以后，如果遇到对称符号的左边部分，则将其压入栈中，当遇到对称符号的右边部分，则弹出栈中的一个对象，实现比对，如果是对称的，则说明当前的符号是平衡的，如果不对称，则说明当前字符串是不平衡的，当字符串读完以后，如果所有的符号都是平衡的，栈中此时应该就是为空，通过判断栈中是否为空，说明字符串是否是符号平衡的。

依据上面实现的栈类，实现符号平衡判断的过程比较简单，如下所示：

bool isbalance(const string &str)
{
        string::size_type len = str.size();

        Stack<char> stack;

        for(string::size_type i = 0; i < len ; ++ i)
        {
                /*first selection*/
                if(str[i] == '[' || str[i] == '{' ||
                   str[i] == '(' || str[i] == '<')
                {
                        stack.push(str[i]);
                }
                /*如果是对称的符号，则从栈中弹出*/
                if(str[i] == ']' || str[i] == '}' ||
                   str[i] == ')' || str[i] == '>')
                {
                        /*如果栈中没有对象，则说明不平衡*/
                        if(stack.isempty())
                        {
                                cout << "the string is Unblanced" << endl;
                                return false;
                        }
                        /*采用switch-case语句判断*/
                        switch(str[i])
                        {
                                case ']':
                                {
                                        /*判断是否是匹配的*/
                                        if('[' != stack.pop())
                                        {
                                                cout << "Can not blanced with ]" << endl;
                                                return false;
                                        }
                                        break;
                                }
                                case ')':
                                {
                                        if('(' != stack.pop())
                                        {
                                                cout << "Can not blanced with )" << endl;
                                                return false;
                                        }
                                        break;
                                }
                                case '}':
                                {
                                        if('{' != stack.pop())
                                        {
                                                cout << "Can not blanced with }" << endl;
                                                return false;
                                        }
                                        break;
                                }
                                case '>':
                                {
                                        if('<' != stack.pop())
                                        {
                                                cout << "Can not blanced with >" << endl;
                                                return false;
                                        }
                                        break;
                                }
                                /*一般的非对称字符*/
                                default:
                                        break;
                        }
                }
        }
        /************************************************
        *当所有对象遍历完成以后，需要判断栈中是否存在对象
        *栈中为空说明是平衡的，非空则说明是非空的对象
        ************************************************/
        if(stack.isempty())
        {
                cout << "string is blanced!!" << endl;
                return true;
        }
        else/*没有正确的匹配,并输出具体不匹配的符号*/
        {
                cout << stack.pop() << " " << "Unblance string!!" << endl;
                return false;
        }
}

采用上面的代码能够符号是否平衡的判断。

 

接下来说明一下表达式的求值问题，表达式的求值问题主要设计到操作符的优先级问题，比如（）、*/、+-这几种符号的优先级是不一样的，其中括号的优先级最好，乘除其次，加减最低，我们通常看到的表达式都是中缀表达式，也就是在操作符的两边都有对象，当然括号除外啦，这种中缀表达式是不便于在程序中处理的，因为存在很多的优先级差别，很难把握从那个位置先计算。

 

如果在表达式中没有了优先级的问题，求值问题也就变得相对来说更加简单了，后缀表达式是一种非优先级的表达式表示方式，但是如何实现中缀表达式到后缀表达式的切换也是很难实现的。

 

中缀表达式到后缀表达式的实现如下:

中缀表达式：
a*b+c*d-e/f
后缀表达式：
ab*cd*+ef/-

从上面的表达式可以知道后缀表达式相对来说比较容易判断计算的基本过程，而且不存在括号的烦恼。采用栈实现转换的基本思路如下：

对一个中缀表达式进行遍历，当遇到非操作符的字符直接保存到后缀表达式的存储空间中，如果遇到左括号，则将左括号压入栈中,因为优先级最高，只有遇到右括号才会被弹出。如果遇到右括号，则将左括号之前的操作符全部弹出，并保存到后缀表达式的存储空间中，当然这种存储的顺序和出栈的顺序是一致的，括号操作符在后缀表达式中是不存在的，因此不需要将括号保存到后缀表达式的存储空间中。如果遇到乘除操作符（*/），则判断栈中的操作符优先级是否低于当前的操作符也就是判断是否是加减操作符，如果不是则将栈中的操作符（也就是*、/），并保存到后缀表达式存储空间中，然后将当前的操作符压入栈中，如果是则直接将操作符入栈。如果操作符是加减操作符，则弹出栈中左括号之前的所有操作符，并保存到后缀表达式存储空间中，然后将操作符本身压入栈中。当字符串遍历完成以后，依次弹出操作符，并保存到后缀表达式存储区中。

通过上面处理的中缀表达式就能完成后缀的转换，但是由于需要比较操作符的优先级问题，因此可能需要出栈以后，直接将对象又压栈的问题，这是实现这类转换时需要注意的。基本的实现如下：

/*****************************************
 * 实现表达式中缀到表达式后缀的转换
 *****************************************/
bool midtolast(string &src, string &dst)
{
        string::size_type len = src.size();

        /*用来保存栈中弹出的对象*/
        char temp = '\0';

        Stack<char> stack;

        for(string::size_type i = 0; i != len; ++ i)
        {
                switch(src[i])
                {
                        /*如果是'(',则将左括号压入栈中*/
                        case '(':
                        {
                                stack.push(src[i]);
                                break;
                        }
                        /*如果是')',则将栈中左括号之前的对象弹出*/
                        case ')':
                        {
                                /*如果为空，则说明表达式不准确*/
                                if(stack.isempty())
                                {
                                        return false;
                                }
                                /*非空，弹出对象*/
                                temp = stack.pop();
                                /*只要不是左括号，则全部弹出*/
                                while('(' != temp )
                                {
                                        /*并输出到后缀表达式中*/
                                        dst += temp;
                                        /*保证栈为非空*/
                                        if(stack.isempty())
                                                break;
                                        /*弹出新的对象*/
                                        temp = stack.pop();
                                }
                                /*如果弹出的是左括号，则不用输出到后缀表达式*/
                                break;
                        }

                        /***************************************
                        乘除法操作实质上是一致的
                        在压入栈中之前，需要弹出非左括号的同优先级对象
                        遇到左括号或者低优先级的对象就停止，直接入栈
                        ****************************************/
                        case '*':
                        case '/':
                        {
                                /*判断非空的栈，为空则直接入栈即可*/
                                if(!stack.isempty())
                                {
                                        temp = stack.pop();
                                        while(temp != '+' && temp != '-' && temp != '(')
                                        {
                                                dst += temp;
                                                if(stack.isempty())
                                                {
                                                        /*保证temp不影响后面的压栈操作*/
                                                        temp = '\0';
                                                        break;
                                                }
                                                temp = stack.pop();
                                        }
                                }
                                /*如果当前的temp是+-(,则返回到栈中*/
                                if(temp == '+' || temp == '-' || temp == '(')
                                {
                                        stack.push(temp);
                                }
                                /*将当前操作符压栈*/
                                stack.push(src[i]);

                                break;
                        }
                        case '-':
                        case '+':
                        {
                                /*判断非空*/
                                if(!stack.isempty())
                                {
                                        /*加减操作的优先级最低，因此需要弹出所有非左括号的操作符*/
                                        temp = stack.pop();
                                        while(temp != '(' )
                                        {
                                                /*将操作符输出到后缀表达式中*/
                                                dst += temp;
                                                if(stack.isempty())
                                                {
                                                        temp = '\0';
                                                        break;
                                                }
                                                temp = stack.pop();
                                        }
                                }
                                /*如果当前弹出的对象是’(‘,则重新压入栈中*/
                                if(temp == '(')
                                {
                                        stack.push(temp);
                                }
                                /*将操作符本身压入栈中*/
                                stack.push(src[i]);
                                break;
                        }
                        default:
                        {
                                /*针对字符而言直接输出到后缀表达式*/
                                dst += src[i];
                                break;
                        }
                }
        }
        /*将栈中非空的操作符输出到后缀表达式中*/
        while(!stack.isempty())
        {
                temp = stack.pop();
                dst += temp;
        }
        return true;
}

后缀表达式求值的问题，实现了后缀表达式的转换，实现表达式的求值问题也就比较简单了，实现的基本思路如下：

遍历后缀表达式，遇到非操作符的字符则直接压入栈中，如果遇到操作符则从栈中弹出两个对象，进行对应的操作，然后将计算的结果又压入栈中。继续遍历，直到表达式被遍历完成，此时栈中保存的值也就是当前表达式的值，需要注意除法和减法的操作数顺序问题以及除数不能为0的。为了说明该方法的准确性，我采用0-9以内的数作为操作数，进行4则运算，目前我还只能实现这些计算，对于复杂的多位数还需要另外的处理。实现的代码如下：

/*后缀表达式求值问题*/
int retVal(const string &src)
{
        Stack<int> stack;
        int temp = 0, s = 0;

        int len = src.size();
        for(string::size_type i = 0; i != len; ++ i)
        {
                /*本程序只能处理整形的加减乘除操作*/
                switch(src[i])
                {
                        /*遇到数值直接压入栈中*/
                        case '0':case '1':case '2': case '3': case '4':
                        case '5':case '6':case '7': case '8': case '9':
                        {
                                stack.push(myatoi(src[i]));
                                break;
                        }
                        /*********************************************
                        * 遇到操作符弹出两个数值进行操作
                        * 需要注意减法和除法的压栈顺序
                        * 操作完成以后将得到的结果压入到栈中
                        * 最后栈中的值就是计算的结果
                        **********************************************/
                        case '+':
                        {
                                temp = stack.pop() + stack.pop();
                                stack.push(temp);
                                temp = 0;
                                break;
                        }
                        case '-':
                        {
                                s = stack.pop();
                                temp = stack.pop() - s;
                                stack.push(temp);
                                s = 0;
                                temp = 0;
                                break;
                        }
                        case '*':
                        {
                                temp = stack.pop() * stack.pop();
                                stack.push(temp);
                                temp = 0;
                                break;
                        }
                        case '/':
                        {
                                s = stack.pop();
                                if(s != 0)
                                {
                                        temp = stack.pop() / s;
                                }
                                stack.push(temp);
                                s = 0;
                                temp = 0;
                                break;
                        }
                }
        }
        /*获得最后的值*/
        return stack.pop();
}

为了分析上面的代码准确性，写了如下的测试代码：

int main()
{
        string s1;
        cout << "Input a string to test the balance :" << endl;
        cin >> s1;
        isbalance(s1);
#if 10
        string src;
        string dst;
        cout << "Input a expression: " << endl;
        cin >> src;
        midtolast(src,dst);
        cout << "After the convertion: " << endl;
        cout << dst << endl;
        cout << "The result of expression: " << endl;
        cout << retVal(dst) << endl;
#endif
        return 0;
}

测试结果：

[gong@Gong-Computer data_struct]$ vi testblance.cpp
[gong@Gong-Computer data_struct]$ g++ -g testblance.cpp -o testblance
[gong@Gong-Computer data_struct]$ ./testblance
Input a string to test the balance :
This(is)[a]{te}<st>.
string is
Input a expression:
3*3-(5-2+3*6)*(7-3*1)
After the convertion:
33*52-36*+731*-*-
The result of expression:
-75

从上面的测试结果基本上实现符号平衡测试、表达式的求值问题，但是当前的表达式只能计算0-9为操作数的四则运算，复杂的多位数还不能进行测试。

 

以上的三个例子是栈的经典运用，对栈的特性先入后出有更深层次的理解才能更好的运用。

 

在函数调用中，如果不保存调用程序的状态，在被调用程序中就会修改程序的状态，这时候也就不能还原到之前的状态，只有将当前的状态保存起来，压入栈中，当被调用程序执行完成以后，将当前程序栈中的内容弹出就能实现任务状态的还原，当前函数执行完成以后，调用该函数的状态也需要还原。这时候就实现了先调用的函数最后执行，所以说函数调用是典型的先入后出问题。这也说明为什么栈如此的重要。