栈在括号匹配中的应用

小半 • 2023年1月22日下午6:23 • 技术随笔 • 阅读 242

括号匹配问题：

在书写代码的过程中，括号必须是成对出现，必须是相匹配的，不仅体现在其数量上的相匹配，还要注意类型上也必须是相匹配的。

举例：

缺少一边括号：

类型不匹配：

正确匹配：

括号匹配利用栈的特性：

算法演示：

匹配成功：

右括号匹配失败：

左括号全部入栈：
扫描到右括号，左括号开始出栈：

右括号匹配失败：

左括号入栈：
左括号出栈：

因此代码书写完之后，还需要检查栈是否非空，如果是，则证明还有匹配失败的左括号。

算法实现：

完整代码如下所示：

#include<stdio.h>
#define MaxSize 10
typedef struct 
{    // 定义顺序栈
    int data[MaxSize];  // 静态数组存放栈中元素
    int top;    // 栈顶指针：指向目前栈顶元素的位置
} SeqStack;
void InitStack(SeqStack& S)//栈的初始化
{
    S.top = -1;
}
bool StackEmpty(SeqStack S) //判断栈是否是空栈
{
    if (S.top == -1) 
    {
        return true;
    }
    else 
    {
        return false;
    }
}
bool Push(SeqStack& S, char x) //元素进栈
{
    if (S.top == MaxSize - 1)
    {
        return false;
    }
    S.top = S.top + 1;
    S.data[S.top] = x;
    return true;
}
bool Pop(SeqStack& S, char& x) //出栈操作
{
    if (S.top == -1)
    {
        return false;
    }
    x = S.data[S.top];
    S.top = S.top - 1;
    return true;
}
bool bracketCheck(char str[], int length)//算法实现---括号匹配
{
    SeqStack S;
    InitStack(S);
    for (int i = 0; i < length; i++) //扫描栈中的所有括号
    {
        // 如果字符是左括号，则压入栈中
        if (str[i] == '(' || str[i] == '[' || str[i] == '{') 
        {
            Push(S, str[i]);
        }
        else
        {
            if (StackEmpty(S)) // 如果不是左括号，且栈为空则表示匹配失败
            {
                return false;
            }
            // 创建临时变量，用于存储栈中所弹出的字符--左括号
            char topElem;
            // 弹出栈顶元素
            Pop(S, topElem);
            // 如果括号类型不匹配，则视为匹配失败
            if (str[i] == ')' && topElem != '(') 
            {
                return false;
            }
            if (str[i] == ']' && topElem != '[')
            {
                return false;
            }
            if (str[i] == '}' && topElem != '{') 
            {
                return false;
            }
        }
    }
    return StackEmpty(S);
}

int main()
{
    char a[] = "[([][])]";
    if (bracketCheck(a, 8))
    {
        printf("匹配成功！");
    }
     else
        printf("匹配失败！");
}