本文共 1125 字，大约阅读时间需要 3 分钟。

题目描述

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

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

示例：

输入: “()” 输出: true

输入: “()[]{}”

输出: true

输入: “([)]”

输出: false

输入: “{[]}”

输出: true

解题思路

首先，因为括号是成对出现的，所以，字符串的长度必须是2的倍数，如果不是直接return false。

其次，如果字符串为空，直接return true。 使用栈这种数据结构进行实现是比较方便的。

bool EffectiveBrackets(string s){	if(s.empty())		return true;	if(s.length()%2!=0)		return false;	stack
   
     st;	for(int i=0;i
   

结果:

分析: 1.先判断字符串是否为空，若为空，则直接返回true。 2.判断字符串是否是2的倍数，如果不是，则返回false。 3.遍历字符串，如果字符为’(’，则在栈顶增加’)’，如果字符为’{’，则在栈顶增加’}’，如果字符为’[’，则在栈顶增加’]’。 4.如果栈顶为空，或者栈顶元素不是我们匹配的元素，则返回false。 5.遍历完成，出栈。

演示b过程

()[]{} 当i=0时，s[0]=’(’，入栈’)’ 当i=1时，s[1]=’)’，st.top()=’)’，不为空且st.top()=s[1]，出栈 当i=2时，s[2]=’[’，入栈’]’ 当i=3时，s[3]=’]’，st.top()=’]’，不为空且st.top()=s[3]，出栈 当i=4时，s[4]=’{’，入栈’}’ 当i=5时，s[5]=’}’，st.top()=’}’，不为空且st.top()=s[5]，出栈，结束。

演示c过程

([)] 当i=0时，s[0]=’(’，入栈’)’ 当i=1时，s[1]=’[’，入栈’]’ 当i=2时，s[2]=’)’，st.top()=’]’，不为空但st.top()!=s[2]，return false

演示d过程

{[]} 当i=0时，s[0]=’{’，入栈’}’ 当i=1时，s[1]=’[’，入栈’]’ 当i=2时，s[2]=’]’，st.top()=’]’，不为空且st.top()=s[2]，st.pop()，出栈。 当i=3时，s[3]=’}’，st.top()=’}’，不为空且st.top()=s[3]，st.pop()，出栈，结束。

转载地址：http://kiuy.baihongyu.com/