Repository navigation
Expand file tree
/
Copy pathWellNestedOpenClose.java
More file actions
106 lines (97 loc) · 2.61 KB
/
Copy pathWellNestedOpenClose.java
File metadata and controls
106 lines (97 loc) · 2.61 KB
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
/*
https://leetcode.com/problems/valid-parentheses/
*/
import java.util.Deque;
import java.util.LinkedList;
public class WellNestedOpenClose {
public static char close(char c) {
switch (c) {
case '(':
return ')';
case '[':
return ']';
case '{':
return '}';
default:
throw new IllegalArgumentException(String.valueOf(c));
}
}
public static boolean isValid(String s) {
Deque<Character> stack = new LinkedList<>();
int l = s.length();
for (int i = 0; i < l; i++) {
char c = s.charAt(i);
switch (c) {
case '(':
case '[':
case '{':
stack.push(c);
break;
default:
if (stack.isEmpty() || c != close(stack.pop()))
return false;
break;
}
}
if (!stack.isEmpty())
return false;
return true;
}
/*
By using a magic value for characters that don't close,
we can reuse this on the main loop code.
Another saner but less efficient possibility would be to return character / boolean pair,
where the boolean indicates if the char can be closed.
*/
public static char closeMagic(char c) {
switch (c) {
case '(':
return ')';
case '[':
return ']';
case '{':
return '}';
}
return 0;
}
public static boolean isValidMagic(String s) {
Deque<Character> stack = new LinkedList<>();
int l = s.length();
for (int i = 0; i < l; i++) {
char c = s.charAt(i);
if (closeMagic(c) != 0) {
stack.push(c);
} else {
if (stack.isEmpty() || c != closeMagic(stack.pop()))
return false;
}
}
if (!stack.isEmpty())
return false;
return true;
}
public static void main(String[] args) {
String stringsPass[] = {
"",
"()",
"[]",
"{}",
"([])",
"[()]",
};
for (String s : stringsPass) {
assert isValid(s);
assert isValidMagic(s);
}
String stringsFail[] = {
"(",
")",
"(]",
"([)]",
};
for (String s : stringsFail) {
assert !isValid(s);
assert !isValidMagic(s);
}
}
}