الانتقال من الدولة إلى الدولة في هذا Automaton عبر Hashmap
https://stackoverflow.com/questions/1874991
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
أنا أستخدم هذه الطريقة للانتقال من حالة إلى أخرى على جهاز محاكاة Automaton هذا:
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);
}
}
}
هنا:
State nextState;
nextState = ((State)actualState.get(characterToProcess));
قد أفعل شيئا خاطئا، لكنني لا أحصل عليه.
يتعطل Automaton في الحالة 0 دائما، على الرغم من أن StringBuilder يتم معالجته بشكل صحيح، لماذا؟
إليك الرمز الكامل:
package afd;
import java.io.*;
import java.util.*;
/**
*
* @author Administrator
*/
public class Main {
/**
* @param args the command line arguments
*/
public static void main(String[] args) throws IOException {
// TODO code application logic here
FileReader fr = new FileReader("E://Documents and Settings//Administrator//My Documents//NetBeansProjects//AFD//src//afd//dfa.in");
BufferedReader br = new BufferedReader(fr);
String firstLine= br.readLine();
String [] firstLineSplitted = firstLine.split(" ");
/*debug*/
//System.out.println("firstLine is " + firstLine);
int numberOfTestCases = Integer.parseInt(firstLine);
for (int indexOfTestCases =0; indexOfTestCases < numberOfTestCases; indexOfTestCases++ ){
int aux;
System.out.println("Case Number " + (aux = indexOfTestCases+1));
String caseStartLine = br.readLine();
/*debug*/
//System.out.println("caseStarLine is " + caseStartLine);
String [] caseStartLineSplitted = caseStartLine.split(" ");
int numberOfStates;
int numberOfAlphabetSymbols;
int numberOfFinalStates;
numberOfStates = Integer.parseInt(caseStartLineSplitted[0]);
numberOfAlphabetSymbols = Integer.parseInt(caseStartLineSplitted[1]);
numberOfFinalStates = Integer.parseInt(caseStartLineSplitted[2]);
Automaton automaton = new Automaton();
automaton.setAllStates(numberOfStates);
// automaton.size = numberOfStates;
// automaton.numberOfAlphabetSymbols = numberOfAlphabetSymbols;
// automaton.numberOfFinalStates = numberOfFinalStates;
//Automaton a = new Automaton(numberOfStates);
String alphabetLine = br.readLine();
System.out.println("alphabetLine is " + alphabetLine);
automaton.setAlphabet (alphabetLine);
// automaton.alphabetSymbols =new StringBuffer(alphabetLine);
for (int indexOfStates = 0; indexOfStates < numberOfStates; indexOfStates++){
String transitionsLine = br.readLine();
/*debug*/
System.out.println("for the state " + indexOfStates + " transitionsLine is " + transitionsLine);
automaton.setTransitions(indexOfStates,transitionsLine);
/*String [] ijLineSplitted = ijLine.split(" ");
int i = Integer.parseInt(ijLineSplitted[0]);
int j = Integer.parseInt(ijLineSplitted[1]);
*/
}
String finalStatesLine = br.readLine();
/*debug*/
System.out.println("finalStatesLine is " + finalStatesLine);
String finalStatesLineSplitted [] = finalStatesLine.split(" ");
automaton.markFinalStates(finalStatesLineSplitted);
String initialStateAndNumberOfStringsLine = br.readLine();
/*debug*/
//System.out.println("initialStateAndNumberOfStringsLine is " +initialStateAndNumberOfStringsLine);
String [] splittedInitialStateLine = initialStateAndNumberOfStringsLine.split(" ");
int initialState = Integer.parseInt(splittedInitialStateLine[0]);
int numberOfStrings = Integer.parseInt(splittedInitialStateLine[1]);
automaton.markInitialState(initialState);
for (int stringIndex =0; stringIndex<numberOfStrings; stringIndex++){
String stringToProcess = br.readLine();
/*debug*/
System.out.println("stringToProcess is " + stringToProcess);
automaton.processString(stringToProcess);
}
}
}
}
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
3 2 1
ab
1 0
2 0
2 0
2
0 3
abaa
aab
aba
3 3 2
ade
0 1 2
1 2 0
2 1 0
1 2
2 2
a
de
3 2 1
ab
1 0
2 0
2 0
2
0 3
abaa
aab
aba
3 3 2
ade
0 1 2
1 2 0
2 1 0
1 2
2 2
a
de
تحرير: هنا سأشرح تنسيق ملف الإدخال هذا
يمثل السطر الأول عدد حالات الاختبار.
يبدأ كل حالة اختبار مع 3 أعداد صحيحة، الأول هو عدد الولاية ل Automaton، التالي هو عدد الرموز في الأبجدية، ثم عدد الدول النهائية.
السطر التالي هو الأبجدية. تظهر الرموز معا.
ثم هناك عدد من الخطوط المساواة لعدد الدول التي تصف وظيفة الانتقال. يمثل السطر الأول من هذه المجموعة من هذه المجموعة وظيفة الانتقال للدولة الأولى في Automaton (QO)، يمثل العنصر الأول الحالة التي تم التوصل إليها عندما يذهب الرمز الأول في الأبجدية إلى هذه الحالة، وما إلى ذلك. واجهت مشكلة في فهم هذا من بيان المشكلة الأصلية. هذه هي أسهل طريقة جئت لرؤيتها:
الخطوط:
1 0
2 0
2 0
مساو:
AlphabetSymbol0 AlphabetSymbol1
State0 State1 State0
State1 State2 State0
State2 State2 State0
ثم هناك خط يقول وهو الدول النهائية للسيارات.
ثم يأتي خطا يقول وهو الحالة الأولية وعدد سلاسل المدخلات سيأتي.
ثم تأتي الخطوط مع سلاسل المدخلات.
يجب أن يكون إخراج هذا البرنامج:
جيم
ase Number 1
alphabetLine is ab
for the state 0 transitionsLine is 1 0
THE STATE 0 REACHES THE STATE 1 WITH THE SYMBOL a
THE STATE 0 REACHES THE STATE 0 WITH THE SYMBOL b
for the state 1 transitionsLine is 2 0
THE STATE 1 REACHES THE STATE 2 WITH THE SYMBOL a
THE STATE 1 REACHES THE STATE 0 WITH THE SYMBOL b
for the state 2 transitionsLine is 2 0
THE STATE 2 REACHES THE STATE 2 WITH THE SYMBOL a
THE STATE 2 REACHES THE STATE 0 WITH THE SYMBOL b
finalStatesLine is 2
THE STATE 2 IS MARKED AS FINAL
THE INITIAL STATE ID IS 0
THE STATE 0 IS MARKED AS INITIAL
stringToProcess is abaa
THE FOUND INITIAL ONE IS 0
the actual state for baa is 0
the actual state for aa is 0
the actual state for a is 0
the actual state for is 0
**THE STRING abaa IS ACCEPTED AT STATE 2**
stringToProcess is aab
THE FOUND INITIAL ONE IS 0
the actual state for ab is 0
the actual state for b is 0
the actual state for is 0
**THE STRING aab IS REJECTED AT STATE 0**
stringToProcess is aba
THE FOUND INITIAL ONE IS 0
the actual state for ba is 0
the actual state for a is 0
the actual state for is 0
**THE STRING aba IS ACCEPTED AT STATE 1**
Case Number 2
alphabetLine is ade
for the state 0 transitionsLine is 0 1 2
THE STATE 0 REACHES THE STATE 0 WITH THE SYMBOL a
THE STATE 0 REACHES THE STATE 1 WITH THE SYMBOL d
THE STATE 0 REACHES THE STATE 2 WITH THE SYMBOL e
for the state 1 transitionsLine is 1 2 0
THE STATE 1 REACHES THE STATE 1 WITH THE SYMBOL a
THE STATE 1 REACHES THE STATE 2 WITH THE SYMBOL d
THE STATE 1 REACHES THE STATE 0 WITH THE SYMBOL e
for the state 2 transitionsLine is 2 1 0
THE STATE 2 REACHES THE STATE 2 WITH THE SYMBOL a
THE STATE 2 REACHES THE STATE 1 WITH THE SYMBOL d
THE STATE 2 REACHES THE STATE 0 WITH THE SYMBOL e
finalStatesLine is 1 2
THE STATE 1 IS MARKED AS FINAL
THE STATE 2 IS MARKED AS FINAL
THE INITIAL STATE ID IS 2
THE STATE 2 IS MARKED AS INITIAL
stringToProcess is a
THE FOUND INITIAL ONE IS 2
the actual state for is 0
**THE STRING a IS ACCEPTED AT STATE 2**
stringToProcess is de
THE FOUND INITIAL ONE IS 2
the actual state for e is 0
the actual state for is 0
**THE STRING de IS REJECTED AT STATE 0**
أنا أحصل على خطأ كل الخطوط المكتوبة بخط غامق.
انا احصل:
Case Number 1
THE STRING abaa IS ACCEPTED AT STATE 0
THE STRING aab IS ACCEPTED AT STATE 0
THE STRING aba IS ACCEPTED AT STATE 0
Case Number 2
THE STRING a IS ACCEPTED AT STATE 0
THE STRING de IS ACCEPTED AT STATE 0
بلدي Automaton يقبل كل شيء والتعالق على الدولة 0، لماذا؟
المحلول
أنا متأكد من أن المشكلة هي أن الدولة تحتاج إلى تجاوز. المساواة (كائن) و. hashcode (). أنا صدق allstates هو List<State> ولندات الاتصال (الولاية) في تلك القائمة تساوي قد تم تجاوزها.
نصائح أخرى
حسنا، لشيء واحد processState الطريقة لا يبدو أن تحديث currentState مجال Automaton على الإطلاق. في الواقع، لا يبدو أنك تعديل هذا في أي مكان.
من شأنه أن يساعد على الرغم من أنني شرحت ما تفعله أفضل قليلا. لقد ألقيت فقط الكثير من التعليمات البرمجية المصدر غير المستدلة وتقول "تعثر على الحالة 0"، على الرغم من أننا لا نعرف ما هي الحالة 0 أو كيف يمكن اكتشاف هذه الحالة. انا التخمين يشير ذلك الحالي إلى هذا، على الرغم من أن State لا تحتوي الحالات على أرقام إما، لذلك من الصعب معرفة مكان البدء في تحليل هذا ...
على الأقل، توفير بت من المعلومات (على الرغم من أن أكثر سيكون أفضل بكثير):
- القيم الميدانية / الإخراج التي تتوقع رؤيتها للإشارة إلى النجاح، وما الذي تراه حاليا (يكون صريح حول القيم المحددة لحقول معينة)؛
- المكان الذي تتوقع تحديث هذه الحقول وتحت الظروف.
لا تنتمي إلى StackOverflow
