1

文字列に一致する中かっこ、大かっこ、またはかっこがあるかどうかを確認したい。

For example:
{}
()
[]

スタックでできます。再帰でやりたい。私は同様の質問に対する回答を読んでいましたが、回答はスタックに再帰が混在していました。ユーザーは、再帰もスタックであるため、再帰メソッドのパラメーターにスタックを含める必要はないと言って、これらの回答に応答しました-これは私には理にかなっています。

ただし、大きな問題があります。文字列を逆方向に調べて、文字列が空になるまで最後にチェックした位置を常に削除しているので、true を返します。探しているものを保持するための追加のパラメーターをメソッドに追加せずに、特定の部分、ブレース、ブラケット、または括弧をチェックする方法を想像することはできません。それでも、これを行うためのより簡単な方法が必要であると私は考え続けています。

public boolean isBalanced(String in)
{
    if(in.isEmpty())
        return true;

    if(in.charAt(in.length()) == '}')
    {
        return recIsBalanced(in.substring(0, in.length()));
    }

    else if(in.charAt(in.length()) == ']')
    {

    }


    return recIsBalanced(in.substring(0, in.length()));
}
4

5 に答える 5

3

再帰を使用してこの問題を解決する最も簡単な方法は、文字列を両方向から縮小することです。が表示されるまで、左から右から繰り返します。これらが一致しない場合、文字列はバランスが取れていません。それ以外の場合は、これらの中括弧で囲まれた文字列に同じアルゴリズムを適用します。片方の端からのみ移動するのは非常に難しく、いくつかの状態を保存する必要があります。

編集：DanielFischerに感謝します。実際には、ブレースが見つかるまで、たとえば左から片側から繰り返します（このブレースが1つのリターンを開いていない場合false）。一致するブレースが見つかるまで、反対側（この場合は右）から繰り返します。これで、この中括弧で囲まれたサブストリングのバランスが取れていて、閉じブラケットの右側のストリングの両方が再帰を使用してバランスが取れている場合にのみ、ストリングのバランスがとられます。

于 2013-02-18T10:32:14.687 に答える
0 
boolean isBalanced(String str)
{
    if (str.isEmpty()) {
        return true;
    }
    else if (str.charAt(0) == '(') {
        return str.charAt(str.length() - 1) == ')'
            && isBalanced(str.substring(1, str.length()));
    }
    else if (str.charAt(0) == '[') {
        return str.charAt(str.length() -  1) == ']'
            && isBalanced(str.substring(1, str.length()));
    }
    else if (str.charAt(0) == '{') {
        return str.charAt(str.length() - 1) == '}'
            && isBalanced(str.substring(1, str.length()));
    }
    else {
        return true;
    }

}
于 2015-10-05T14:37:37.533 に答える
0

入力文字列を解析することで実行できます。この場合の文法は次のとおりです。

P -> (P)
P -> [P]
P -> {P}
P -> e  (Null)

文字列で解析された位置を追跡する方が簡単で、その再帰スタックは閉じる括弧を保持します。これは単純な python 実装です。

ps = { '{': '}', '(': ')', '[': ']'}
all_ps = set(['{', '}', '(', ')', '[', ']'])
read_position = 0

def _is_balanced( s, closing_par=None ):
  global read_position
  while read_position < len(s):
    if s[read_position] == closing_par:
      read_position += 1         # Read closing parenthesis
      return True
    elif s[read_position] in ps:
      read_position += 1         # Read opening parenthesis
      if not _is_balanced( s, ps[s[read_position-1]] ):
        return False
    else:
      if s[read_position] not in all_ps:
        read_position += 1       # Read non-parenthesis char
      else:
        return False            # It is closing parenthesis, witouh opening before
  return closing_par is None    # Are we looking for a closing parenthesis?

def is_balanced( s ):
  global read_position
  read_position = 0  # Reset parsing position
  return _is_balanced( s )
于 2013-02-18T16:04:18.113 に答える