私は、命題論理ステートメントを接続法標準形に翻訳することに取り組んでいます。私が抱えている問題は、おそらく複雑な括弧のレベルを解析することです。私が解決する必要がある問題は正しい順序であり、外側に移動する前に最初に内括弧を解決するために再帰を使用する必要があると思いますが、自分のアイデアを実装する方法がわかりません。プログラムはJavaで書かれています。誰でも助けることができますか？
質問する
3127 次
3 に答える
1
CNF に変換するステートメントの例を教えてください。開始論理ステートメントに括弧があることを意味していると思いますが、見るのに役立ちます。
それまでの間、再帰は必要ないと言います... しかし、スタックは非常に役に立ちます:) アイテムとその数学演算をスタックにプッシュし、それらをポップして、必要に応じてそれらに作用します。宿題なので詳しくは説明しませんが、push-push-push-pop-multiply-push-push-pop-add-pop-divide... スタックを次のように使用します。現在の操作に集中する方法。
Postfix Notation の調査も関連しており、役立つ可能性があります...それに関するウィキペディアの記事でさえ、いくつかのアイデアを提供します (ただし、コンピューターサイエンス指向の記事は絶対にもっとあります)。
免責事項: 私の例では、これらのプッシュとポップの数や順序については考えていません :)
アップデート
データを複数回通過させる必要はなく、その場で CNF に変換できます。
あなたは正しい方向に向かっているので、いくつかのヘルプ/ヒント:
- オペランド用と演算子用の 2 つのスタックを使用します。
- 2 つのオペランドと 1 つの演算子がある場合、オペランドをポップし、演算子を適用して、結果を新しい (統合された) オペランドとしてプッシュします。
- 後置の利点は、オンザフライで変換できることです...たとえば、→に遭遇した場合、オペランド スタックに ¬ を適用し、演算子スタックに ⋁ をプッシュします。
あなたの例を縮小すると：
F→(E⋀(A→B))
変換の最初のステップは次のようになります (基礎となる論理変換規則が完全に理解されており、それが作業中のコードに過ぎないと仮定しています):
F→(E⋀(A→B))
¬F⋁(E⋀(A→B))
¬F⋁(E⋀(¬A⋁B))
CNF postfix では、次のようになります。
F¬EA¬B⋁⋀⋁ // (Parentheses are obviated in postfix notation)
そこにたどり着くには、最初の論理ステートメントを左から右に 1 回のパスで読み取ります... オペランドをオペランド スタックにプッシュし、演算子をオペレーター スタックにプッシュします。
演算子を適用すると、オペランド スタックから必要なオペランドがポップされ、演算子が適用され、結果の文字列が新しいオペランドとしてスタックにプッシュされます。
閉じ括弧または優先度の低い操作は、pop-apply-push をトリガーします。全体は次のようになります。
Operand Operator
Stack Stack
---------- ----------
Read F: Push onto Operand stack F ........ ..........
Read →: On-the-fly conversion (→ becomes ¬⋁)
Unary Operator ¬ pops F from Operands; applies it; pushes back to Operands
¬F ....... ..........
Push ⋁ onto the op-stack ¬F ....... ⋁ .......
Read (: Discard
Read E: Push onto Operands stack ¬F E .... ⋁ ......
Read ⋀: Push onto Operators stack ¬F E .... ⋁⋀ .....
Read (: Discard
Read A: Push onto Operands stack ¬F E A .. ⋁⋀ .....
Read →: On-the-fly conversion (→ becomes ¬⋁)
Unary Operator ¬ pops A from Operands; applies; pushes back to Operands
¬F E ¬A . ⋁⋀ .....
Push ⋁ onto Operators stack ¬F E ¬A . ⋁⋀⋁ ....
Read B: Push onto Operands stack ¬F E ¬A B ⋁⋀⋁ ....
Read ): Triggers Operators/Operands pop; applies; pushes back to Operands
(After, there are three operands on the Operands stack)
¬F E (¬A⋁B) ⋁⋀ ....
Read ): Triggers Operators/Operands pop; applies; pushes back to Operands
(After, there are two operands on the Operands stack)
¬F (E⋀(¬A⋁B)) ⋁ ....
No more reads: Final Operators/Operands pop/apply/push (result is output)
¬F⋁(E⋀(¬A⋁B))
注意事項と注意事項:
これは正しい方向への出発点にすぎません...演算子の優先順位などの問題に対処する必要があります(つまり、プッシュして後で行動するか、ポップして今行動するか)。決定は、次に読む文字に基づいていることがわかります (上で暗示したように、閉じ括弧ではありません)。
それは実際よりも複雑に聞こえます...上記の疑似コードは12〜15行を超えることはありません。ただし、私が対処していない複雑さがあります... <--> 関数は → と同様の方法でモデル化する必要があります... この考え方を採用して、すべての機能を実装する必要があります変換規則。
暗黙の括弧はあなたをつまずかせる可能性があります。
6 * (8 * 6) + 4
本当に
(6 * (8 * 6)) + 4
演算子の優先順位を正しく処理しないと、次のような結果になる可能性があります
686*4+*
これにより、正しい答え (292) ではなく、312 が得られます。
この投稿の Unicode 論理記号を読むのに問題がある場合は、お知らせください。標準の文字でやり直すこともできますが、Uni で読むとはるかに読みやすくなります :)
HTH、
ジェームズ
PS: Postfix を示す気の利いた小さなアプレットはこちら:
http://fac-web.spsu.edu/cs/faculty/bbrown/web_lectures/postfix/
于 2012-04-30T19:27:39.940 に答える
0
擬似コード:
parseRestOfString (int openParens, String rest) {
c = rest (0);
if (c == ')' && openParens == 0) ...
それはあなたにヒントを与えますか？
于 2012-04-30T19:23:22.433 に答える