6

質問：

文字列から余分な括弧を削除します。
例えば 

    ((a+b))*c       => (a+b)*c  
    (a+b)+c         => (a+b)+c  
    ((a+b)/(c+d))   => ((a+b)/(c+d))   
    (a+(((b-c)))*d) => (a+(b-c)*d)  and so on.

私は次の解決策を思いつきました:
アプローチ: 文字列をスキャンし、(マップを使用して) 左括弧のインデックスと、それが余分かどうか (デフォルトでは余分です) を覚えています。閉じ括弧が見つかった場合は、マップから対応する開き括弧を確認し、余分な場合は両方を削除します。

void removeExtraParentheses(string& S){
  map<int, bool> pmap;
  for(int i = 0; i < S.size(); i++){
    map<int, bool>::iterator it;
    if(S.at(i) == '('){
        pmap[i] = true;
    }
    else if(S.at(i) == ')'){
        it = pmap.end();
        it--;
        if(!(*it).second){
            pmap.erase(it);
        }
        else{
            S.erase(S.begin() + i);
            S.erase(S.begin() + (*it).first);
            pmap.erase(it);
            i = i - 2;
        }
    }
    else{
        if(!pmap.empty()){
            it = pmap.end();
            it--;
            (*it).second= false;
        }
    }
  }
}

時間の複雑さ: O(n2)
スペース: O(n)
余分なストレージを使用し、二次時間で実行しているため、ソリューションにあまり満足していません。

これを O(n) 時間と O(1) 空間で実行できるでしょうか? そうでない場合、何ができるのが最善ですか？

4

3 に答える 3

3

式ツリーを構築し、最小の括弧で式を再生成します。生成されていない元の括弧は不要です。

簡単でほぼ正しい解決策は、各演算子に優先順位を割り当てることです。作業中のノードの直下にあるノードが、そのノードよりも優先順位の低い演算子である場合は常に括弧が必要です。たとえば、* (乗算) ノードにいて、2 つの子ノードの 1 つが+ (加算) ノードである場合。さらに、左バインディングまたは右バインディングを処理するためのいくつかのロジック:+ノードにいて、右側のノードも+ノードである場合は、括弧が必要です。

これは部分的にしか正しくありません。C++ には、実際には優先順位文法にマッピングできない構造がいくつかあるためです。型キャスト構造の一部、または三項演算子が頭に浮かびます。ただし、少なくとも三項演算子の場合、特別な処理はそれほど難しくありません。

編集：

あなたの大きな質問に関して：メモリ内に式全体を構築する必要があるため、これは明らかに空間内の O(1) ではありません。メモリの O(1) は可能ではないと思います。潜在的に、無制限のネストが可能であり、かっこが必要かどうかは不確定な時間後までわからないためです。実際に分析したわけではありませんが、時間的には O(n) だと思います。ノード数の上限はn(文字列の長さ) であり、各ノードに 1 回だけアクセスする必要があります。

于 2012-11-02T23:45:16.553 に答える
2

多かれ少なかれウェブで見つけた...

与えられた入力: ((A+B)*C) 期待される出力: (A+B)*C

仮定:

  • Peek (キュー) は、キューの前端にある要素を削除せずに伝えるだけです。
  • precedence( ) は、演算子の優先順位テーブルを参照する関数です

以下の疑似コード：

  1. 中置式を RPN に変換します (例: Shunting-yard algo O(n))

    AB+C*

  2. 演算子のみをキューに挿入Q

    (フロント)+ -------- *(リア)

  3. 後置式を解析する
  4. オペランドの場合、スタック 'S' にプッシュする
  5. If 演算子
    • y=削除(Q)
    • if precedence(y) > precedence(peek(Q)), then Push (S, "Pop(S) y Pop(S)")
    • if precedence(y) < precedence(peek(Q)), then Push (S, "( Pop(S) y Pop(S) )")
  6. 上の最終結果S

すべて O(n) である必要があります。

于 2012-11-02T23:58:11.890 に答える
0

これを刺そうと思いました。これが私の頭に浮かんだ問題の解決策です。これは疑似コードであり、直接実行するためのものではないことに注意してください。

(実際には、どちらかというと C++ っぽいですが、実際の C++ を最後に書いてからしばらく経ちました。アルゴリズムを理解することを意図していたときに、すべてを正しくするために努力する気がしませんでした。)

queue<tuple<int, bool> > q = new queue<tuple<int, bool> >();

for (int i = 0; i < str.length; i++)
{
    char a = str.charAt(i);

    if (a == '(')
    {
        q.push(new tuple<int, bool>(i, false));
    }
    else if (a == ')')
    {
        if (q.top().bool)
        {
            // remove top.int and i from string
        }

        q.pop();
        q.top().bool = true;
    }
    else
    {
        q.top().bool = false;
    }
}

でジョブを実行し、スペースO(n)を使用しO(n)ます (実際には、使用されるスペースの量は、実際には文字列に存在する最も深いネスト レベルに基づいていますが、 よりも低いことが保証されていますn) 。

(// remove top.int and i from stringこれは実際には ではできないことに注意してくださいO(1)。ただし、少し工夫すれば で同様のことができますO(1)。たとえば、出力用の文字のリストを実際に作成し、int の代わりにイテレータを格納することができます。次に、O(1) の 2 つの文字を削除できます。最後に、O(n) のリストを繰り返し処理することにより、最終的な文字列を構築できます。別の解決策は、DummyOrCharacters の配列 (またはベクトル) で実際に作業することです。 , これはダミーで何も含まないか, 文字を含んでいます. もう一度, で文字をダミーで置き換えることができますO(1). もう一度, 構造を繰り返し処理し, で出力文字列を作成しますO(n))

于 2012-11-03T00:04:21.157 に答える