1106。解析布爾表達(dá)式

難度：難

主題：字符串、堆棧、遞歸

布爾表達(dá)式 是一個(gè)計(jì)算結(jié)果為 true 或 false 的表達(dá)式。它可以是以下形狀之一：

• 't' 的計(jì)算結(jié)果為 true。
• 'f' 的計(jì)算結(jié)果為 false。
• '!(subExpr)' 計(jì)算結(jié)果為內(nèi)部表達(dá)式 subExpr 的 邏輯 NOT。
• '&(subExpr₁, subExpr₂, ..., subExpr_n)' 計(jì)算結(jié)果為內(nèi)部的 邏輯 AND表達(dá)式 subExpr₁, subExpr₂, ..., subExpr_n 其中 n >= 1.
• '|(subExpr₁, subExpr₂, ..., subExpr_n)' 計(jì)算結(jié)果為內(nèi)部的 邏輯 OR表達(dá)式 subExpr₁, subExpr₂, ..., subExpr_n 其中 n >= 1.

給定一個(gè)表示布爾表達(dá)式的字符串表達(dá)式，返回該表達(dá)式的評(píng)估。

保證給定的表達(dá)式有效并遵循給定的規(guī)則。

示例1：

• 輸入： 表達(dá)式 = "&(|(f))"
• 輸出： false
• 說(shuō)明：
  • 首先，評(píng)估 |(f) --> f.現(xiàn)在的表達(dá)式是“&(f)”。
  • 然后，評(píng)估 &(f) --> f.現(xiàn)在的表達(dá)式是“f”。
  • 最后返回 false。

示例2：

• 輸入： 表達(dá)式 = "|(f,f,f,t)"
• 輸出： true
• 解釋： (false OR false OR false OR true) 的評(píng)估為 true。

示例 3：

• 輸入： 表達(dá)式 = "!(&(f,t))"
• 輸出： true
• 說(shuō)明：
  • 首先，評(píng)估 &(f,t) --> （假與真）-->假--> f.現(xiàn)在的表達(dá)式是“!(f)”。
  • 然后，評(píng)估 !(f) -->不假-->真的。我們返回 true。

約束：

• 1 4
• 表達(dá)式[i] 是以下字符之一：'(', ')', '&', '|', '!', 't', 'f', 和 ','。

提示：

1. 編寫(xiě)一個(gè)函數(shù)“parse”，它調(diào)用輔助函數(shù)“parse_or”、“parse_and”、“parse_not”。

解決方案：

我們將把解決方案分解為更小的函數(shù)，用于處理解析和評(píng)估不同類型的表達(dá)式：parse_or、parse_and、parse_not，以及一個(gè)主要的解析函數(shù)，用于遞歸地處理表達(dá)式的解析。我們將使用堆棧來(lái)跟蹤嵌套表達(dá)式并逐步評(píng)估它們。

方法：

1. 解析和遞歸:

   • 遇到嵌套括號(hào)時(shí)使用堆棧來(lái)跟蹤表達(dá)式。
   • 按順序處理字符并管理嵌套計(jì)算的堆棧。
   • 遇到右括號(hào) ) 時(shí)，提取最后一組表達(dá)式并應(yīng)用邏輯運(yùn)算（&、| 或 !）。

2. 輔助函數(shù):

   • parse_or：如果至少一個(gè)子表達(dá)式為 true，則通過(guò)返回 true 來(lái)評(píng)估 |(expr1, expr2, ..., exprN)。
   • parse_and：僅當(dāng)所有子表達(dá)式都為 true 時(shí)才返回 true 來(lái)評(píng)估 &(expr1, expr2, ..., exprN)。
   • parse_not：通過(guò)返回子表達(dá)式的相反值來(lái)計(jì)算 !(expr)。

3. 表達(dá)式處理:

   • 像 t 和 f 這樣的單個(gè)字符直接翻譯為 true 和 false。
   • 當(dāng)遇到運(yùn)算（&、|、!）時(shí)，內(nèi)部表達(dá)式將根據(jù)各自的規(guī)則進(jìn)行計(jì)算。

讓我們用 PHP 實(shí)現(xiàn)這個(gè)解決方案：1106。解析布爾表達(dá)式

<?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ù)（解析布爾表達(dá)式）:

  • 迭代表達(dá)式并將字符推入堆棧。
  • 遇到 ) 時(shí)，它會(huì)收集括號(hào)內(nèi)的所有元素，并根據(jù)運(yùn)算（&、|、!）對(duì)其進(jìn)行求值。
  • 將結(jié)果轉(zhuǎn)換為“t”（真）或“f”（假）并將它們推回堆棧。

• 輔助函數(shù):

  • parse_and：如果所有子表達(dá)式都是“t”（true），則返回 true。
  • parse_or：如果任何子表達(dá)式為“t”，則返回 true。
  • parse_not：反轉(zhuǎn)單個(gè)子表達(dá)式的布爾值。

演練示例：

1. 輸入：“&(|(f))”

   • 堆棧處理：
     • &, (, |, (, f, ), ) → 內(nèi)部表達(dá)式 |(f) 計(jì)算為 f。
     • 產(chǎn)生 &(f)，其計(jì)算結(jié)果為 f。
   • 輸出：假。

2. 輸入：“|(f,f,f,t)”

   • 評(píng)估 |手術(shù)：
     • 找到一個(gè)“t”，因此計(jì)算結(jié)果為 true。
   • 輸出：true。

3. 輸入：“!(&(f,t))”

   • 堆棧處理：
     • !, (, &, (, f, ,, t, ), ) → &(f,t) 計(jì)算結(jié)果為 f。
     • 然后 !(f) 被評(píng)估為 true。
   • 輸出：true。

復(fù)雜：

• 時(shí)間復(fù)雜度：O(N)，其中N是表達(dá)式的長(zhǎng)度。每個(gè)字符的處理次數(shù)有限。
• 空間復(fù)雜度：O(N)，因?yàn)槎褩Ｓ糜诟櫱短妆磉_(dá)式。

該解決方案非常適合約束條件，并且應(yīng)該有效處理輸入大小。

聯(lián)系鏈接

如果您發(fā)現(xiàn)本系列有幫助，請(qǐng)考慮在 GitHub 上給 存儲(chǔ)庫(kù) 一個(gè)星號(hào)或在您最喜歡的社交網(wǎng)絡(luò)上分享該帖子？。您的支持對(duì)我來(lái)說(shuō)意義重大！

如果您想要更多類似的有用內(nèi)容，請(qǐng)隨時(shí)關(guān)注我：

• 領(lǐng)英
• GitHub

以上是解析布爾表達(dá)式的詳細(xì)內(nèi)容。更多信息請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！