当前位置：首页 > news >正文

数据结构——括号匹配问题

news 来源：原创 2024/11/15 23:23:20

这是一道常见的经典的数据结构中栈的问题。

题目：

20. 有效的括号 - 力扣（LeetCode）

我们运用C语言实现这个问题。

有效括号

调用栈

由于要涉及到栈的问题，不可避免的要运用栈的函数接口。比较直接的方法是，直接复制栈的代码，直接拿来用就行了。这里要注意，我们要把原来的“int”改成“char”。

//动态
typedef char STDataType;

typedef struct Stack
{
    //数据类型
    STDataType* a;
    //栈顶
    int top;
    //扩容
    int capacity;
}Stack;

//初始化
void StackInit(Stack* ps);
//释放空间
void StackDestory(Stack* ps);
//添加数据——入栈
void StackPush(Stack* ps, STDataType x);
//删除数据——出栈 
void StackPop(Stack* ps);
//取栈里的数据
STDataType StackTop(Stack* ps);
//数据个数
int StackSize(Stack* ps);
//判空
bool StackEmpty(Stack* ps); 

//初始化
void StackInit(Stack* ps)
{
    //判空
    assert(ps);
    //扩容
    ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
    //扩容失败
    if (ps->a == NULL)
    {
        perror("ps->a:");
        //终止
        exit(-1);
    }
    ps->capacity = 4;
    //插入数据top++
    ps->top = 0;
}

//释放空间
void StackDestory(Stack* ps)
{
    //判空
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->capacity = 0;
    ps->top = 0;
}

//添加数据
void StackPush(Stack* ps, STDataType x)
{
    //判空
    assert(ps);

    //判断是否要扩容
    if (ps->top == ps->capacity)
    {
        STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(ps->a) * 2 * (ps->capacity));
        if (tmp == NULL)
        {
            perror("realloc:");
            //终止
            exit(-1);
        }
        else
        {
            ps->a = tmp;
            ps->capacity *= 2;
        }
    }
    //加数据
    ps->a[ps->top] = x;
    //注意顺序
    ps->top++;
}

//删除数据
void StackPop(Stack* ps)
{
    //判空
    assert(ps);
    //不能为负数
    assert(ps->top > 0);

    ps->top--;
}


//取栈里的数据
STDataType StackTop(Stack* ps)
{
    //判空
    assert(ps);
    //不能为负数
    assert(ps->top > 0);
    
    return ps->a[ps->top - 1];
}

//数据个数
int StackSize(Stack* ps)
{
    //判空
    assert(ps);
    
    return ps->top;
}

//判空
bool StackEmpty(Stack* ps)
{
    //判空
    assert(ps);

    return ps->top == 0;
}

实现接口

其实这跟我们写的那些接口一样，第一步还是初始化

ST st;
StackInit(&st);

我们用学习C语言的时候的语法中的switch语句解决就行了。

这里一定要注意：我在这里找错误找了一个多小时，才找到，case选择时，一定要把左括号放在前面，右括号放在后面，因为题中的测试例子都是先左后右的。

首先while循环，为‘0’的时候就停下来。我们再来思考一下，左括号我们放数据，是不是直接调用Stackpush，然后s++，就行了。然后右括号提取之前我们应该先存放左括号的值，然后与左括号相比较，失败就直接返回false，成功就继续，s++，然后可能会遇到为空的情况，为空直接返回false。

结尾我们再判断是不是为0，0就是false，非0就是ture。

bool isValid(const char* s)
{
    //初始化
    Stack st;
    StackInit(&st);
    while (*s != '\0')
    {
        switch (*s)
        {
        case '(':
        case '{':
        case '[':
        {
            //添加数据
            StackPush(&st, *s);
            s++;
            break;
        }
        case ')':
        case '}':
        case ']':
        {
            //判空
            if (StackEmpty(&st))
            {
                StackDestory(&st);
                return false;
            }
            //存前一个的数据
            STDataType top = StackTop(&st);
            StackPop(&st);
            //匹配失败
            if ((*s == '(' && top != ')')
                || (*s == '[' && top != ']')
                || (*s == '{' && top != '}'))
            {
                StackDestory(&st);
                return false;
            }
            else
            {
                s++;
            }
            break;
     
        }
        }
    }
    bool ret = StackEmpty(&st);
    StackDestory(&st);
    return ret;
}

然后提交