ブール式の解析

1106。ブール式の解析

難易度: 難しい

トピック: 文字列、スタック、再帰

ブール式は、true または false に評価される式です。次のいずれかの形状になります:

• true と評価される 't'。
• false と評価される 'f'。
• '!(subExpr)' は、内部式 subExpr. の 論理 NOT
として評価されます。
• '&(subExpr₁, subExpr₂, ..., subExpr_n)' は、内部の 論理 AND として評価されます。式 subExpr₁、subExpr₂、...、subExpr_n ここで、n >= 1.
• '|(subExpr₁, subExpr₂, ..., subExpr_n)' は、内部の 論理 OR として評価されます。式 subExpr₁、subExpr₂、...、subExpr_n ここで、n >= 1.

ブール式を表す文字列式を指定すると、その式の評価を返します。

指定された式が有効であり、指定されたルールに従っていることが保証されます。

例 1:

• 入力: 式 = "&(|(f))"
• 出力: false
• 説明:
  • まず、 |(f) --> を評価します。 f.式は「&(f)」になりました。
  • 次に、&(f) --> を評価します。 f.式は「f」になりました。
  • 最後に false を返します。

例 2:

• 入力: 式 = "|(f,f,f,t)"
• 出力: true
• 説明: (false OR false OR false OR true) の評価は true です。

例 3:

• 入力: 式 = "!(&(f,t))"
• 出力: true
• 説明:
  • まず、&(f,t) --> を評価します。 (偽 AND 真) --> false --> f.式は「!(f)」になりました。
  • 次に、!(f) --> を評価します。 false ではありません -->真実。 true を返します。

制約:

• 1 4
• expression[i] は、「(」、「)」、「&」、「|」、「!」、「t」、「f」、「,」のいずれかの文字です。

ヒント:

1. ヘルパー関数「parse_or」、「parse_and」、「parse_not」を呼び出す関数「parse」を作成します。

解決策:

ソリューションを、さまざまなタイプの式の解析と評価を処理する小さな関数 (parse_or、parse_and、parse_not)、および式の解析を再帰的に処理するメインの解析関数に分割します。スタックを使用してネストされた式を追跡し、段階的に評価します。

アプローチ：

1. 解析と再帰:

   • ネストされた括弧が見つかった場合は、スタックを使用して式を追跡します。
   • 文字を順番に処理し、ネストされた評価のスタックを管理します。
   • 右括弧 ) が見つかった場合は、式の最後のセットを抽出し、論理演算 (&、|、または !) を適用します。

2. ヘルパー関数:

   • parse_or: 少なくとも 1 つの部分式が true の場合に true を返すことによって |(expr1, expr2, ..., exprN) を評価します。
   • parse_and: すべての部分式が true の場合にのみ true を返すことによって &(expr1, expr2, ..., exprN) を評価します。
   • parse_not: 部分式の逆を返すことによって !(expr) を評価します。

3. 式の処理:

   • t や f のような単一の文字は、直接 true と false に変換されます。
   • 演算 (&、|、!) が発生すると、内部式はそれぞれのルールに基づいて評価されます。

このソリューションを PHP で実装してみましょう: 1106。ブール式の解析

<?php
/**
 * @param String $expression
 * @return Boolean
 */
function parseBooleanExpression($expression) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * the logical AND
 * 
 * @param $subExpr
 * @return bool
 */
function parse_and($subExpr) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * the logical OR
 * 
 * @param $subExpr
 * @return bool
 */
function parse_or($subExpr) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}
/**
 * the logical NOT
 * 
 * @param $subExpr
 * @return bool
 */
function parse_not($subExpr) {
    // subExpr contains only one element for NOT operation
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo parseBooleanExpression("&(|(f))") ? "true" : "false"; // Output: false
echo "\n";
echo parseBooleanExpression("|(f,f,f,t)") ? "true" : "false"; // Output: true
echo "\n";
echo parseBooleanExpression("!(&(f,t))") ? "true" : "false"; // Output: true
?>

説明：

• メイン関数 (parseBooleanExpression):

  • 式を反復処理し、文字をスタックにプッシュします。
  • ) に遭遇すると、括弧内のすべての要素を収集し、演算 (&、|、!) に基づいて評価します。
  • 結果を 't' (true) または 'f' (false) に変換し、スタックにプッシュします。

• ヘルパー関数:

  • parse_and: すべての部分式が 't' (true) の場合、true を返します。
  • parse_or: 部分式が 't' の場合は true を返します。
  • parse_not: 単一の部分式のブール値を反転します。

チュートリアルの例:

1. 入力: "&(|(f))"

   • スタック処理:
     • &, (, |, (, f, ), ) → 内部式 |(f) は f に評価されます。
     • 結果は &(f) となり、f と評価されます。
   • 出力: false。

2. 入力: "|(f,f,f,t)"

   • | を評価します。手術：
     • 「t」を 1 つ見つけると、true と評価されます。
   • 出力: true。

3. 入力: "!(&(f,t))"

   • スタック処理:
     • !, (, &, (, f, ,, t, ), ) → &(f,t) は f に評価されます。
     • !(f) は true と評価されます。
   • 出力: true。

複雑：

• 時間計算量: O(N)、N は式の長さです。各文字の処理回数は限られています。
• 空間の複雑さ: O(N)、ネストされた式を追跡するために使用されるスタックが原因です。

このソリューションは制約に適しており、入力サイズを効果的に処理できるはずです。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上がブール式の解析の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。