infix-notation - ブール式から冗長な括弧を削除するアルゴリズム

Question

プレフィックス表記にブール式があります。だとしましょうor and A B or or C D E。それを中置記法に変換すると、 になり ((A and B) or ((C or D) or E))ます。まで減らしたい(A and B) or C or D or E。中置記法を減らすべきですか、それとも前置記法から式を減らす方が実際には簡単ですか。どのアルゴリズムを使用すればよいですか?

Answer 1

X % (X1 ? X2 ? .. ? Xn) % X(n+1)括弧は、Xi が括弧で囲まれた式またはブール値「?」である式で削除できます 。および "%" は、それぞれが "?" である場合に限り、演算子です。演算子は「%」演算子以上の優先順位を持っています。

中置記法の場合、最も内側の式を見つけ、括弧を削除できるかどうかを確認し、結果を保存し、親式を処理して、すべての括弧のチェックが完了するまで続行します。

これはマッピングの問題になります。後置記法により、括弧の削除が容易になります。接頭辞、中置記法、後置記法の変換は簡単です。