解析布林表達式-php教程-PHP中文網

Parsing A Boolean Expression

1106。解析布林表達式

難度：難

主題：字串、堆疊、遞歸

布林表達式 是計算結果為 true 或 false 的表達式。它可以是以下形狀之一：

't' 的計算結果為 true。
'f' 的計算結果為 false。
'!(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) --> （假與真）-->假--> f.現在的表達式是「!(f)」。
- 然後，評估 !(f) -->不假-->真的。我們回傳 true。

約束：

1 4
表達式[i] 是下列字元之一：'(', ')', '&', '|', '!', 't', 'f', 和 ','。

提示：

寫一個函數“parse”，它呼叫輔助函數“parse_or”、“parse_and”、“parse_not”。

解：

我們將把解決方案分解為更小的函數，用於處理解析和評估不同類型的表達式：parse_or、parse_and、parse_not，以及一個主要的解析函數，用於遞歸地處理表達式的解析。我們將使用堆疊來追蹤嵌套表達式並逐步評估它們。

方法：

解析與遞歸:
- 遇到巢狀括號時使用堆疊來追蹤表達式。
- 依序處理字元並管理巢狀計算的堆疊。
- 遇到右括號 ) 時，提取最後一組表達式並應用邏輯運算（&、| 或 !）。
輔助函數:
- parse_or：如果至少一個子表達式為 true，則透過傳回 true 來評估 |(expr1, expr2, ..., exprN)。
- parse_and：只有當所有子表達式都為 true 時才傳回 true 來評估 &(expr1, expr2, ..., exprN)。
- parse_not：透過傳回子表達式的相反值來計算 !(expr)。
表達式處理:
- 像 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
?>

登入後複製

解釋：

主要函數（解析布林表達式）:
- 迭代表達式並將字元推入堆疊。
- 遇到 ) 時，它會收集括號內的所有元素，並根據運算（&、|、!）對其進行求值。
- 將結果轉換為「t」（真）或「f」（假）並將它們推回堆疊。
輔助函數:
- parse_and：如果所有子表達式都是「t」（true），則傳回 true。
- parse_or：如果任何子表達式為“t”，則傳回 true。
- parse_not：反轉單一子表達式的布林值。

演練範例：

輸入：「&(|(f))」
- 堆疊處理：
  - &, (, |, (, f, ), ) → 內部表達式 |(f) 計算為 f。
  - 產生 &(f)，其計算結果為 f。
- 輸出：假。
輸入：「|(f,f,f,t)」
- 評估 |手術：
  - 找到一個“t”，因此計算結果為 true。
- 輸出：true。
輸入：「!(&(f,t))」
- 堆疊處理：
  - !, (, &, (, f, ,, t, ), ) → &(f,t) 計算結果為 f。
  - 然後 !(f) 被評估為 true。
- 輸出：true。