32

多くのテキスト エディターと IDE には、対応するかっこ、角かっこ、または中かっこのいずれかの開始文字または終了文字の上にカーソルを置くと、対応するかっこ、角かっこ、または中かっこを強調表示する機能があります。

テキスト ファイル内の開き括弧または閉じ括弧の位置から、一致する括弧の位置を見つけるために使用されるアルゴリズムは何ですか? これらの文字は入れ子にすることができるので、反対の文字が見つかるまでテキストを前後にスキャンするだけでは不十分です。

例：

最近、Java でBrainf*ckインタープリターを作成しているときに、この問題に遭遇しました。 その言語では while ループに類似しており、ネストすることができます[。]インタープリターは、データ ポインターの値に一致[または]依存するものを見つける必要があります。ネスティングの図については、 ROT13 サンプル コードを参照してください。

4

2 に答える 2

57

文字の配列内の開き括弧の位置を指定すると、カウンターを使用して一致する閉じ括弧を見つける単純なアルゴリズムがあります。

  • カウンターを 1 に初期化します。
  • テキストを順方向 (右方向) にループします。
    • 別の開き括弧が検出された場合は、カウンターをインクリメントします。
    • 閉じ括弧が検出された場合は、カウンターをデクリメントします。
  • カウンターがゼロになると、対応する閉じ括弧が見つかりました。

コードでは、これは次のようになります。

public int findClosingParen(char[] text, int openPos) {
    int closePos = openPos;
    int counter = 1;
    while (counter > 0) {
        char c = text[++closePos];
        if (c == '(') {
            counter++;
        }
        else if (c == ')') {
            counter--;
        }
    }
    return closePos;
}

閉じ括弧が与えられた場合に対応する開き括弧の位置を見つけるアルゴリズムは逆です。

  • カウンターを 1 に初期化します。
  • テキストを逆方向 (左方向) にループします。
    • 左括弧が検出された場合は、カウンターをデクリメントします。
    • 閉じ括弧が検出された場合は、カウンターをインクリメントします。
  • カウンターがゼロになると、対応する開き括弧が見つかりました。

コード内:

public int findOpenParen(char[] text, int closePos) {
    int openPos = closePos;
    int counter = 1;
    while (counter > 0) {
        char c = text[--openPos];
        if (c == '(') {
            counter--;
        }
        else if (c == ')') {
            counter++;
        }
    }
    return openPos;
}

注:上記の例はいずれも、括弧のバランスが取れていることを前提としているため、配列の境界チェックは行われません。実際の実装では、配列の末尾からはみ出していないことを確認し、そうであれば、入力テキストでかっこのバランスが取れていないことを示す例外をスロー (またはエラー コードを返します) します。

于 2012-10-05T18:44:11.720 に答える