区块链技术博客
www.b2bchain.cn

标题: 大佬们,帮我看看这个程序哪里有问题,可以运行,结果不是想要的

D0b2wT.gif

b2bchain.cn区块链技术社区提供第9191篇技术文章标题: 大佬们,帮我看看这个程序哪里有问题,可以运行,结果不是想要的
问题解答:

大佬们,帮我看看这个程序哪里有问题,可以运行,结果不是想要的

一个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");
        }
    }

}

标题: 大佬们,帮我看看这个程序哪里有问题,可以运行,结果不是想要的 由www.b2bchain.cn 提供
文章整理自网络,只为个人学习与分享使用
链接地址https://www.b2bchain.cn/?p=9191

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 标题: 大佬们,帮我看看这个程序哪里有问题,可以运行,结果不是想要的
分享到: 更多 (0)
D0b2wT.gif

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们