ユーザーが特定のタスクに条件を追加できるアプリを開発しています。
たとえば、彼は条件 a、b、c、d を持ち、それらを最終的に次のように組み合わせることができます。
(a AND b) OR ( c AND d )
または
(a AND b AND c) or d
または
(a AND !b) AND c OR !d
等
括弧を削除して、これらの条件を同等のものに変換するにはどうすればよいですか?
質問する
5606 次
3 に答える
4
ブール代数のすべての式は、、、および(単項) のみANDを使用して、括弧なしで同等の式に変換できます。OR!NOT
以下は、単純だが非効率的なアルゴリズムです。
式の例を使用する(a OR !b) AND cと、
変数の真理値の組み合わせごとに真理値表を作成します。
| a | b | c | (a OR !b) AND c | | 0 0 0 | 0 | | 0 0 1 | 1 | | 0 1 0 | 0 | | 0 1 1 | 0 | | 1 0 0 | 0 | | 1 0 1 | 1 | | 1 1 0 | 0 | | 1 1 1 | 1 |式が true であるすべての値のセット (右端の列にあるすべての行) について、 s を使用して、その特定の値のセットに対してのみ true と評価される
1式を作成します。AND!| a | b | c | (a OR !b) AND c | | 0 0 0 | 0 | | 0 0 1 | 1 | (!a AND !b AND c ) | 0 1 0 | 0 | | 0 1 1 | 0 | | 1 0 0 | 0 | | 1 0 1 | 1 | (a AND !b AND c ) | 1 1 0 | 0 | | 1 1 1 | 1 | (a AND b AND c )式を OR で結合します。
(!a AND !b AND c ) OR (a AND !b AND c ) OR (a AND b AND c )結果の式が最小になることはめったにないため、後でいくつかの最小化手法を適用することをお勧めします。
(!a AND !b AND c) OR (a AND !b AND c) OR (a AND b AND c) = (!a AND !b AND c) OR (a AND c) = (!b AND c) OR (a AND c)
タダ！
ステップ 1 での真理値表の作成は (変数の数で) O(2^n) 操作であり、ひどいことに注意することが重要です。変数の数が自明でない場合は、おそらく別の手法を使用することをお勧めします。このアルゴリズムの主な利点は、任意の式を必要な形式に変換する方法が非常に明確になることです。
編集：明確にするために、通常の優先ルールを使用している場合は、最終式の括弧を削除できます。
于 2013-01-07T01:25:00.067 に答える
3
ブール代数のさまざまなプロパティを使用して式を単純化することができますが、すべての括弧を削除できない場合があります。NOT、AND、およびORの演算の順序がないため、一部の式では括弧が必要です。したがって、式を左から右に読み取るように再配置できない場合は、括弧が必要になります。
于 2012-11-27T15:59:27.137 に答える
0
括弧のない同等のものへの変換の動機が何であるか完全にはわからないので、ユーザーが目的のタスク条件をアプリに伝えるための表現機能 (つまり、表現言語) を確立しようとしているという意味であると解釈しました。
通常の演算子の優先順位規則を持つ通常の中置式言語では、括弧の必要性をなくして任意の複雑な式をサポートすることはできません。
あなたにはいくつかの選択肢があると思います：
括弧をサポートします。(それらを解析するのはそれほど難しくありません。)
RPN とも呼ばれる逆ポーランド記法など、括弧を使用しない代替の比較的標準的な、またはよく知られている表現言語を使用します。http://en.wikipedia.org/wiki/Reverse_Polish_notationを参照してください。RPN は、括弧を使用するのではなく、配置と積み重ねによって、ユーザーが演算子の優先順位を完全に制御できるようにする後置表記を使用します。これには、オペランドと演算を慎重に (再) 順序付けする必要があるという犠牲が伴います。（フリーランチはありません。）
言語の表現力を、より通常の (中置) 言語 (演算子の優先順位を持つ) で括弧を必要としない特定のパターンに制限します。
最後に、(テキスト言語ではなく) ユーザーが式を作成するのに役立つユーザー インターフェイスがある場合は、上記の #2 のようなことを行い、ユーザーがサブ式を定義する順序を使用して、括弧を必要とせずに演算子の優先順位を示すことができます。基本的に、UI は式ツリーの構築を支援します。
最後に、式を実行する目的で括弧を削除する方法について質問がある場合、これはコード生成の問題に似ています。ここでも、RPN のスタックが役立ちます。または、(潜在的に括弧で囲まれた) 式を、追加の (コンパイラ用語では一時的な) 変数によって明示的に接続された個々のミニ (たとえば、3 つのオペランド) ステートメントに変換できます。たとえば、 の後に(a + b) * cがt1 = a + b続きfinal-result = t1 * cます。
于 2012-12-11T02:54:37.160 に答える