大佬们,帮我看看这个程序哪里有问题,可以运行,结果不是想要的
一个DFA识别字符串的代码,我不论输入什么字符串,都给我输出no,和预期的结果不一致,各位大佬们帮我看看。/*Node.java*/
package
//状态节点类
class Node {
private String name;//状态节点的名字
public Node() {
}
//有参构造函数
public Node(String name) {//有参构造函数
this.name = name;
}
//获取状态名字
public String getName() {//获取状态名字
return this.name;
}
//设置状态名字
public void setName(String name) {//设置状态名字
this.name = name;
}
}
/*DFA.java*/
package
import java.util.ArrayList;
import java.util.Scanner;
//DFA类
class DFA {
//结点个数
static int maxNodeNum = 1000;
//五元组
private ArrayList<Node> stateNodes;//状态节点的的集合(ArrayList集合列表形式)
private ArrayList<Character> alphabet;// 字母表(字符集合)
private int[][] graph;//转换表(有向图)
private ArrayList<Node> finalNodes;//终结节点的集合
private Node initNode;//开始节点
//状态表节点个数,字母表字符集合
private int nodeNum;
private int alphabetNum;
public DFA() {//构造函数,初始化DFA实例对象
maxNodeNum = 1000;
this.stateNodes = new ArrayList<Node>();
this.alphabet = new ArrayList<Character>();
this.graph = new int[maxNodeNum][256];
this.initNode = new Node();
this.finalNodes = new ArrayList<Node>();
this.init();
this.run();
}
public static void main(String[] args) {
DFA myDfa = new DFA();
myDfa.init();
myDfa.run();
}
//得到状态q在该状态集合中的下标位置
int getNodeIndex(Node q) {
String qName = q.getName();
for (int i = 0; i < stateNodes.size(); i++) {//遍历一遍节点状态集合stateNodes
Node curNode = stateNodes.get(i);//名字相同就是同一节点
if (curNode.getName() == qName) {//找到就返回q在终点状态集合stateNodes的下标编号
return i;
}
}
return -1;//找不到就返回-1,表示没有这个节点
}
//得到字母表c在字母表集合的下标位置
int getCharIndex(Character c) {
for (int i = 0; i < alphabet.size(); i++) {
Character curCharacter = alphabet.get(i);
if (curCharacter == c) {
return i;
}
}
return -1;
}
//判断状态节点是不是终结状态,如果在finalState终点节点中找到就是终结状态
Boolean findFinalState(Node q) {
for (int i = 0; i < finalNodes.size(); i++) {
if (finalNodes.get(i).getName() == q.getName())
return true;
}
return false;
}
//init()函数初始化自动机,将五元组存储在实例对象的5个属性中
public void init() {
//假如自动机M:({q0,q1,q2},{0},转换函数,q0,{q2})
Node q0 = new Node("q0");
Node q1 = new Node("q1");
Node q2 = new Node("q2");
Node q3 = new Node("q3");
stateNodes.add(q0);
stateNodes.add(q1);
stateNodes.add(q2);
stateNodes.add(q3);
//字母表包含一个输入字符'0'
alphabet.add('a');
alphabet.add('b');
//开始状态initNode 是q0
initNode = q0;
//终止状态有一个q3
finalNodes.add(q3);
//更新状态节点数,字母表中的字母个数
nodeNum = 4;
alphabetNum = 2;
//初始化转换表
this.graphInit();
//将转换函数存入graph表,graph[q1编号][字符编号]=q2编号
graph[0]['a'] = 1;//(q0,'a') -> q1
graph[0]['b'] = 2;
graph[1]['a'] = 3;
graph[1]['b'] = 2;
graph[2]['a'] = 1;
graph[2]['b'] = 3;
graph[3]['a'] = 3;
graph[3]['b'] = 3;
}
//初始化转换表,二维表graph[节点p编号][字符c编号] = -1表示节点p经过字符c会到达陷进状态
public void graphInit() {
for (int i = 0; i < nodeNum; i++) {
for (int j = 0; j < alphabetNum; j++) {
graph[i][j] = -1;
}
}
}
//dfs()递归
public boolean dfs(Node currentNode, String sentence) {
//递归出口
//递归出口1:符号串长度为0时,到达递归出口,此时判断是否到达终结点
if (sentence.length() == 0 || sentence == null) {
//findFinalState判断是否到达终点
if (findFinalState(currentNode))//是终结点就代表是一个合法的句子
return true;
return false;
}
Character firstCharacter = sentence.charAt(0);//取出剩下句子的第一个字符
int charIndex = getCharIndex(firstCharacter);//取得字符在字符表中的下标编号
int nodeIndex = getNodeIndex(currentNode);//取得节点在状态表中的下标编号
if (charIndex == -1) return false;//递归出口2:遇到非法字符就错误
if (nodeIndex == -1) return false;//递归出口3:到达陷阱状态(状态表里没有-1)
int nextNodeIndex = graph[nodeIndex][charIndex];//得到由currentNode状态字符到达的新状态节点
if (nextNodeIndex == -1) return false;//状态表中没有的状态就是陷阱状态
return dfs(stateNodes.get(nextNodeIndex), sentence.substring(1));
/*
* stateNodes.get(nextNodeIndex)递归下一个参数(下一个节点Node)
* sentence.substring(1)截取当前句子的第一个字符剩下的字符串
* */
}
//run()启动函数
public void run() {
Scanner scanner = new Scanner(System.in);
System.out.println("输入需要识别的符号串:");
String sentence = scanner.nextLine();//scanner输入类读入一行字符串作为输入的符号串
if (dfs(this.initNode, sentence)) {
System.out.println("Yes");//dfs递归判断是否识别成功
} else {
System.out.println("No");
}
}
}