## 1. 概念介绍
栈（Stack）又名堆栈，它是一种重要的数据结构。从数据结构角度看，栈也是线性表，其特殊性在于栈的基本操作是线性表操作的子集，它是操作受限的线性表，因此，可称为限定性的数据结构。限定它仅在表尾进行插入或删除操作。表尾称为栈顶，相应地，表头称为栈底。栈的基本操作除了在栈顶进行插入和删除外，还有栈的初始化，判空以及取栈顶元素等。
![](https://raw.githubusercontent.com/xidoublestar/image/master/pictures/栈.gif)
## 2. 题目描述

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true
示例 2:

输入: "()[]{}"
输出: true
示例 3:

输入: "(]"
输出: false
示例 4:

输入: "([)]"
输出: false
示例 5:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses

## 3. 解题思路
```shell
/*
解题思路：
解法一、栈
1、遍历字符串
2、当为左符号时压栈
3、当为右符合时出栈与当前字符对比，如果不相等则返回false
4、结束遍历时，如果栈不为空，则返回false，否则返回true
*/

```

## 4. 测试结果

解法一、栈
![](https://raw.githubusercontent.com/xidoublestar/image/master/pictures/20200529154447.png)
## 5. 栈
```c
/*
title: leetcode20. 有效的括号
author: xidoublestar
method: 栈
type: C
date: 2020-5-29
*/
bool isValid(char* s) {
	if (!strlen(s))
		return true;
	int s_len = strlen(s);
	char* mid = (char*)malloc(s_len);
	int top = 0;
	for (int i = 0; i < s_len; i++)
	{
		if (s[i] == '(' || s[i] == '[' || s[i] == '{')
			mid[top++] = s[i];
		else if (s[i] == ')' && (!top || mid[--top] != '('))
			return false;
		else if (s[i] == ']' && (!top || mid[--top] != '['))
			return false;
		else if (s[i] == '}' && (!top || mid[--top] != '{'))
			return false;
	}
	free(mid);
	return top ? false : true;
}

```

## 6. 复杂度分析
解法一、栈
时间复杂度：O(n)
空间复杂度：O(n)

ITPub博客

leetcode20. 有效的括号

最新文章