forked from lgaBug/algorithm014-algorithm014
-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathvaildParentheses20.java
More file actions
93 lines (89 loc) · 2.29 KB
/
Copy pathvaildParentheses20.java
File metadata and controls
93 lines (89 loc) · 2.29 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
package Week_01;
import java.util.Arrays;
import java.util.HashMap;
public class vaildParentheses20 {
public static void main(String[] args) {
Solution20 s = new Solution20();
String test = "((";
System.out.println(s.isValid(test));
}
}
class Solution20 {
HashMap<Character, Character> t;
{
t = new HashMap<>();
t.put(')', '(');
t.put(']', '[');
t.put('}', '{');
}
public boolean isValid(String s) {
if (s.length() % 2 != 0) {
return false;
}
stack20 stack = new stack20();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if ( t.containsKey(ch) ) {
char pair = t.get(ch);
if (stack.isEmpty()) {
System.out.println("stack empty");
return false;
}
char p = stack.pop();
if (p != pair) {
System.out.println("pop is not same with pair (" + p + ") (" + pair + ")");
return false;
}
} else {
stack.push(ch);
}
}
return stack.isEmpty();
}
}
class stack20 {
char[] stack;
int length;
int size;
public stack20() {
this(10);
}
public stack20(int length) {
this.length = length;
this.stack = new char[length];
this.size = 0;
}
public boolean isEmpty() {
if (this.size == 0) {
return true;
}
return false;
}
public void full() {
if (this.size < this.length) {
return;
}
int incer = 5;
char[] newStack = new char[this.length + incer];
System.arraycopy(this.stack, 0, newStack, 0, length);
this.stack = newStack;
this.length += incer;
}
public void push(char x) {
this.full();
this.stack[this.size] = x;
this.size++;
}
public char pop() {
if (this.isEmpty()) {
throw new RuntimeException("stack empty");
}
char x = this.stack[size-1];
this.stack[size-1] = 0;
this.size--;
return x;
}
public void print() {
System.out.println(Arrays.toString(this.stack));
}
}