有限狀態機搜索「ABBA」

我試圖編寫一個while開關案例有點代碼建模一個有限狀態機的搜索字符串「ABBA」是否存在的有限狀態機。當我輸入「ABBA」時，它會輸出Word found!。但是，如果我輸入"AABBA"它不會找到單詞&輸出正確的消息。任何幫助表示讚賞。謝謝！有限狀態機搜索「ABBA」

import java.util.*; 
public class AB{ 
    public static void main(String args[]){ 
     Scanner input = new Scanner(System.in); 
     String word = input.next(); 
     int current = 0; 
     int status = 0; 
     System.out.println("Starting to evaluate..."); 
     while(status != 4){ 
      for(int i = current; i < word.length(); i++){ 
       String part = word.substring(current, i + 1); 
       switch(status){ 
        case 0: //start 
         if(part.equals("A")){ 
          status = 1; 
         } 
         else if(part.equals("B"){ 
          status = 0; 
          current = i; 
         } 
        break; 
        case 1: //A is there now 
         if(part.equals("AB")){ 
          status = 2; 
         } 
         else if(part.equals("AA"){ 
          status = 1; 
          current = 1; 
         } 
        break; 
        case 2: //AB is there now 
         if(part.equals("ABB")){ 
          status = 3; 
         } 
         else if(part.equals("ABA"){ 
          status = 1; 
          current = 1; 
         } 
        break; 
        case 3: //ABB is there now 
         if(part.equals("ABBA")){ 
          status = 4; 
          System.out.println("Word found!"); 
         } 
         else if(part.equals("ABBB"){ 
          status = 0; 
          current = i; 
         } 
        break; 
       } 
      } 
     } 
    } 
}

來源

2017-07-28 Anna

而/開關結構是一個要求？ –

@AlexeyR。是的它是 – Anna

我改變了String word = input.next（）爲String word =「AABBA」，它工作正常。你確定這不是一個掃描儀問題。 – Malphrush

我在你的方法中看不到有效的是你實際上不使用狀態機的能力。首先你應該瞭解通過狀態驅動你的機器是什麼。在你的例子中，輸入字符串的每個順序字母都是。既然你已經採取了一種狀態，你現在應該檢查下一個符號將切換到哪個狀態。讓我提出以下實施..

下面是狀態圖：

這裏是實現框圖代碼：

public boolean abbaMatcher(String abba) 
{ 
    int state = 0; 
    int symbol = 0; 


    while (symbol < abba.length()){ 
     char c = abba.charAt(symbol); 
     switch (state){ 
      case 0: if(c == 'a'){ 
         state = 1; 
        }else{ 
         state = 0; 
        }; 
        break; 
      case 1: if(c == 'b'){ 
         state = 2; 
        }else{ 
         state = 1; 
        }; 
        break; 
      case 2: if(c == 'b'){ 
         state = 3; 
        }else{ 
         state = 1; 
        }; 
        break; 
      case 3: if(c == 'a'){ 
         return true; 
        }else{ 
         state = 0; 
        }; 
        break; 
     } 
     symbol++; 
    } 

    return false; 
}

這可能只用更容易被寫一個for循環，但是while/switch結構是一個要求。

來源

2017-07-28 16:48:03

你應該解決你對OPs代碼所做的改變，以及爲什麼你的工作更好。您還應該解決代碼中的問題。只是說，「使用此代碼」沒有幫助。 – Malphrush

你只是爲他們做了一些作業。在清晰抽象和功課的問題上，考慮問題會導致他們修復他們的解決方案，而不是在他們的膝蓋上放下答案。不是downvoting或任何東西，只是一個建議。 –

我喜歡它，但如果您添加轉換圖以便理解您的所有實現，它會更好。 –

以下代碼類似於您的實現，但它佔用動態序列（不同的序列），並且不會混淆子字符串，而是遍歷字符串的底層字符數組。

這也解釋了所有在啓動另一個序列，例如序列：字符串"ABABAB"在尋找序列"ABAB"將不得不在索引0和"ABAB"結果發現"ABAB"索引2.發現這可以很容易地被移除註釋掉wIndex = startIndex。

代碼：

public static void main (String[] args) throws java.lang.Exception { 
    // Scanner input = new Scanner(System.in); 
    String word = "B BABBABBA B"; 
    String seq = "ABBA"; 
    char[] wChars = word.toCharArray(); 
    char[] sChars = seq.toCharArray(); 
    int wIndex = 0; // wChars index 
    int sIndex = 0; // sChars index 
    int startIndex = 0; // starting index of the seq found in wChars 

    System.out.println("Starting to evaluate..."); 

    while(wIndex < wChars.length) { 
     if(wChars[wIndex] == sChars[sIndex]) { 
      if(sIndex == 0) { 
       startIndex = wIndex; 
      } 
      sIndex += 1; 
     } else { 
      sIndex = 0; 
     } 

     if(sIndex >= sChars.length) { 
      System.out.println("Sequence \"" + seq + "\" found at index " + startIndex + "."); 
      sIndex = 0; 
      wIndex = startIndex; // set wIndex to startIndex to account for 
           // sequence within a sequence, basically 
           // backtracking 
     } 

     wIndex += 1; 
    } 
}

輸出：

Starting to evaluate... 
Sequence "ABBA" found at index 3. 
Sequence "ABBA" found at index 6.

來源

2017-07-28 17:09:26

有限狀態機搜索「ABBA」

回答

相關問題