栈及栈运用之括号匹配

栈的定义及存储
只能在固定一端进行插入和删除操作的线性结构。进行插入删除操作的一端称为栈顶，另一端称为栈底，插入数据的操作称为压栈，删除数据的操作称为出栈。
栈的储存结构有顺序栈和链链两种。
顺序栈和顺序表基本一样，不同的是顺序栈只能固定在栈顶进行操作。顺序栈除了单个栈外还有共享栈，所谓共享栈就是两个栈共用一快储存空间，当然共享栈一般用于两个栈空间需求相反的情况下，比如一个增加一个减少，这就可以用共享栈了。
链栈可用单链表实现，一般将链表的头作为栈顶，链表的尾部作为栈底，这种情况下采用首插和首删法将比尾插和尾删更高效，因此在链栈中采用首插和首删法进行进栈和出栈的操作。
那么这两种储存方式哪种好一些呢？就进行时间复杂度比较而言两种方式都差不多，然而我们知道链表在内存中储存是碎片化的，所以比较浪费空间，因此就空间存储上顺序栈要优越一点。因此我们在这里实现一个顺序栈，并用实现的顺序栈做一个实例—–括号匹配。
顺序栈的实现
栈的基本操作有入栈、出栈、判空、取栈顶元素、计算栈内元素个数。下面我们用C++语言来实现：

template<typename T>
class Stack
{
public:
    Stack()
        :_array(NULL)
        ,_size(0)
        , _capacity(0)
    {}
    ~Stack()
    {
        if (_array)
        {
            delete[] _array;
        }
    }
    void Push(const T& data)
    {
        CheckCapacity();
        _array[_size++] = data;
    }
    void Pop()
    {
        if (!Empty())
        {
            _size--;
        }
    }
    T& Top()
    {
        assert(_size != 0);
        return _array[_size-1];
    }
    T& Top()const
    {
        assert(_size != 0)
        return _array[_size-1];
    }
    size_t Size()const
    {
        return _size;
    }
    bool Empty()const
    {
        return !_size;
    }
private:
    void CheckCapacity()
    {
        if (_size == _capacity)
        {
            _capacity = _capacity * 2 + 3;
            T *ptemp = new T[_capacity];
            if (_size)
            {
                for (size_t i = 0; i < _size; i++)
                {
                    ptemp[i] = _array[i];
                }
                delete[] _array;
            }
            _array = ptemp;
        }
    }

    T* _array;
    size_t _capacity;
    size_t _size;
};

这里写了一个模板类，当用某个类型来对这个模板进行实例化后就可以对这个栈进行压栈和出栈操作了。下面我们来用用这个栈——括号匹配。
栈的简单运用之括号匹配
这里的括号以C++程序中常用的三种括号()、[]、{}为例，我们要用程序来判断一段字符串的括号匹配是否正确。
括号通常有四种情况：
（1）、左括号多了。
（2）、右括号多了。
（3）、括号顺序错了。
（4）、括号匹配正确。
下面给出实现代码：

bool MatchBrackets(char* pStr)
{
    assert(pStr != NULL);
    Stack<char> stack_char;
    size_t len = strlen(pStr);
    for (size_t i = 0; i < len; i++)
    {
        if (pStr[i] != '(' && pStr[i] != ')'&&
            pStr[i] != '[' && pStr[i] != ']'&&
            pStr[i] != '{' && pStr[i] != '}')
            continue;
        if (pStr[i] == '(' || pStr[i] == '[' || pStr[i] == '{')
        {
            stack_char.Push(pStr[i]);
        }
        else
        {
            if (stack_char.Empty())
            {
                cout << "右括号多了" << endl;
                return false;
            }
            char ch = stack_char.Top();
            if (ch == '(' && pStr[i] == ')' ||
                ch == '['&&pStr[i] == ']' ||
                ch == '{'&&pStr[i] == '}')
            {
                stack_char.Pop();
            }
            else
                return false;
        }
    }
    if (!stack_char.Empty())
    {
        cout << "左括号多了" << endl;
        return false;
    }
    return true;
}

当括号匹配成功时就返回true，否则返回false，我们来看看测试：
先给出左括号多的例子：
void test1()
{
char str[] = “abc{cd(dfsfs[fksd]}”;
if (MatchBrackets(str))
cout << “匹配正确”;
}

再给出右括号多的情况：

void test2()
{
    char str[] = "abc{cd(dfs)fs[fksd]}}";
    if (MatchBrackets(str))
        cout << "匹配正确";
}

匹配错误：

void test2()
{
    char str[] = "abc{cd(dfs)f)s[fksd]}";
    if (MatchBrackets(str))
        cout << "匹配正确";
    else
        cout << "匹配错误";
}

正确匹配：

void test2()
{
    char str[] = "abc{cd(dfs)fs[fksd]}";
    if (MatchBrackets(str))
        cout << "匹配正确";
    else
        cout << "匹配错误";
}

以上就是栈的描述及栈的简单运用—括号匹配，在后面的文章会运用栈来进行更深一点的运用。欢迎各位勘误。