来源Leetcode第20题有效的括号
给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。
有效字符串需满足：左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。示例 1:
输入: “()”
输出: true
栈
这题一看到就知道和表达式匹配里的括号规则一样是要考虑括号的顺序的，方法是用栈来实现，但是由于玩了会魂3(但其实什么也没玩到，灰心哥下次我必在火鸡场杀了你)，导致偷懒直接标记括号数量来匹配，完全忽略了另一个要求正确的顺序，导致AC不了。
正确的顺序这样只能够通过栈来实现了。
代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41public boolean isValid(String s) {
// 空字符串
if (s.length() == 0)
return true;
// 排除奇数长度(位运算)
if ((s.length() & 1) == 1)
return false;
// 栈元素个数
int index = 0;
// 栈
char[] stack = new char[s.length()];
for (int i = 0; i < s.length(); i++) {
switch (s.charAt(i)) {
case '(':
case '[':
case '{':
// 进栈
stack[index++] = s.charAt(i);
continue;
case ')':
if (index == 0 || stack[--index] != '(')
return false;
// stack[--index] == '(' ，才会contniue
// --index：相当于满足的元素出栈
continue;
case ']':
if (index == 0 || stack[--index] != '[')
return false;
continue;
case '}':
if (index == 0 || stack[--index] != '{')
return false;
continue;
}
}
return index == 0; // 判断栈是否为空
}
C语言版本：1
2
3
4
5
6
7
8
9
10
11
12
13
14bool isValid(char * s){
if (s == NULL || s[0] == '\0') return true;
char stack[10240]; int top =0;
for (int i = 0; s[i]; ++i) {
if (s[i] == '(' || s[i] == '[' || s[i] == '{') stack[top++] = s[i];
else {
if ((--top) < 0) return false;//先减减，让top指向栈顶元素
if (s[i] == ')' && stack[top] != '(') return false;
if (s[i] == ']' && stack[top] != '[') return false;
if (s[i] == '}' && stack[top] != '{') return false;
}
}
return (top ? false : true);//防止“【”这种类似情况
}