java实现正则表达式到NFA的转换-白红宇

java实现正则表达式到NFA的转换

阅读量：6916 次

发布时间：2019-06-27

本文共 12781 字，大约阅读时间需要 42 分钟。

我用java实现了一个正则表达式到NFA的转换程序,以下是我的代码

package com.siwanghu.regextoNFA;public class Node {    private int id;    private static int ID=0;        public Node(){    	this.id=ID++;    }	public int getId() {		return id;	}		public static void reset(){		ID=0;	}	@Override	public String toString() {		return id+"";	}    }

package com.siwanghu.regextoNFA;public class Edge {	private Node begin;	private Node end;	private String label;	private Edge edge;		public Edge() {		super();	}	public Edge(Node begin, Node end) {		super();		this.begin = begin;		this.end = end;	}	public Edge(Node begin, Node end, String label) {		super();		this.begin = begin;		this.end = end;		this.label = label;	}	public String getLabel() {		return label;	}	public void setLabel(String label) {		this.label = label;	}	public Edge getEdge() {		return edge;	}	public void setEdge(Edge edge) {		this.edge = edge;	}		public Node getBegin() {		return begin;	}	public void setBegin(Node begin) {		this.begin = begin;	}	public Node getEnd() {		return end;	}	public void setEnd(Node end) {		this.end = end;	}	@Override	public String toString() {		return "Edge [begin=" + begin + ", end=" + end + ", label=" + label				+ "]";	}	}package com.siwanghu.regextoNFA;import java.util.ArrayList;import java.util.List;public class Graph {	private List
     
       edges;	private Node start;	private Node end;	public Graph() {		edges = new ArrayList
      
       ();	}	public List
       
         getEdges() {		return edges;	}	public Node getStart() {		return start;	}	public void setStart(Node start) {		this.start = start;	}	public Node getEnd() {		return end;	}	public void setEnd(Node end) {		this.end = end;	}	public void reset() {		Node.reset();	}	public void Star(Object obj) {		if (obj.getClass().getName().equals(Graph.class.getName())) {			addStar((Graph) obj);			return;		}		if (obj.getClass().getName().equals(Character.class.getName())) {			addStar((Character) obj);			return;		} else {			throw new RuntimeException("You have an error in your Regex syntax");		}	}	public void Union(Object obj1, Object obj2) {		if (obj1.getClass().getName().equals(Character.class.getName())) {			if (obj2.getClass().getName().equals(Graph.class.getName())) {				addUnion((Character) obj1, (Graph) obj2);				return;			}			if (obj2.getClass().getName().equals(Character.class.getName())) {				addUnion((Character) obj1, (Character) obj2);				return;			}		}		if (obj1.getClass().getName().equals(Graph.class.getName())) {			if (obj2.getClass().getName().equals(Graph.class.getName())) {				addUnion((Graph) obj1, (Graph) obj2);				return;			}			if (obj2.getClass().getName().equals(Character.class.getName())) {				addUnion((Graph) obj1, (Character) obj2);				return;			}		} else {			throw new RuntimeException("You have an error in your Regex syntax");		}	}	public void Concat(Object obj1, Object obj2) {		if (obj1.getClass().getName().equals(Character.class.getName())) {			if (obj2.getClass().getName().equals(Graph.class.getName())) {				addConcat((Character) obj1, (Graph) obj2);				return;			}			if (obj2.getClass().getName().equals(Character.class.getName())) {				addConcat((Character) obj1, (Character) obj2);				return;			}		}		if (obj1.getClass().getName().equals(Graph.class.getName())) {			if (obj2.getClass().getName().equals(Graph.class.getName())) {				addConcat((Graph) obj1, (Graph) obj2);				return;			}			if (obj2.getClass().getName().equals(Character.class.getName())) {				addConcat((Graph) obj1, (Character) obj2);				return;			}		} else {			throw new RuntimeException("You have an error in your Regex syntax");		}	}	public void addStar(Graph graph) {		Node begNode = new Node();		Node endNode = new Node();		Edge edge1 = new Edge(endNode, begNode, "epsilon");		Edge edge2 = new Edge(begNode, graph.getStart(), "epsilon");		Edge edge3 = new Edge(graph.getEnd(), endNode, "epsilon");		for (int i = 0; i < graph.getEdges().size(); i++) {			this.edges.add(graph.getEdges().get(i));		}		this.edges.add(edge1);		this.edges.add(edge2);		this.edges.add(edge3);		this.start = begNode;		this.end = endNode;	}	public void addStar(Character character) {		Node nodeCenter = new Node();		Node nodebeg = new Node();		Node nodeend = new Node();		Edge edgeLink = new Edge(nodeCenter, nodeCenter, character.toString());		Edge edgeEpsilonBeg = new Edge(nodebeg, nodeCenter, "epsilon");		Edge edgeepsilonEnd = new Edge(nodeCenter, nodeend, "epsilon");		this.edges.add(edgeLink);		this.edges.add(edgeEpsilonBeg);		this.edges.add(edgeepsilonEnd);		this.start = nodebeg;		this.end = nodeend;	}	public void addUnion(Character character, Graph graph) {		Node begNode = new Node();		Node endNode = new Node();		Edge edge1 = new Edge(begNode, graph.getStart(), "epsilon");		Edge edge2 = new Edge(graph.getEnd(), endNode, "epsilon");		Edge edge3 = new Edge(begNode, endNode, character.toString());		for (int i = 0; i < graph.getEdges().size(); i++) {			this.edges.add(graph.getEdges().get(i));		}		this.edges.add(edge1);		this.edges.add(edge2);		this.edges.add(edge3);		this.start = begNode;		this.end = endNode;	}	public void addUnion(Graph graph, Character character) {		Node begNode = new Node();		Node endNode = new Node();		Edge edge1 = new Edge(begNode, graph.getStart(), "epsilon");		Edge edge2 = new Edge(graph.getEnd(), endNode, "epsilon");		Edge edge3 = new Edge(begNode, endNode, character.toString());		for (int i = 0; i < graph.getEdges().size(); i++) {			this.edges.add(graph.getEdges().get(i));		}		this.edges.add(edge1);		this.edges.add(edge2);		this.edges.add(edge3);		this.start = begNode;		this.end = endNode;	}	public void addUnion(Graph graph1, Graph graph2) {		Node begNode = new Node();		Node endNode = new Node();		Edge edge1 = new Edge(begNode, graph1.getStart(), "epsilon");		Edge edge2 = new Edge(begNode, graph2.getStart(), "epsilon");		Edge edge3 = new Edge(graph1.getEnd(), endNode, "epsilon");		Edge edge4 = new Edge(graph2.getEnd(), endNode, "epsilon");		this.start = begNode;		this.end = endNode;		for (int i = 0; i < graph1.getEdges().size(); i++) {			this.edges.add(graph1.getEdges().get(i));		}		for (int i = 0; i < graph2.getEdges().size(); i++) {			this.edges.add(graph2.getEdges().get(i));		}		this.edges.add(edge1);		this.edges.add(edge2);		this.edges.add(edge3);		this.edges.add(edge4);	}	public void addUnion(Character characterOne, Character characterTwo) {		Node nodebeg = new Node();		Node nodeend = new Node();		Edge edgeOne = new Edge(nodebeg, nodeend, characterOne.toString());		Edge edgeTwo = new Edge(nodebeg, nodeend, characterTwo.toString());		edges.add(edgeOne);		edges.add(edgeTwo);		start = nodebeg;		end = nodeend;	}	public void addConcat(Character character, Graph graph) {		Node begNode = new Node();		Edge edge = new Edge(begNode, graph.getStart(), character.toString());		for (int i = 0; i < graph.getEdges().size(); i++) {			this.edges.add(graph.getEdges().get(i));		}		this.edges.add(edge);		this.start = begNode;		this.end = graph.getEnd();	}	public void addConcat(Graph graph, Character character) {		Node endNode = new Node();		Edge edge = new Edge(graph.getEnd(), endNode, character.toString());		for (int i = 0; i < graph.getEdges().size(); i++) {			this.edges.add(graph.getEdges().get(i));		}		this.edges.add(edge);		this.start = graph.getStart();		this.end = endNode;	}	public void addConcat(Graph graph1, Graph graph2) {		Edge edge = new Edge(graph1.getEnd(), graph2.getStart(), "epsilon");		this.start = graph1.getStart();		this.end = graph2.getEnd();		for (int i = 0; i < graph1.getEdges().size(); i++) {			this.edges.add(graph1.getEdges().get(i));		}		for (int i = 0; i < graph2.getEdges().size(); i++) {			this.edges.add(graph2.getEdges().get(i));		}		this.edges.add(edge);	}	public void addConcat(Character characterOne, Character characterTwo) {		Node begNode = new Node();		Node midNode = new Node();		Node endNode = new Node();		Edge edge1 = new Edge(begNode, midNode, characterOne.toString());		Edge edge2 = new Edge(midNode, endNode, characterTwo.toString());		this.start = begNode;		this.end = endNode;		this.edges.add(edge1);		this.edges.add(edge2);	}	@Override	public String toString() {		String printString = "Start=" + this.start + "  End=" + this.end + "\n";		for (int i = 0; i < edges.size(); i++) {			printString += edges.get(i) + "\n";		}		return printString;	}}

