1106。ブール式の解析

難易度: 難しい

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

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

• true と評価される 't'。
• false と評価される 'f'。
• '!(subExpr)' は、內(nèi)部式 subExpr. の 論理 NOT
として評価されます。
• '&(subExpr₁, subExpr₂, ..., subExpr_n)' は、內(nèi)部の 論理 AND として評価されます。式 subExpr₁、subExpr₂、...、subExpr_n ここで、n >= 1.
• '|(subExpr₁, subExpr₂, ..., subExpr_n)' は、內(nèi)部の 論理 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. ヘルパー関數(shù)「parse_or」、「parse_and」、「parse_not」を呼び出す関數(shù)「parse」を作成します。

解決策:

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

アプローチ：

1. 解析と再帰:

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

2. ヘルパー関數(shù):

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

3. 式の処理:

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

このソリューションを 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
?>

説明：

• メイン関數(shù) (parseBooleanExpression):

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

• ヘルパー関數(shù):

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

チュートリアルの例:

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

   • スタック処理:
     • &, (, |, (, f, ), ) → 內(nèi)部式 |(f) は f に評価されます。
     • 結(jié)果は &(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 は式の長さです。各文字の処理回數(shù)は限られています。
• 空間の複雑さ: O(N)、ネストされた式を追跡するために使用されるスタックが原因です。

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

連絡先リンク

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

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

• LinkedIn
• GitHub

以上がブール式の解析の詳細內(nèi)容です。詳細については、PHP 中國語 Web サイトの他の関連記事を參照してください。