栈与队列OJ题思路共享括号匹配（C语言实现）

2024-03-07 03:07:35 阅读 0

不久前，我们向大家介绍了两种新的结构：栈和队列。有一些关于栈和队列的非常经典的OJ问题。这里我一共给大家分享三个问题，即1。括号匹配问题：问题20 - 2.使用队列实现堆栈：问题225 - 3.使用堆栈实现队列：问题232.今天的章节，我们将分享第一个问题：括号匹配问题

如果你还没有自己实现过栈和队列，请跳转到栈和队列的详细解释。这里的问题要求你使用你已经实现的结构！

2. 括号匹配问题 2.1 问题回顾

我们先看一下问题：

首先，这里需要注意的是，括号仅由三对'('、'['、'{'组成，一些复杂形式如：[({})]也是有效的括号。这道题出现在我们的栈和队列题中，所以我不在乎，这道题是一道非常经典的栈结构相关题，因为栈特殊的先进先出结构，所以我们可以想到, *当字符串中给出左括号时（无论三个括号中哪一个是左括号），就会被压入栈中，然后，如果遇到右括号（无论是哪一个括号），就会被压入栈中。三个括号就是右括号），就会从栈中弹出来匹配，看看左右两边能不能匹配。*我们画个图来理解：

现在我们有了基本的想法，我们就可以开始了。

2.2 代码实现 2.21 导入堆栈

我们已经明白这道题可以用栈来回答，但是这道题并没有给我们提供栈的结构，所以我们需要将之前写好的栈导入到我们的题中：具体请看下面的视频手术：

如何导入自己的堆栈

2.22 代码实现

我们实现栈的时候，并没有在初始化函数中定义结构体，而是在test.c文件中初始化了该结构体。所以第一步是定义问题中的结构并初始化它：

bool isValid(char * s)
{
    ST st;//定义一个结构体st(ST是我们自己命名的)
    StackInit(&st);//初始化结构体
}

接下来我们先实现遇到左括号时的情况：

bool isValid(char * s)
{
    ST st;
    StackInit(&st);
    int i=0;
    while(s[i]!='\0')
    {
        if(s[i]=='('||s[i]=='['||s[i]=='{')//遇见左括号就入栈
        {
            StackPush(&st,s[i]);//这是我们自己实现的入栈函数
            i++;
        }
}

考虑完左括号后，下一步是右括号：

else//遇见右括号了,出栈
        {
            STDataType top=StackTop(&st);//取出栈顶元素
            StackPop(&st);//然后再将栈顶元素删除,使得栈顶的下一个元素到栈顶位置
            if((s[i]==')'&&top!='(')||(s[i]==']'&&top!='[')||(s[i]=='}'&&top!='{'))
            {
                StackDestroy(&st);//每一次使用完栈结构都需要销毁
                  return false;//如果不匹配就返回假
            }
            else
            {
                i++;//如果匹配就接着往后走
            }
        }

。这里需要注意的是，我们在写if条件语句时，写的是不匹配的情况，而不是匹配的情况。不匹配的情况下直接返回false，程序结束。这样写比较简单。

合并所有代码：

bool isValid(char * s)
{
    ST st;
    StackInit(&st);
    int i=0;
    while(s[i]!='\0')
    {
        if(s[i]=='('||s[i]=='['||s[i]=='{')
        {
            StackPush(&st,s[i]);
            i++;
        }
        else//遇见右括号了,但是栈里面可能没有数据,说明前面没有左括号
        {
            STDataType top=StackTop(&st);
            StackPop(&st);
            if((s[i]==')'&&top!='(')||(s[i]==']'&&top!='[')||(s[i]=='}'&&top!='{'))
            {
                StackDestroy(&st);
                  return false;
            }
            else
            {
                i++;
            }
        }
    }
    return true;//如果整个过程都没有返回false,那么最后就返回true;
}

2.3 代码优化 2.31 修改第一步

当我们提交代码时，我们发现一个错误：

这里我们的代码只通过了五个用例。* 我们可以看到，当字符串只有一个左括号时，我们根本没有进入我们的 else 语句。这相当于我们将左括号压入堆栈后程序结束。所以直接返回 false.* 并且值得注意的是，这里如果有多个字符，如果有五个左括号而没有右括号，也会报错，所以我们修改代码：

bool isValid(char * s)
{
    ST st;
    StackInit(&st);
    int i=0;
    while(s[i]!='\0')
    {
        if(s[i]=='('||s[i]=='['||s[i]=='{')
        {
            StackPush(&st,s[i]);
            i++;
        }
        else
        {
            STDataType top=StackTop(&st);
            StackPop(&st);
            if((s[i]==')'&&top!='(')||(s[i]==']'&&top!='[')||(s[i]=='}'&&top!='{'))
            {
                StackDestroy(&st);
                  return false;
            }
            else
            {
                i++;
            }
        }
    }
    bool ret=StackEmpty(&st);//当栈里不为空时,证明还有左括号与右括号没有匹配
    StackDestroy(&st);
    return ret;
}

这里我们在完成所有程序后判断堆栈是否为空。如果不为空，说明还有括号没有匹配到。我们的 ret 等于 false 并返回 false。如果堆栈为空，则返回 true。

2.32 修改第二步

当我们修改第一步后提交代码时，会遇到另一个问题：

我们可以发现这里报的错误和我们之前实现栈时写的断言有关。它说 ps->top 失败。结合下面的用例：“]”，我们可以推断，当遇到右括号时，我们需要执行取栈顶数据的操作，但是没有左括号压入栈，即栈为空，取不到数据（如果不断言，可能会出现乱码），那么到这里我们就离成功又近了一步。也就是说，在执行else语句之前，我们需要判断栈是否为空。如果为空，则直接返回false。

而栈为空的情况有以下几种情况：

我们最终修改后的代码：

bool isValid(char * s)
{
    ST st;
    StackInit(&st);
    int i=0;
    while(s[i]!='\0')
    {
        if(s[i]=='('||s[i]=='['||s[i]=='{')
        {
            StackPush(&st,s[i]);
            i++;
        }
        else//遇见右括号了,但是栈里面可能没有数据,说明前面没有左括号
        {
            if(StackEmpty(&st))//如果栈为空就返回false
            {
                return false;
            }
            STDataType top=StackTop(&st);
            StackPop(&st);
            if((s[i]==')'&&top!='(')||(s[i]==']'&&top!='[')||(s[i]=='}'&&top!='{'))
            {
                  return false;
            }
            else
            {
                i++;
            }
        }
    }
    bool ret=StackEmpty(&st);//栈为空证明左右括号已经匹配完了
    StackDestroy(&st);
    return ret;
}