如何解析布尔表达式？F#递归实现布尔表达式求值求助

你的思路非常靠谱！这种"剥洋葱"式优先处理最内层括号、求值替换后再重复的方式，完全适配递归逻辑，理解起来也特别直观。我来一步步帮你把这个思路转换成可运行的F#代码：

第一步：实现无括号表达式的求值辅助函数 #

首先我们需要一个小函数，用来处理没有嵌套括号的简单布尔表达式（比如T|F、T&T&T），把它计算成T或F字符串。核心是拆分操作符和操作数，再按布尔逻辑计算：

let evaluateSimpleExpr (expr: string) =
    // 拆分操作数和操作符
    let parts = expr.Split([|'&'; '|'|], System.StringSplitOptions.RemoveEmptyEntries) |> Array.map (fun s -> s.Trim())
    let ops = expr |> Seq.filter (fun c -> c = '&' || c = '|') |> Seq.toList

    // 递归计算结果
    let rec compute acc ops parts =
        match ops, parts with
        | [], [_] -> acc
        | op::restOps, part::restParts ->
            let nextVal = part = "T"
            let newAcc = 
                match op with
                | '&' -> acc && nextVal
                | '|' -> acc || nextVal
                | _ -> failwithf "无效操作符: %c" op
            compute newAcc restOps restParts
        | _ -> failwith "表达式格式错误"

    let initialVal = parts.[0] = "T"
    let result = compute initialVal ops parts.[1..]
    if result then "T" else "F"

第二步：实现递归处理带括号的表达式 #

接下来是主递归函数，完全按照你的思路来：找到最内层括号→求值→替换→递归处理新字符串，直到只剩T或F：

let rec evaluateBoolExpr (expr: string) =
    // 判断是否已经是最终结果
    match expr.Trim() with
    | "T" -> true
    | "F" -> false
    | s ->
        // 找最右边的'('（对应最内层括号的左括号）
        let leftParenIndex = s.LastIndexOf('(')
        if leftParenIndex = -1 then
            // 无括号直接用辅助函数求值
            evaluateSimpleExpr s = "T"
        else
            // 匹配对应的右括号
            let rightParenIndex = s.IndexOf(')', leftParenIndex)
            if rightParenIndex = -1 then
                failwith "括号不匹配"
            // 提取并计算括号内的表达式
            let innerExpr = s.Substring(leftParenIndex + 1, rightParenIndex - leftParenIndex - 1)
            let innerResult = evaluateSimpleExpr innerExpr
            // 替换原字符串并递归处理
            let newExpr = s.Remove(leftParenIndex, rightParenIndex - leftParenIndex + 1).Insert(leftParenIndex, innerResult)
            evaluateBoolExpr newExpr

第三步：测试你的示例 #

用你给出的例子验证一下效果：

// 测试1: (T|F) → true
evaluateBoolExpr "(T|F)" // 返回 true

// 测试2: (T&(T&T)) → true
evaluateBoolExpr "(T&(T&T))" // 返回 true

// 测试3: ((T|T)&(T&F)) → false
evaluateBoolExpr "((T|T)&(T&F))" // 返回 false

// 测试4: (F) → false
evaluateBoolExpr "(F)" // 返回 false

一些可优化的点 #

• 目前代码未处理错误输入（比如无效字符、不匹配括号、空表达式等），如果需要可以添加参数检查和错误处理逻辑。
• 极端复杂的表达式可能触发递归栈限制，日常使用基本不会遇到；若要支持极端场景，可以改成尾递归或循环实现。

内容的提问来源于stack exchange，提问作者BigBlackBunny