Skip to content

Commit 476a7a4

Browse files
lazyKindManlazyKindMan
committed
第九次提交
正则识别 NFA构建完成
1 parent d0693bc commit 476a7a4

4 files changed

Lines changed: 105 additions & 25 deletions

File tree

‎Edgle.java‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -13,8 +13,8 @@ public Edgle()
1313
public Edgle(String ma,Node st,Node end)
1414
{
1515
mark=ma;
16-
startNode=(Node)st.Clone();
17-
endNode=(Node)end.Clone();
16+
startNode=st;
17+
endNode=end;
1818
}
1919
public void SetMark(String ma)
2020
{
@@ -26,8 +26,8 @@ public String GetMark()
2626
}
2727
public void setNode(Node st,Node end)//两个参数，getNodew为-1代表不对该参数进行设置
2828
{
29-
if(st.getNode()!=-1) startNode=(Node)st.Clone();
30-
if(end.getNode()!=-1) endNode=(Node)end.Clone();
29+
if(st.getNode()!=-1) startNode=st;
30+
if(end.getNode()!=-1) endNode=end;
3131
}
3232
public Node GetStartnode()
3333
{

‎Graph.java‎

Lines changed: 9 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -15,8 +15,8 @@ public Graph()
1515
public Graph(Node st,Node ed)//注意使用克隆让数据封装
1616
{
1717
map=new HashMap<Node,List<Edgle>>();//初始化map
18-
startNode=(Node)st.Clone();
19-
endNode=(Node)ed.Clone();
18+
startNode=st;
19+
endNode=ed;
2020
}
2121
public Node GetStartnode()
2222
{
@@ -52,10 +52,14 @@ public void AddEdgle(Edgle ed)
5252
map.put(nd, newEds);
5353
}
5454
}
55+
public Map<Node,List<Edgle>> getMap()
56+
{
57+
return map;
58+
}
5559
public void setNode(Node st,Node ed )//设置起始和结束节点
5660
{
57-
if(st.getNode()!=-1) startNode=(Node)st.Clone();
58-
if(ed.getNode()!=-1) endNode=(Node)ed.Clone();
61+
if(st.getNode()!=-1) startNode=st;
62+
if(ed.getNode()!=-1) endNode=ed;
5963
}
6064
public void TraverseGraph()//遍历图操作 就输出，不做深搜广搜
6165
{
@@ -69,5 +73,6 @@ public void TraverseGraph()//遍历图操作 就输出，不做深搜广搜
6973
}
7074
System.out.print("\n");
7175
}
76+
System.out.println(String.format("startNode:%d endNode:%d",startNode.getNode(),endNode.getNode()));
7277
}
7378
}

‎Node.java‎

Lines changed: 15 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -25,17 +25,19 @@ public static int getSum()//每次获取点都让点的数字加一
2525
return sumNum-1;
2626
}
2727
//Node对象的复制
28-
public Object Clone()
29-
{
30-
Object o=null;
31-
try
32-
{
33-
o=(Node)super.clone();
34-
}
35-
catch(CloneNotSupportedException e)
36-
{
37-
System.out.println(e.toString());
38-
}
39-
return o;
40-
}
28+
// public Object Clone()
29+
// {
30+
// Object o=null;
31+
// try
32+
// {
33+
// o=(Node)super.clone();
34+
// }
35+
// catch(CloneNotSupportedException e)
36+
// {
37+
// System.out.println(e.toString());
38+
// }
39+
// return o;
40+
// }
41+
//虽然不克隆会破坏封装性，但是鉴于一个点就是一个对象，克隆点虽然值是一样，但是所表示
42+
//的应当还是另外个点，所以取消克隆对象方法
4143
}

‎RegularExpRecognize.java‎

