欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

栈---实现顺序栈及简单的括号匹配问题

程序员文章站 2024-01-24 23:28:34
...


通常情况下,(Stack)可定义为只允许在表的末端进行插入和删除的线性表。允许插入和删除的一端称作栈顶(top),不允许插入和删除的一端称作栈底(bottom)。当栈中没有任何元素时则成为空栈。
栈---实现顺序栈及简单的括号匹配问题

栈的分类


栈的抽象数据类型有两种典型的存储方式:

  • 顺序栈:基于数组的存储表示
  • 链式栈:基于链表的存储表达方式

代码实现

//顺序栈的实现
#include<stdlib.h>
#include<iostream>
#include<assert.h>

using namespace std;
const int stackIncreament = 20;//扩容大小

template<class T>
class Stack
{
public:
    //构造函数
    Stack(int sz = 50)
    {
        top = -1;
        maxSize = sz;
        elements = new T[maxSize];
        assert(elements != NULL);
    }
    ~Stack()                       //析构函数
    {
        delete[]elements;
    }
    void push(const T& x);          //压栈操作
    bool pop(T& x);                 //出栈操作
    bool getTop(T& x)               //取栈顶元素
    {
        if (IsEmpty() == true)
            return false;
        x = elements[top];
        return true;
    }
    //判空
    bool IsEmpty()const
    {
        return (top == -1) ? true : false;
    }
    //判满
    bool IsFull()const
    {
        return (top == maxSize - 1) ? true : false;
    }
    //返回栈中元素个数
    int getSize()const
    {
        return top + 1;
    }
    //将栈置空
    void makeEmpty()
    {
        top = -1;
    }



private:
    T *elements;                //存放栈中元素的栈数组
    int top;                    //栈顶指针
    int maxSize;                //栈最大可容纳元素个数
    void overFloeProcess();     //栈的溢出处理
};

//私有函数,扩充栈的存储空间
template<class T>
void Stack<T>::overFloeProcess()
{
    T * newArray = new T[maxSize + stackIncreament];
    if (newArray == NULL)
    {
        cerr << "内存分配失败!" << endl;
        exit(1);
    }
    for (int i = 0; i <= top; i++)
    {
        newArray[i] = elements[i];
    }
    maxSize += stackIncreament;
    delete[]elements;
}

//压栈操作
template<class T>
void Stack<T>::push(const T& x)
{
    while (IsFull() == true){
        overFloeProcess();
    }
    elements[++top] = x;
}

//出栈操作
template<class T>
bool Stack<T>::pop(T& x)
{
    if (IsEmpty() == true)
        return false;
    x = elements[top--];//返回栈顶元素值
    return true;
}

//括号匹配
void PrintMatchedPairs(char * exprssion, int size)
{
    if (exprssion == NULL)
        return;
    Stack<int> s(size);
    int x;//pop返回的值
    int n;//栈中元素的个数
    for (int i = 1; i <= size; i++)
    {
        if (exprssion[i-1] == '(')
            s.push(i);
        else if (exprssion[i-1] == ')')
        {
            if (s.pop(x) == true)
                cout << x << " 与 " << i << "匹配" << endl;
            else
                cout << "没有与第" << i << "个右括号匹配的左括号!" << endl;
        }
    }
    while (s.IsEmpty() == false)
    {
        s.pop(x);
        cout << "没有与第" << x << "个右括号匹配的左括号!" << endl;
    }
}


int main()
{
    char * c = "(0)ii(ooio(o)))";
    cout << strlen(c) << endl;
    PrintMatchedPairs(c, strlen(c));
    return 0;
}

栈的灵活运用之括号配对

在一个字符串”(a * (b + c) - d)”中,位置1的左括号与位置8的右括号匹配,位置4的左括号和位置11的右括号匹配。
在字符串”(a + b)(“中,位置6的左括号没有右括号与之匹配。
利用栈的知识,我们就能轻松地找到已经匹配的左右括号和还未匹配的左右括号。
思路分析
循环遍历字符串,遇到’(‘将位置信息push,遇到’)’将栈顶的数据pop,由于栈的先进后出规则,pop操作得到的信息是与之匹配的左括号的位置。
首先遇到右括号,pop会返回false,接收false并进行处理。
字符串读完后栈不为空,依次出栈并显示信息,直到栈为空。

//括号匹配
void PrintMatchedPairs(char * exprssion, int size)
{
    if (exprssion == NULL)
        return;
    Stack<int> s(size);
    int x;//pop返回的值
    int n;//栈中元素的个数
    for (int i = 1; i <= size; i++)
    {
        if (exprssion[i-1] == '(')
            s.push(i);
        else if (exprssion[i-1] == ')')
        {
            if (s.pop(x) == true)
                cout << x << " 与 " << i << "匹配" << endl;
            else
                cout << "没有与第" << i << "个右括号匹配的左括号!" << endl;
        }
    }
    while (s.IsEmpty() == false)
    {
        s.pop(x);
        cout << "没有与第" << x << "个右括号匹配的左括号!" << endl;
    }
}