【2022-11-05每日一题】1106. 解析布尔表达式[Hard]

2022-11-05
2分钟阅读时长

2022-11-05每日一题:1106. 解析布尔表达式

难度:Hard

标签:栈 、 递归 、 字符串

给你一个以字符串形式表述的 布尔表达式(boolean) expression,返回该式的运算结果。

有效的表达式需遵循以下约定:

  • "t",运算结果为 True
  • "f",运算结果为 False
  • "!(expr)",运算过程为对内部表达式 expr 进行逻辑 非的运算(NOT)
  • "&(expr1,expr2,...)",运算过程为对 2 个或以上内部表达式 expr1, expr2, ... 进行逻辑 与的运算(AND)
  • "|(expr1,expr2,...)",运算过程为对 2 个或以上内部表达式 expr1, expr2, ... 进行逻辑 或的运算(OR)

 

示例 1:

输入:expression = "!(f)"
输出:true

示例 2:

输入:expression = "|(f,t)"
输出:true

示例 3:

输入:expression = "&(t,f)"
输出:false

示例 4:

输入:expression = "|(&(t,f,t),!(t))"
输出:false

 

提示:

  • 1 <= expression.length <= 20000
  • expression[i]{'(', ')', '&', '|', '!', 't', 'f', ','} 中的字符组成。
  • expression 是以上述形式给出的有效表达式,表示一个布尔值。

方法一:

详细思路过程见官方题解,这里只做个人刷题记录,方便后续查询阅读

func parseBoolExpr(expression string) bool {
    stk := []rune{}
    // range 遍历 c 的类型为 rune
    for _, c := range expression {
        if c == ',' { // 跳过逗号
            continue
        }
        if c != ')' { // 不等于右括号直接入栈
            stk = append(stk, c)
            continue
        }
        // 统计 t 和 f 的个数
        t, f := 0, 0
        for stk[len(stk)-1] != '(' {
            c := stk[len(stk)-1]
            stk = stk[:len(stk)-1]
            if c == 't' {
                t++
            } else {
                f++
            }
        }
        stk = stk[:len(stk)-1] // 移除左括号
        op := stk[len(stk)-1]
        stk = stk[:len(stk)-1] // 移除操作符
        c := 't'
        switch op {
        case '!':
            // true 取反为 false
            if t == 1 {
                c = 'f'
            }
        case '&':
            // 与操作,f不为0个即为 false
            if f != 0 {
                c = 'f'
            }
        case '|':
            // 或操作,没有t 即为 false
            if t == 0 {
                c = 'f'
            }
        }
        stk = append(stk, c)
    }
    return stk[len(stk)-1] == 't'
}

switch 改写

func parseBoolExpr(expression string) bool {
    stk := []rune{}
    // range 遍历 c 的类型为 rune
    for _, c := range expression {
        if c == ',' { // 跳过逗号
            continue
        }
        if c != ')' { // 不等于右括号直接入栈
            stk = append(stk, c)
            continue
        }
        // 统计 t 和 f 的个数
        t, f := 0, 0
        for stk[len(stk)-1] != '(' {
            c := stk[len(stk)-1]
            stk = stk[:len(stk)-1]
            if c == 't' {
                t++
            } else {
                f++
            }
        }
        stk = stk[:len(stk)-1] // 移除左括号
        op := stk[len(stk)-1]
        stk = stk[:len(stk)-1] // 移除操作符
        c := 'f'
        if (op == '!' && f > 0) || (op == '&' && f == 0) || (op == '|' && t > 0) {
            c = 't'
        }
        stk = append(stk, c)
    }
    return stk[len(stk)-1] == 't'
}

复杂度分析

  • 时间复杂度:O(n)。
  • 空间复杂度:O(n)。

LeetCode题库地址