これに正式にアプローチして、多くのデバッグを行わなくても実用的なソリューションを思い付く可能性を高めましょう。
バランスの取れた文字列とは何ですか？簡単な文法は次のとおりです。
BalancedString: Sequence end-of-string;
Sequence:
Fragment Sequence |
(* empty *);
Fragment:
'(' Sequence ')' |
'[' Sequence ']' |
'{' Sequence '}' |
any-character-not-in-'()[]{}';
この文法は(hello)[[good]{bye}]、複数の「トップレベル」グループを持つような文字列を生成することに注意してください。
それを再帰下降パーサーに変えましょう。各非終端記号（、、、BalancedStringおよびSequence）Fragmentは関数になります。'BalancedString'非終端記号を解析する関数から始めます。
private static bool parseBalancedString(String input, int offset) {
offset = parseSequence(input, offset);
return offset == input.length();
}
parseSequenceこの関数は、解析を停止したオフセットを返すことを期待していることに注意してください。parseSequence次に書きましょう。直接再帰的にする代わりに、ループを使用します。
private static int parseSequence(String input, int offset) {
bool parseSucceeded = true;
while (parseSucceeded) {
int newOffset = parseFragment(input, offset);
parseSucceeded = newOffset > offset;
newOffset = offset;
}
return offset;
}
parseSequenceは、解析を停止したオフセットを返すことを期待していることに注意しparseFragmentてください。失敗した場合は、渡されたオフセットを返す必要があります。今、私たちは書くでしょうparseFragment。3つの類似したプロダクションから共通のコードをヘルパー関数に抽出します。
private static int parseFragment(String input, int offset) {
if (offset >= input.length()) {
return offset;
}
switch (input.charAt(offset)) {
case '(': return helpParseFragment(input, offset, ')');
case '[': return helpParseFragment(input, offset, ']');
case '{': return helpParseFragment(input, offset, '}');
default: return offset + 1;
}
}
ヘルパー関数は、オープナーのオフセットを受け取ることを期待しているため、失敗した場合はそのオフセットを返すことができます。成功すると、クローザーを過ぎたオフセットを返します。
private static int helpParseFragment(String input, int offset, char closer) {
int newOffset = parseSequence(input, offset + 1);
if (newOffset > offset && newOffset < input.length() && input.charAt(newOffset) == closer) {
return newOffset + 1;
} else {
return offset;
}
}