leetcode 1106. 解析布尔表达式

发表于 2019-07-17

| 0

| 阅读次数:

给你一个以字符串形式表述的 布尔表达式（boolean） expression，返回该式的运算结果。
有效的表达式需遵循以下约定：

1. “t”，运算结果为 True
2. “f”，运算结果为 False
3. “!(expr)”，运算过程为对内部表达式 expr 进行逻辑 非的运算（NOT）
4. “&(expr1,expr2,…)”，运算过程为对 2 个或以上内部表达式 expr1, expr2, … 进行逻辑 与的运算（AND）
5. “|(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

两个栈，一个存操作 stackOp，一个存值 stackVal，遇到字符 ) 时计算相应表达式的值（以(开始的表达式），加入栈 stackVal

示例代码(go)

func parseBoolExpr(expression string) bool {
    stackOp := make([]byte, 0)
    stackVal := make([]byte, 0)
    n := len(expression)
    for i := 0; i < n; i++ {
        if expression[i] == '&' || expression[i] == '|' || expression[i] == '!' {
            stackOp = append(stackOp, expression[i])
        }
        if expression[i] == '(' || expression[i] == 't' || expression[i] == 'f' {
            stackVal = append(stackVal, expression[i])
        }
        if expression[i] == ')' {
            haveT, haveF := false, false
            op := stackOp[len(stackOp)-1]
            stackOp = stackOp[:len(stackOp)-1]
            for stackVal[len(stackVal)-1] != '(' {
                if stackVal[len(stackVal)-1] == 't' {
                    haveT = true
                } else {
                    haveF = true
                }
                stackVal = stackVal[:len(stackVal)-1]
            }
            stackVal = stackVal[:len(stackVal)-1]
            if op == '!' {
                if haveT {
                    stackVal = append(stackVal, 'f')
                } else {
                    stackVal = append(stackVal, 't')
                }
            }
            if op == '&' {
                if haveF {
                    stackVal = append(stackVal, 'f')
                } else {
                    stackVal = append(stackVal, 't')
                }
            }
            if op == '|' {
                if haveT {
                    stackVal = append(stackVal, 't')
                } else {
                    stackVal = append(stackVal, 'f')
                }
            }
        }
    }
    if stackVal[0] == 't' {
        return true
    }
    return false
}