1106. 解析布尔表达式

Myth丶恋晨 2023-10-04 18:53 33阅读 0赞

给你一个以字符串形式表述的 布尔表达式（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 是以上述形式给出的有效表达式，表示一个布尔值。

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/parsing-a-boolean-expression  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：  
根据题意我们可以知道，一个运算符一定会跟随一对括号，比如 (t)(t)。  
所以我们可以直接判断 expression\[0\]，得到最外层的运算符，根据运算符处理内层的表达式。

如果不是运算符，肯定就是 t 或者 f 直接判断即可  
如果是 !!，里面要么就是单一的字符，要么就是一个新的表达式。再调用 parseBoolExpr 解析并取反即可。  
如果是 & 或者 |∣， 需要对里面每个表达式分别求解。通过括号匹配，拿到第一个 ( 匹配的 ) 里面的表达式，再通过 parseBoolExpr 计算出值。  
在计算 & 的时候，如果有一个值为 false，可以提前结束计算。同理，在计算 |∣ 时， 如果有一个值为 true，也可以提前结束计算。

作者：resara  
链接：https://leetcode.cn/problems/parsing-a-boolean-expression/solution/golang-fen-jie-by-resara/  
来源：力扣（LeetCode）  
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

func parseBoolExpr(expression string) bool {
    	start, end := 2, len(expression)-1
    	switch expression[0] {
    	case '!':
    		return Not(expression[start:end])
    	case '&':
    		return AndOr(expression[start:end], true)
    	case '|':
    		return AndOr(expression[start:end], false)
    	default:
    		return expression == "t"
    	}
    }
    
    // flag &: true |: false
    func AndOr(exp string, flag bool) bool {
    	pre, idx := 0, 0
    	for i := 0; i < len(exp); i++ {
    		if exp[i] == '(' {
    			if pre == 0 {
    				idx = i
    			}
    			pre++
    		} else if exp[i] == ')' {
    			pre--
    			if pre == 0 {
    				t := parseBoolExpr(exp[idx-1 : i+1])
    				if !t && flag {
    					return false
    				}
    				if t && !flag {
    					return true
    				}
    			}
    		} else {
                if pre <= 0 {
    				if exp[i] == 'f' && flag {
    					return false
    				}
    				if exp[i] == 't' && !flag {
    					return true
    				}
    			}
    		}
    	}
    	return flag
    }
    
    func Not(exp string) bool {
    	if len(exp) == 1 {
    		return !(exp == "t")
    	}
    	return !parseBoolExpr(exp)
    }
    
    作者：resara
    链接：https://leetcode.cn/problems/parsing-a-boolean-expression/solution/golang-fen-jie-by-resara/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

#### 解题思路 ####

动态创建函数