LeetCode刷题——括号匹配问题

x33g5p2x  于9个月前 转载在 其他  
字(1.9k)|赞(0)|评价(0)|浏览(85)

前言:这次介绍一道用C语言刷题很难受的一题,主要用到“栈”的思想。

1.括号匹配问题

OJ链接

给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

思路分析:

由于栈结构的特殊性,非常适合做对称匹配类的题目。

首先要弄清楚,字符串里的括号不匹配有几种情况。

先来分析一下 这里有三种不匹配的情况:


  1. 第一种情况,字符串里左方向的括号多余了 ,所以不匹配。

  2. 第二种情况,括号没有多余,但是 括号的类型没有匹配上。

  3. 第三种情况,字符串里右方向的括号多余了,所以不匹配。

我们的代码只要覆盖了这三种不匹配的情况,就不会出问题。

题解:

借助上次博客实现的栈实现此题。在栈中存放左括号,遇到右括号,则出栈顶元素,判断栈顶元素是否和当前括号匹配,如果不匹配,则说明不匹配。遍历完所有字符,如果栈为空,则表示完全匹配。

//上次博客中栈的定义
typedef char STDatatype;
typedef struct Stack
{
    STDatatype* a;
    int top;        // 栈顶
    int capacity;
}ST;
 
 
void StackInit(ST* ps);
void StackDestroy(ST* ps);
void StackPush(ST* ps, STDatatype x);
void StackPop(ST* ps);
bool StackEmpty(ST* ps);
int StackSize(ST* ps);
STDatatype StackTop(ST* ps);
 
 
void StackInit(ST* ps)
{
    assert(ps);
    ps->a = NULL;
    ps->top = 0; // -1
    ps->capacity = 0;
}
 
 
void StackDestroy(ST* ps)
{
    assert(ps);
    if (ps->a)
    {
        free(ps->a);
    }
    ps->a = NULL;
    ps->top = 0; 
    ps->capacity = 0;
}
 
 
void StackPush(ST* ps, STDatatype x)
{
    assert(ps);
 
 
    // 检查空间够不够,不够就增容
    if (ps->top == ps->capacity)
    {
        int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        STDatatype* tmp = realloc(ps->a, sizeof(STDatatype)*newcapacity);
        if (tmp == NULL)
        {
            printf("rellaoc fail\n");
            exit(-1);
        }
        ps->a = tmp;
        ps->capacity = newcapacity;
    }
 
 
    ps->a[ps->top] = x;
    ps->top++;
}
 
 
void StackPop(ST* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));
 
 
    --ps->top;
}
 
 
bool StackEmpty(ST* ps)
{
    assert(ps);
 
 
    return ps->top == 0;
}
 
 
int StackSize(ST* ps)
{
    assert(ps);
 
 
    return ps->top;
}
 
 
STDatatype StackTop(ST* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));
 
 
    return ps->a[ps->top - 1];
}



//正文开始
bool isValid(char * s){
    ST st;
    StackInit(&st);
    bool match=true;
    while(*s)
    {
        if(*s=='('||*s=='{'||*s=='[')
        {
            StackPush(&st,*s);
            ++s;
        }
        else
        {
            if(StackEmpty(&st))
            {
                match = false;
                break;
            }
 
 
            char ch = StackTop(&st);
            StackPop(&st);
            if((*s == ']' && ch != '[')
            || (*s == '}' && ch != '{')
            || (*s == ')' && ch != '('))
            {
                match = false;
                break;
            }
            else
            {
                ++s;
            }
        }
    }
 
 
    if(match == true)
    {
        match = StackEmpty(&st);
    }
 
    StackDestroy(&st);
    return match;
}

嗯,你没有看错,这道题用C语言实现需要手动写一个栈,正文部分其实很少,等后边C++学到STL标准库可以省力很多!

相关文章