验证括号
给定一个字符串，如果括号的出现顺序是(),()(),或者（（））,我们认为括号是有效的。如果出现顺序是))，或者)(，或者))((，则认为是无效的。现在需要写一个函数，判断给定的字符串是否有效。
分析
- 1 括号必须成对出现，每一个")"之前必然有一个"("，这样才能保证括号是有效的。
- 2 可以考虑使用Stack方式处理，循环括号字符串，每遇到一个"(",就入栈一个")"，当遇到")"时，就pop出一个元素，如果pop出来的元素与当前不同，那么就是false.
- 3 如果最终stack不是空的，那么就是false。
代码一
bool validParentheses(String braces) {
StackString stack = new StackString(braces.length);
for(int i = 0; i< braces.length;i++){
if(braces[i] == "("){
stack.push(")");
}else if( stack.isEmpty() || stack.pop() != braces[i] ) {
//print(stack.stackArray);
//print("top is: "+ stack.top.toString());
return false;
}
}
return stack.isEmpty();
}
class StackString {
int maxSize;
List<String> stackArray;
int top;
StackString(int s) {
maxSize = s;
stackArray = new List<String>(s);
top = -1;
}
void push(String j) {
stackArray[++top] = j;
print("top is: "+ top.toString());
}
String pop() {
return stackArray[top--];
}
String peek() {
return stackArray[top];
}
bool isEmpty() {
return (top == -1);
}
bool isFull() {
return (top == maxSize - 1);
}
}
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
41
42
43
44
45
46
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
41
42
43
44
45
46
代码2
同样的思路，使用一个变量来记录。当遇到"("就自增1，当遇到")"就自减1，最终变量为0。如果不为0，说明是无效的括号串。
bool validParentheses(String braces) {
int stack = 0;
for (int i = 0; i < braces.length; i++) {
String current = braces[i];
if (current != ')' && current != '(') {
continue;
}
if (current == '(') {
stack++;
}
else {
if (stack == 0) {
return false;
}
stack--;
}
}
return stack == 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19