ブール代数が一致すると真を返すメソッド

Question

中括弧の文字列を受け取り、カッコが一致する場合はtrueを返し、一致しない場合はfalseを返すメソッドを作成しようとしています。

これらブラケットマッチングの例である：

{}

{} {}

{{}}

{{{{{}}}}

これは、一致しない角括弧の例です。

{

} {

{{}

{{}}} {}

私はこのコードの後ろに適切なロジックを把握することができません。私は最初にlength（）mod 2を試しました。結果が0の場合にのみ、このメソッドはtrueを返します。しかし明らかにバグがありました。なぜなら、{}のような文字列であっても真実を返すからです。 {を検出するコードをいくつか追加し、見つからない場合は自動的にfalseを返します。しかし、私はまだ誤りを受けています。ここで

は私のコードです：

public boolean bracketsMatch(String brackets) 
{ 
    if(!(brackets.length() % 2 == 0)) 
    { 
     int i = 0; 
     int j = 0; 
     boolean check = false; 
     while(brackets.charAt(i) == '{') 
     { 
      for(int o = i + 1; o < brackets.length(); o++) 
      { 
       if(o == '}') 
       { 
        check = true; 
        break; 
       } 
       else 
       { 
       j++; 
       } 
      } 

      if(check == false) 
       return false; 

      i + = j; 
     } 

     return true; 
    } 
    else 
    { 
     return false; 
    } 
} 

正しいこの問題のロジック、と私は何の間違いを作っていますでしょうか？ありがとう！

Answer 1

カウンタを使用してください。 {を見つけたらそれを増やし、}を見つけるとそれを減らしてください。ある時点でカウンタが負の場合、stringは無効です。すべての文字を処理した後にcounterが0の場合はtrueを返します。

OK

{ } 
1 0 

{ } { } 
1 0 1 0 

{ { } } 
1 2 1 0 

{ { { } { { } } } } 
1 2 3 2 3 4 3 2 1 0 

ないOK

{ 
1 

} { 
-1 <- no point checking farther 

{ { } 
1 2 1 

{ { } } } { } 
1 2 1 0 -1 <- no point checking farther 

Answer 2

文字列を繰り返します。開いている括弧をクリックするとスタックにプッシュします。閉じた括弧がある場合は、スタックから括弧を開きます。スタックを空にしてポップしたとき、または反復処理が完了したときにスタックにまだ開いている括弧が残っている場合は、括弧は釣り合っていません

複数のタイプのバランスをチェックしているなら、 ] {}など、あなたがポップアップしたときに、ポップされたオープニングブラケットが、あなたが直前に見つけた閉じブラケットと同じタイプであることを確認する必要があります。

Answer 3

私は@Pshemoさんanswerで説明したアルゴリズムが好きで、エレガントな実装では、私に起こりました。結果が負の場合は、for-eachループとswitchでcountを{にデクリメントして}とreturn falseを増やすことができます。countは、私はまた、あなたのシナリオ

実装がここに渡す

public static void main(String[] args) { 
    String[] good = { "{ }", "{ } { }", "{ { } }", "{ { { } { { } } } }" }; 
    String[] bad = { "{", "} {", "{ { }", "{ { } } } { }" }; 
    for (String str : good) { 
     if (!bracketsMatch(str)) { 
      System.out.printf("error with good: %s%n", str); 
     } 
    } 
    for (String str : bad) { 
     if (bracketsMatch(str)) { 
      System.out.printf("error with bad: %s%n", str); 
     } 
    } 
} 

を使用して、上記のための小型のユニットテストを作成し

public static boolean bracketsMatch(String brackets) { 
    int count = 0; 
    for (char ch : brackets.toCharArray()) { 
     switch (ch) { 
     case '{': count++; break; 
     case '}': if (--count < 0) return false; 
     } 
    } 
    return count == 0; 
} 

のようなものが付いている方0であることを確認するために、思い出し。