解析布尔表达式

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', 和 ','。

提示：

1. 编写一个函数“parse”，它调用辅助函数“parse_or”、“parse_and”、“parse_not”。

解决方案：

我们将把解决方案分解为更小的函数，用于处理解析和评估不同类型的表达式：parse_or、parse_and、parse_not，以及一个主要的解析函数，用于递归地处理表达式的解析。我们将使用堆栈来跟踪嵌套表达式并逐步评估它们。

方法：

1. 解析和递归:

   • 遇到嵌套括号时使用堆栈来跟踪表达式。
   • 按顺序处理字符并管理嵌套计算的堆栈。
   • 遇到右括号 ) 时，提取最后一组表达式并应用逻辑运算（&、| 或 !）。

2. 辅助函数:

   • parse_or：如果至少一个子表达式为 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
?>

解释：

• 主要函数（解析布尔表达式）:

  • 迭代表达式并将字符推入堆栈。
  • 遇到 ) 时，它会收集括号内的所有元素，并根据运算（&、|、!）对其进行求值。
  • 将结果转换为“t”（真）或“f”（假）并将它们推回堆栈。

• 辅助函数:

  • parse_and：如果所有子表达式都是“t”（true），则返回 true。
  • parse_or：如果任何子表达式为“t”，则返回 true。
  • parse_not：反转单个子表达式的布尔值。

演练示例：

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

   • 堆栈处理：
     • &, (, |, (, f, ), ) → 内部表达式 |(f) 计算为 f。
     • 产生 &(f)，其计算结果为 f。
   • 输出：假。

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

   • 评估 |手术：
     • 找到一个“t”，因此计算结果为 true。
   • 输出：true。

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

   • 堆栈处理：
     • !, (, &, (, f, ,, t, ), ) → &(f,t) 计算结果为 f。
     • 然后 !(f) 被评估为 true。
   • 输出：true。

复杂：

• 时间复杂度：O(N)，其中N是表达式的长度。每个字符的处理次数有限。
• 空间复杂度：O(N)，因为堆栈用于跟踪嵌套表达式。

该解决方案非常适合约束条件，并且应该有效处理输入大小。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是解析布尔表达式的详细内容。更多信息请关注PHP中文网其他相关文章！