LeetCode：有效的括号

刺骨的言语ヽ痛彻心扉 2023-10-10 18:58 48阅读 0赞

### 题目链接：[20. 有效的括号 - 力扣（Leetcode）][20. _ - _Leetcode] ###

**还是老套路二话不说，先上代码：**

typedef char STDataType;
    typedef struct Stack
    {
    	STDataType* a;
    	int top;
    	int capacity;
    }ST;
    // 初始化栈
    void STInit(ST* pst);
    // 销毁栈
    void STDestroy(ST* pst);
    // 添加数据
    void STPush(ST* pst, STDataType x);
    // 删除数据
    void STPop(ST* pst);
    // 弹出数据
    STDataType STTop(ST* pst);
    // 判断是否为空
    bool STEmpty(ST* pst);
    // 判断大小
    int STSize(ST* pst);
    // 初始化栈
    void STInit(ST* pst)
    {
    	assert(pst);
    	pst->a = NULL;
    	pst->top = 0;
    	pst->capacity = 0;
    }
    // 销毁栈
    void STDestroy(ST* pst)
    {
    	assert(pst);
    	free(pst->a);
    	pst->a = NULL;
    	pst->top = 0;
    	pst->capacity = 0;
    }
    // 添加数据
    void STPush(ST* pst, STDataType x)
    {
    	if (pst->capacity == pst->top)
    	{
    		int newcapacity = (pst->capacity == 0 ? 4 : pst->capacity * 2);
    		STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));
    		if (tmp == NULL)
    		{
    			perror("realloc fail");
    			return;
    		}
    		pst->a = tmp;
    		pst->capacity = newcapacity;
    	}
    	pst->a[pst->top] = x;
    	pst->top++;
    }
    // 删除数据
    void STPop(ST* pst)
    {
    	assert(pst);
    	assert(!(STEmpty(pst)));
    	pst->top--;
    }
    // 弹出数据
    STDataType STTop(ST* pst)
    {
    	assert(pst);
    	assert(!(STEmpty(pst)));
    	return pst->a[pst->top - 1];
    }
    // 判断是否为空
    bool STEmpty(ST* pst)
    {
    	assert(pst);
    	return pst->top == 0;
    }
    // 判断大小
    int STSize(ST* pst)
    {
    	assert(pst);
    	return pst->top;
    }
    bool isValid(char* s) {
    	ST st;
    	STInit(&st);
    	while (*s)
    	{
    		// 左括号入栈
    		if (*s == '(' || *s == '{' || *s == '[')
    		{
    			STPush(&st, *s);
    		}
    		// 右括号出栈匹配
    		else
    		{
    			if (STEmpty(&st))
    			{
    				STDestroy(&st);
    				return false;
    			}
    			else
    			{
    				char tmp = STTop(&st);
    				STPop(&st);
    				if (*s == ']' && tmp != '[' || *s == ')' && tmp != '(' || *s == '}' && tmp != '{')
    				{
    					STDestroy(&st);
    					return false;
    				}
    			}
    		}
    		++s;
    	}
    	bool ret = STEmpty(&st);
    	STDestroy(&st);
    	return ret;
    }

![cb838c690a2344d1bc225b355cdcceb6.png][]

**过啦！！！！！！**

--------------------

## 题目思路： ##

>          该题比较简单，是对栈特性很好的应用，具体操作如下：
>          循环遍历String中的字符，逐个取到每个括号，如果该括号是：
>             1. 左括号，直接入栈
>             2. 右括号，与栈顶的左括号进行匹配，如果不匹配直接返回false
>                否则继续循环
>          循环结束后，如果栈空则匹配，否则左括号比右括号多肯定不匹配

我们需要注意的细节

**1.最后返回true时，栈必须为空，才能保证括号的匹配成功了的。  
2.第一个字符如果是右括号，那么肯定就不匹配了，直接返回false。**

[20. _ - _Leetcode]: https://leetcode.cn/problems/valid-parentheses/
[cb838c690a2344d1bc225b355cdcceb6.png]: https://img-blog.csdnimg.cn/cb838c690a2344d1bc225b355cdcceb6.png