有效的括号

题目

LeetCode 题号20 有效的括号

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

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

提示:
1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成

示例1:

输入:s = "()"
输出:true

示例 2:

输入:s = "()[]{}"
输出:true

示例 3:

输入:s = "(]"
输出:false

示例 4:

输入:s = "([)]"
输出:false

示例 5:

输入:s = "{[]}"
输出:true

解题思路

使用栈

当接触题目,我们会想到如果计算出左括号的数量和右括号的数量
如果每种括号左右数量相同,会不会就是有效的括号

示例4 每种括号的左右数量分别相等,但不是有效的括号
这是因为结果还与括号的位置有关。


仔细分析 发现符合题意的括号 它的部分子表达式仍然是有效的括号
并且每次删除一个有效的括号对 会逐渐把括号对删完!

这个思考的过程其实就是栈的实现过程。
因此我们考虑使用栈,当遇到匹配的最小括号对时,我们将这对括号从栈中删除(即出栈),
如果最后栈为空,那么它是有效的括号,反之不是

偷来的图mad有防盗链 点击查看吧
https://pic.leetcode-cn.com/baa8829ac398e665eb645dca29eadd631e2b337e05022aa5a678e091471a4913-20.gif
偷来的图嘿嘿嘿

官方题解

我们遍历给定的字符串 ss。当我们遇到一个左括号时,我们会期望在后续的遍历中,有一个相同类型的右括号将其闭合。
由于后遇到的左括号要先闭合,因此我们可以将这个左括号放入栈顶。

当我们遇到一个右括号时,我们需要将一个相同类型的左括号闭合。此时,我们可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型,或者栈中并没有左括号,那么字符串 ss 无效,返回 False。为了快速判断括号的类型,我们可以使用哈希表存储每一种括号。哈希表的键为右括号,值为相同类型的左括号。

在遍历结束后,如果栈中没有左括号,说明我们将字符串 ss 中的所有左括号闭合,返回 True,否则返回 False。
注意到有效字符串的长度一定为偶数,因此如果字符串的长度为奇数,我们可以直接返回 False,省去后续的遍历判断过程。

代码实现

注释写的贼详细

:

  • 这里把自己的code搬了上来 懒得再敲一边Stack了
  • 只看isValid 就行了
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

typedef char ElemType;
typedef struct Stack
{
	ElemType* a;
	int top; // 栈顶位置
	int capacity; // 容量
}Stack;

void StackInit(Stack* ps);
void StackDestroy(Stack* ps);
void StackPush(Stack* ps, ElemType x);
void StackPop(Stack* ps);
ElemType StackTop(Stack* ps);
int StackSize(Stack* ps);
bool StackEmpty(Stack* ps);

void StackInit(Stack* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	// 初始化时 top赋  0  ---> 意味着top指向 栈顶数据 的下一个
	//                top赋 -1 ---> 意味着top指向 栈顶数据 
	ps->capacity = 0;
}


void StackDestroy(Stack* ps)  // 即便pop完 也要销毁 因为数据虽然删除 但是空间还在
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}


void StackPush(Stack* ps, ElemType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newcapacaiy = ps->capacity == 0 ? 4 : ps->capacity * 2;
		ElemType* tmp = realloc(ps->a, sizeof(ElemType) * newcapacaiy);
		if (tmp == NULL)
		{
			printf("realloc failed;\n");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacaiy;
	}
	ps->a[ps->top] = x;
	ps->top++;

}


void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}


ElemType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}

int StackSize(Stack* ps);



bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}

bool isValid(char * s)
{
    // 看字符串的len 如果为奇数就直接返回false即可
    int n = strlen(s);
    if( n%2 == 1)
    {
        return false;
    }
    // 实例化一个栈
    Stack st;
    StackInit(&st);
    // 循环条件原因 : 字符串 '/0'结尾 对应ascll码为 null
    while(*s)
    {
        if(
            *s == '('
            || *s == '['
            || *s == '{'
        ) // 如果 *s 为左括号则入栈 ++s 向后走
        {
            StackPush(&st, *s);
            ++s;
        }
        else // 如果不为左括号
        {
            if(StackEmpty(&st)) // 判断Stack内是否为空 也就是没左括号 没有直接false即可
            {
                StackDestroy(&st);
                return false;
            }
            // Stack不为空 弹出栈顶元素  也就是最后进的左括号 
            ElemType top = StackTop(&st);
            StackPop(&st);
            // 反证法 把错误的情况的写完 剩下的就是正确的
            if(
                (*s == ')' && top != '(')
                ||(*s == '}' && top != '{')
                ||(*s == ']' && top != '[')
            )
            {
                StackDestroy(&st);
                return false;
            }
            // 此时top = *s 
            else  // 剩下三种情况 1. (*s=')' && top='(')  ~~~  继续走即可
            {
                ++s;
            }
        }
    }
    // 遍历完s 判断Stack内是否为空 返回一个bool类型
    // 1. 不为空 说明 Stack内有剩余 即存在左括号 直接返回false
    // 2. 为空 说明 Stack内无剩余
    bool ret = StackEmpty(&st);
    StackDestroy(&st);
    return ret;
}

先写这一种吧 刚学完栈的练习题

栈学习 Code地址