# 题目

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

有效字符串需满足：

示例 1:

示例 2:

示例 3:

示例 4:

示例 5:

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

# 分析

这种对称性的题目很符合栈的特点

遍历字符 s，碰到左符号，就往栈里 push 对应的右符号，碰到右符号，且于栈顶元素相同，则栈 pop，否则返回 false，如果遍历完了栈不为空同样返回 false。只有当遍历完栈为空才返回 true。

	// 时间复杂度: O (n)
	// 空间复杂度: O (n)
	class Solution {
	public:
	bool isValid(string s) {
	if (s.size() % 2 != 0) return false; // 如果 s 的长度为奇数，一定不符合要求
	stack<char> st;
	for (int i = 0; i < s.size(); i++) {
	if (s[i] == '(') st.push(')');
	else if (s[i] == '{') st.push('}');
	else if (s[i] == '[') st.push(']');
	// 第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号 return false
	// 第二种情况：遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。所以 return false
	else if (st.empty() \|\| st.top() != s[i]) return false;
	else st.pop(); //st.top () 与 s [i] 相等，栈弹出元素
	}
	// 第一种情况：此时我们已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以 return false，否则就 return true
	return st.empty();
	}
	};

堆栈