1

我想将 State 对象（它们是以 Character 作为键，State 作为 Value 的 HashMaps 放入名为 allStates 的 ArrayList 中。我应该在这里覆盖 equals 和 hashCode 方法吗？为什么？如何？

此代码适用于我迄今为止构建的 Automaton 和 State 类：

class State extends HashMap<Character, State>{

boolean isFinal;
boolean isInitial;
int stateId;

State () {
    isInitial=false;
    isFinal = false;
    }

public boolean equals (Object o){
    boolean isEqual = false;
    State compare = (State)o;

    if ((compare.stateId)==this.stateId)
    {
        return true;
    }
    return isEqual;
}

public int hashCode() {
    int theHashCode = stateId%7;

    return theHashCode;
}


}

  class Automaton{
     List <State> allStates;
    //private List<State> finalStates;
     int  theInitialStateIntIndex;
     State actualState;
      char [] alphabet;

    Automaton() {
        allStates = new ArrayList<State>();
    }

    public void setAllStates (int numberOfStates)  {
        for (int i =0; i <numberOfStates; i++) {
            State newState = new State();
            newState.stateId = i;
            allStates.add(newState);
         }
    }


    public void setAlphabet (String alphabetLine){
        alphabet = alphabetLine.toCharArray();
    }

    public void markFinalStates (String [] finalStates){
        for (int index =0; index<finalStates.length; index++) {
            int aFinalStateId = Integer.parseInt(finalStates[index]);

            State aFinalState = allStates.get(aFinalStateId);
            aFinalState.isFinal = true;
            allStates.add(aFinalStateId, aFinalState);

            /*DEBUG*/
            aFinalState = allStates.get(aFinalStateId);
            if ((aFinalState.isFinal)==true)
            System.out.println("THE STATE " + aFinalStateId + " IS MARKED AS FINAL");
        }
    }

    public void markInitialState (int initialStateId) {
            State theInitialState = allStates.get(initialStateId);
            theInitialState.isInitial=true;
            allStates.add(initialStateId, theInitialState);

            theInitialStateIntIndex = initialStateId;

            /*DEBUG*/

            System.out.println("THE INITIAL STATE ID IS " + initialStateId);

            theInitialState = allStates.get(initialStateId);
            if ((theInitialState.isInitial)==true)
            System.out.println("THE STATE " + initialStateId + " IS MARKED AS INITIAL");
    }


    public void setTransitions(int stateId, String transitionsLine){
            State theOneToChange = allStates.get(stateId);

            String [] statesToReachStringSplitted = transitionsLine.split(" ");

            for (int symbolIndex=0; symbolIndex<statesToReachStringSplitted.length;symbolIndex++){
                int reachedState= Integer.parseInt(statesToReachStringSplitted[symbolIndex]);
                theOneToChange.put(alphabet[symbolIndex],allStates.get(reachedState));

                System.out.println("THE STATE " + stateId + " REACHES THE STATE " + reachedState + " WITH THE SYMBOL " + alphabet[symbolIndex]);
            }

            allStates.add(stateId, theOneToChange);
    }


    public int findInitialState(){
        int index =0;

       cycle: for (; index<allStates.size(); index++){
            State s = allStates.get(index);

            if (s.isInitial==true) {
                break cycle;
           }
        } return index;
}

    public void processString (String string)
    {
        StringBuilder stepString= new StringBuilder (string);

        int actualStateIntIndex;
        System.out.println("THE FOUND INITIAL ONE IS "+ theInitialStateIntIndex);
        State firstState = allStates.get(theInitialStateIntIndex);
        actualState = firstState;

        while (stepString.length()>0){
           Character characterToProcess = stepString.charAt(0);
           stepString.deleteCharAt(0);

           State nextState;
           nextState = ((State)actualState.get(characterToProcess)); // pasa al siguiente State
           actualState = nextState;

           actualStateIntIndex=allStates.indexOf(actualState);

           System.out.println("the actual state for " + stepString + " is " + actualStateIntIndex);
           if ((actualState.isFinal==true) && (stepString.length()==0))
              {
                  System.out.println("THE STRING " + string + " IS ACCEPTED AT STATE " + actualStateIntIndex );
              }
           else if (stepString.length()==0 && (actualState.isFinal==false)){
                  System.out.println("THE STRING " + string + " IS REJECTED AT STATE " + actualStateIntIndex);
              }

           }
       }
    }
4

1 回答 1

0

  1. 如果自动机是 DFA，则可以使用访问字符串来标识该字段。
    访问字符串是可用于从开始状态到达状态的任何字符串。在构建 DFA 时必须构建字符串，但是，它不会增加更多的时间复杂度。（是的，然后需要哈希码/等于字符串）

  2. 或者实际上，通过增加序列号/字符串来识别状态应该适用于所有自动机。然后根据 ID hashcode/equal。

去第二个，比第一个更容易，效果更好，除非你想处理重复的状态。

是的，您需要哈希码和等于用户定义的类型才能使用哈希。

于 2009-12-09T18:38:00.710 回答