package com.siwanghu.regextoNFA;import java.util.Stack;public class Regex {	private String regex = "";	private Stack operatorStack;	private Stack operandStack;	private int[][] priority = {			{ 1, 1, 1, -1, 1, 1 }, // *&|()#			{ -1, 1, 1, -1, 1, 1 }, { -1, -1, 1, -1, 1, 1 },			{ -1, -1, -1, -1, 0, 2 }, { 1, 1, 1, 1, 1, 1 },			{ -1, -1, -1, -1, -1, -1 } };	public Regex() {		regex = "";		operatorStack = new Stack();		operandStack = new Stack();	}	public Regex(String _regex) {		regex = "";		operatorStack = new Stack();		operandStack = new Stack();		prepareString(_regex);	}	public Graph transformNFA() {		if (regex.length() == 0)			return null;		else {			int i = 0;			operatorStack.push('#');			char[] _regex = (regex + "#").toCharArray();			while (_regex[i] != '#'					|| (Character) (operatorStack.peek()) != '#') {				if (!isOperator(_regex[i])) {					operandStack.push((Character)_regex[i]);					i++;				} else {					int value=priorityOperator((Character)(operatorStack.peek()), _regex[i]);					switch (value) {					case 1:						Character character=(Character)operatorStack.pop();						switch (character) {						case '*':							Object obj=operandStack.pop();							Graph graph1=new Graph();							graph1.Star(obj);							operandStack.push(graph1);							break;						case '&':							Object obj2=operandStack.pop();							Object obj1=operandStack.pop();							Graph graph2=new Graph();							graph2.Concat(obj1, obj2);							operandStack.push(graph2);							break;						case '|':							Object obj4=operandStack.pop();							Object obj3=operandStack.pop();							Graph graph3=new Graph();							graph3.Union(obj3, obj4);							operandStack.push(graph3);							break;						default:							break;						}						break;					case 0:						operatorStack.pop();						i++;						break;					case -1:						operatorStack.push(_regex[i]);						i++;						break;					default:						break;					}				}			}			return (Graph) operandStack.pop();		}	}		public void reset(){		Node.reset();		operandStack.clear();		operatorStack.clear();	}	public String getRegex() {		return regex;	}	public void setRegex(String _regex) {		prepareString(_regex);	}	private boolean isOperator(Character character) {		String operatorString = "*&|()#";		if (operatorString.contains(character.toString())) {			return true;		} else {			return false;		}	}	private int priorityOperator(Character character1, Character character2) {		String priorityString = "*&|()#";		return this.priority[priorityString.indexOf(character1.toString())][priorityString				.indexOf(character2.toString())];	}	private void prepareString(String _regex) {		char[] regexs = _regex.replaceAll(" ", "").toCharArray();		for (int i = 0; i < regexs.length; i++) {			if (i == 0)				regex += regexs[i];			else {				if (regexs[i] == '|' || regexs[i] == '*' || regexs[i] == ')') {					regex += regexs[i];				} else {					if (regexs[i - 1] == '(' || regexs[i - 1] == '|')						regex += regexs[i];					else						regex += ("&" + regexs[i]);				}			}		}	}}

package com.siwanghu.regextoNFA;public class Test {	public static void main(String[] args) {		try {			String regexString1 = "a*";			Regex regex1 = new Regex(regexString1);			System.out.println(regex1.getRegex());			System.out.println(regex1.transformNFA());			regex1.reset();						String regexString2 = "ab";			Regex regex2 = new Regex(regexString2);			System.out.println(regex2.getRegex());			System.out.println(regex2.transformNFA());			regex2.reset();						String regexString3 = "a|b";			Regex regex3 = new Regex(regexString3);			System.out.println(regex3.getRegex());			System.out.println(regex3.transformNFA());			regex3.reset();						String regexString4 = "(a|b)*";			Regex regex4 = new Regex(regexString4);			System.out.println(regex4.getRegex());			System.out.println(regex4.transformNFA());			regex4.reset();						String regexString5 = "1(0|1)*101";			Regex regex5 = new Regex(regexString5);			System.out.println(regex5.getRegex());			System.out.println(regex5.transformNFA());			regex5.reset();						String regexString6 = "0*10*10*10*";			Regex regex6 = new Regex(regexString6);			System.out.println(regex6.getRegex());			System.out.println(regex6.transformNFA());			regex6.reset();						String regexString7 = "1(1010*|1(010)*1)*0";			Regex regex7 = new Regex(regexString7);			System.out.println(regex7.getRegex());			System.out.println(regex7.transformNFA());			regex6.reset();					} catch (Exception e) {			System.out.println(e.getMessage());		}	}}

转载于:https://blog.51cto.com/siwanghu/1705664

你可能感兴趣的文章