Lines changed: 77 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -105,6 +105,79 @@ private void GreateAddMap()//创建一个加号性质的图
105105
preGraph.AddEdgle(new Edgle("null",preGraph.GetEndnode(),preGraph.GetStartnode()));
106106
GStack.push(preGraph);//入栈
107107
}
108+
else ErrorRep();
109+
}
110+
private void GreateQueMap()//创建一个问号性质的图
111+
{
112+
if(!GStack.isEmpty())
113+
{
114+
Graph preGraph=GStack.pop();
115+
//增加一条直达边
116+
preGraph.AddEdgle(new Edgle("null",preGraph.GetStartnode(),preGraph.GetEndnode()));
117+
GStack.push(preGraph);//将新生成的栈入栈
118+
}
119+
}
120+
private void GreateAsteriskMap()//创建星号map 闭包增加两条边，起始到终点，终点到起始
121+
{
122+
if(!GStack.isEmpty())
123+
{
124+
Graph preGraph=GStack.pop();
125+
//增加一条直达边
126+
preGraph.AddEdgle(new Edgle("null",preGraph.GetStartnode(),preGraph.GetEndnode()));
127+
preGraph.AddEdgle(new Edgle("null",preGraph.GetEndnode(),preGraph.GetStartnode()));
128+
GStack.push(preGraph);//将新生成的栈入栈
129+
}
130+
else ErrorRep();
131+
}
132+
private void GreateAndMap()
133+
{
134+
if(!GStack.isEmpty())
135+
{
136+
Graph frontGraph=GStack.pop();
137+
if(!GStack.isEmpty())
138+
{
139+
Graph rearGraph=GStack.pop();
140+
//将后取的图的end节点与先取图的开始节点连接
141+
Graph newGraph=new Graph(rearGraph.GetStartnode(),frontGraph.GetEndnode());
142+
for(Node nd : rearGraph.getMap().keySet())
143+
for(int i=0;i<rearGraph.getMap().get(nd).size();i++)
144+
newGraph.AddEdgle(rearGraph.getMap().get(nd).get(i));
145+
for(Node nd : frontGraph.getMap().keySet())
146+
for(int i=0;i<frontGraph.getMap().get(nd).size();i++)
147+
newGraph.AddEdgle(frontGraph.getMap().get(nd).get(i));
148+
newGraph.AddEdgle(new Edgle("null",rearGraph.GetEndnode(),frontGraph.GetStartnode()));
149+
GStack.push(newGraph);
150+
}
151+
else ErrorRep();
152+
}
153+
else ErrorRep();
154+
}
155+
private void GreateOrMap()
156+
{
157+
if(!GStack.isEmpty())
158+
{
159+
Graph frontGraph=GStack.pop();
160+
if(!GStack.isEmpty())
161+
{
162+
Graph rearGraph=GStack.pop();
163+
//新建立一个起始点与一个结束点
164+
Graph newGraph=new Graph(new Node(Node.getSum()),new Node(Node.getSum()));
165+
//起始点将两个图的起始点连接
166+
newGraph.AddEdgle(new Edgle("null",newGraph.GetStartnode(),rearGraph.GetStartnode()));
167+
newGraph.AddEdgle(new Edgle("null",newGraph.GetStartnode(),frontGraph.GetStartnode()));
168+
for(Node nd : rearGraph.getMap().keySet())
169+
for(int i=0;i<rearGraph.getMap().get(nd).size();i++)
170+
newGraph.AddEdgle(rearGraph.getMap().get(nd).get(i));
171+
for(Node nd : frontGraph.getMap().keySet())
172+
for(int i=0;i<frontGraph.getMap().get(nd).size();i++)
173+
newGraph.AddEdgle(frontGraph.getMap().get(nd).get(i));
174+
newGraph.AddEdgle(new Edgle("null",rearGraph.GetEndnode(),newGraph.GetEndnode()));
175+
newGraph.AddEdgle(new Edgle("null",frontGraph.GetEndnode(),newGraph.GetEndnode()));
176+
GStack.push(newGraph);
177+
}
178+
else ErrorRep();
179+
}
180+
else ErrorRep();
108181
}
109182
public void RegularExtract()//正则表达式提取,图的创建
110183
{
@@ -134,10 +207,10 @@ public void RegularExtract()//正则表达式提取,图的创建
134207
switch(sub)
135208
{
136209
case "+":GreateAddMap();break;
137-
case "?":break;
138-
case "*":break;
139-
case "&":break;
140-
case "|":break;
210+
case "?":GreateQueMap();break;
211+
case "*":GreateAsteriskMap();break;
212+
case "&":GreateAndMap();break;
213+
case "|":GreateOrMap();break;
141214
default:ErrorRep();
142215
}
143216
}

0 commit comments

Comments
 (0)