-
Notifications
You must be signed in to change notification settings - Fork 0
/
Test.java
155 lines (144 loc) · 4.04 KB
/
Test.java
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
package stack;
interface Stack <T>{
void stackPush(T obj);//入栈
void stackPop();//出栈
int size();//栈元素数量
T stackTop();//取栈顶
void printStak();//辅助函数,打印栈中元素
}
class StackImp <T> implements Stack <T>{
//栈中要有啥?1.元素数量(头节点),里面放栈头和尾巴
//栈的每个节点放元素和下一个节点的位置
private int size;
private Node first;
private Node last;
//建一个内部类,实例化节点
private class Node {//只能此内部访问,private修饰,增强安全性
private T item;
private Node next;
private Node(T item ,Node next) {//
this.item = item;
this.next = next;
}
}
@Override
public void stackPush(T obj) {
Node tmp = this.first;
Node newNode = new Node(obj, null);
this.last = newNode;
if (null == this.first) {//首次时
this.first = newNode;
}else {
while (null != tmp.next) {
tmp = tmp.next;
}
tmp.next = newNode;
}
++ this.size;
}
@Override
public void stackPop() {
Node tmp = this.first;
if (null == tmp.next) {
this.first =null;
this.last = null;
this.size = 0;
return ;
}
while (null !=tmp.next.next) {
tmp = tmp.next;
}
this.last = tmp;
tmp.next = null;
--this.size;
}
@Override
public int size() {
return this.size;
}
@Override
public T stackTop() {
return (T) this.last.item;//不是返回return this.last啊
}
@Override
public void printStak() {
Node tmp = this.first;
if (null == this.first) {
return;
}
while (null != tmp.next) {
System.out.print(tmp.item + "->");
tmp = tmp.next;
}
System.out.println(tmp.item);
}
// @Override
// public void stackPush(T obj) {
// // TODO Auto-generated method stub
//
// }
}
class Factory{
public static Stack<Character> getStack() {
return new StackImp<Character>();
}
}
public class Test {
public static void main(String[] args) {
// Stack<Character> stack = Factory.getStack();//工厂产生栈对象
Stack<Character> stack = new StackImp<Character>();//自己产生栈对象
String str = "(())hello Jan{{}}";
bracket(stack, str);
//括号匹配:左边括号入栈,右边括号,取栈,是一对,pop,不是,return wrong
//肯能会用到 字符串 转字符数组 char [] strarr = str.toCharArray();
//++++++++++栈检测++++++++++
// System.out.println(stack.size());
// stack.stackPush1("1");
// stack.stackPush1("2");
// stack.stackPush1("3");
// stack.stackPush1("4");
// stack.stackPush1("5");
// stack.stackPop();
// System.out.println(stack.size());
// stack.printStak();
}
public static void bracket (Stack<Character> stack,String str) {
if (null == str) {
return ;
}
char [] strarr = new char [str.length()];//这里的length()区别于数组中的length,前是方法,后是数组变量
strarr = str.toCharArray();//直接就放进去了
int i = 0;//大小写转换 CTRL+ shift x/y
while (i < strarr.length) {
//先判断是不是括号,是左括号,入栈
if ('(' == strarr[i] || '[' == strarr[i] || '{' == strarr [i]) {
stack.stackPush(strarr[i]);
++ i;//前置效率高,不产生临时变量
continue;//入栈后面就不用再走了
}
if (')' == strarr[i] || ']' == strarr[i] || '}' == strarr [i]) {//是右边括号
if(stack.size() == 0) {//栈空了,还来右边括号,那右边括号多
System.out.println("右括号多");
++ i;
return;
}
char c = stack.stackTop();//.toString().charAt(0) ;//曲线救国,对象转字符串再转字符
if ((c == '(' && ')'== strarr[i]) || ( c == '[' && ']' == strarr[i]) || ( c == '{' && '}' == strarr[i])){
stack.stackPop();//栈中的括号与当前匹配
++ i;
continue;
}else {//此时栈中与当前括号不匹配//[}
System.out.println("括号不匹配");
++ i;
return;
}
}
++ i;
}
if(stack.size() != 0) {//循环结束,要么完全匹配(栈空),要么左边括号多(栈不空),
System.out.println("左括号多");
return;
}
System.out.println("匹配 =.=");
}
}