原文链接: https://leetcode-cn.com/problems/minimum-cost-to-change-the-final-value-of-expression

英文原文

You are given a valid boolean expression as a string expression consisting of the characters '1','0','&' (bitwise AND operator),'|' (bitwise OR operator),'(', and ')'.

• For example, "()1|1" and "(1)&()" are not valid while "1", "(((1))|(0))", and "1|(0&(1))" are valid expressions.

Return the minimum cost to change the final value of the expression.

• For example, if expression = "1|1|(0&0)&1", its value is 1|1|(0&0)&1 = 1|1|0&1 = 1|0&1 = 1&1 = 1. We want to apply operations so that the new expression evaluates to 0.

The cost of changing the final value of an expression is the number of operations performed on the expression. The types of operations are described as follows:

• Turn a '1' into a '0'.
• Turn a '0' into a '1'.
• Turn a '&' into a '|'.
• Turn a '|' into a '&'.

Note: '&' does not take precedence over '|' in the order of calculation. Evaluate parentheses first, then in left-to-right order.

 

Example 1:

Input: expression = "1&(0|1)"
Output: 1
Explanation: We can turn "1&(0|1)" into "1&(0&1)" by changing the '|' to a '&' using 1 operation.
The new expression evaluates to 0. 

Example 2:

Input: expression = "(0&0)&(0&0&0)"
Output: 3
Explanation: We can turn "(0&0)&(0&0&0)" into "(0|1)|(0&0&0)" using 3 operations.
The new expression evaluates to 1.

Example 3:

Input: expression = "(0|(1|0&1))"
Output: 1
Explanation: We can turn "(0|(1|0&1))" into "(0|(0|0&1))" using 1 operation.
The new expression evaluates to 0.

 

Constraints:

• 1 <= expression.length <= 105
• expression only contains '1','0','&','|','(', and ')'
• All parentheses are properly matched.
• There will be no empty parentheses (i.e: "()" is not a substring of expression).

中文题目

给你一个 有效的 布尔表达式，用字符串 expression 表示。这个字符串包含字符 '1'，'0'，'&'（按位 与 运算），'|'（按位 或 运算），'(' 和 ')' 。

• 比方说，"()1|1" 和 "(1)&()" 不是有效 布尔表达式。而 "1"， "(((1))|(0))" 和 "1|(0&(1))" 是 有效 布尔表达式。

你的目标是将布尔表达式的 值 反转 （也就是将 0 变为 1 ，或者将 1 变为 0），请你返回达成目标需要的 最少操作 次数。

• 比方说，如果表达式 expression = "1|1|(0&0)&1" ，它的 值 为 1|1|(0&0)&1 = 1|1|0&1 = 1|0&1 = 1&1 = 1 。我们想要执行操作将 新的 表达式的值变成 0 。

可执行的 操作 如下：

• 将一个 '1' 变成一个 '0' 。
• 将一个 '0' 变成一个 '1' 。
• 将一个 '&' 变成一个 '|' 。
• 将一个 '|' 变成一个 '&' 。

注意：'&' 的 运算优先级 与 '|' 相同 。计算表达式时，括号优先级 最高 ，然后按照 从左到右 的顺序运算。

 

示例 1：

输入：expression = "1&(0|1)"
输出：1
解释：我们可以将 "1&(0|1)" 变成 "1&(0&1)" ，执行的操作为将一个 '|' 变成一个 '&' ，执行了 1 次操作。
新表达式的值为 0 。

示例 2：

输入：expression = "(0&0)&(0&0&0)"
输出：3
解释：我们可以将 "(0&0)&(0&0&0)" 变成 "(0|1)|(0&0&0)" ，执行了 3 次操作。
新表达式的值为 1 。

示例 3：

输入：expression = "(0|(1|0&1))"
输出：1
解释：我们可以将 "(0|(1|0&1))" 变成 "(0|(0|0&1))" ，执行了 1 次操作。
新表达式的值为 0 。

 

提示：

• 1 <= expression.length <= 105
• expression 只包含 '1'，'0'，'&'，'|'，'(' 和 ')'
• 所有括号都有与之匹配的对应括号。
• 不会有空的括号（也就是说 "()" 不是 expression 的子字符串）。

通过代码

高赞题解

一道经典的表达式处理问题，我们使用操作符栈+操作数栈的经典双栈方式来进行模拟。

注意这里的“操作数”实际上是一个二元的状态$(p, q)$，其中$p$代表将当前“操作数”对应的范围变为$0$所需的最小操作次数，$q$代表将当前的“操作数”对应的范围变为$1$所需的最小操作次数。

显然，单个的$0$对应于状态$(0,1)$，而单个的$1$对应于状态$(1,0)$。

本题中，除括号外所有运算符优先级相同，需要从左到右进行运算，因此我们每得到一个新的“操作数”（这里既包括由单个的$0$或$1$带来的“操作数”，也包括)导致的出栈情形——对于上一层来说，这一层带来了一个新的“操作数”），就应当在上一个操作符不为(时将当前的“操作数”与上一个“操作数”进行一次“运算”，合并为一个新的“操作数”。

下面我们需要考虑如何实现“运算”。

假设待合并的两个状态为$(p_1,q_1)$和$(p_2,q_2)$。

如果当前操作符为&，则：

• 我们如果要得到$0$，只需要有一边为$0$，代价为$\min(p_1,p_2)$。

• 我们如果要得到$1$，需要左右两边同时为$1$，代价为$q_1+q_2$；或者将操作符变为|，同时只需要左右有一边为$1$，代价为$\min(q_1,q_2)+1$。

如果当前操作符为|，则：

• 我们如果要得到$0$，需要左右两边同时为$0$，代价为$p_1+p_2$；或者将操作符变为&，同时只需要左右有一边为$0$，代价为$\min(p_1,p_2)+1$。
• 我们如果要得到$1$，只需要有一边为$1$，代价为$\min(q_1,q_2)$。

这样我们就实现了操作数之间的运算。

所有操作执行完毕后，我们的操作数栈将只包含一个元素。这个元素必定包含一个零值（对应于表达式原本的值）和一个非零值。而这个非零值就是我们要寻找的答案。

复杂度分析

• 时间复杂度$\mathcal{O}(|S|)$。
• 空间复杂度$\mathcal{O}(|S|)$。

参考代码（Python 3）

class Solution:
    def minOperationsToFlip(self, expression: str) -> int:
        states = []
        ops = []
                
        for c in expression:
            if c in '01)':
                if c == '0':
                    states.append((0, 1))
                elif c == '1':
                    states.append((1, 0))
                else:
                    assert(ops[-1] == '(')
                    ops.pop()
                    
                if len(ops) > 0 and ops[-1] != '(':
                    op = ops.pop()
                    p2, q2 = states.pop()
                    p1, q1 = states.pop()
                    if op == '&':
                        states.append((min(p1, p2), min(q1 + q2, 1 + min(q1, q2))))
                    else:
                        states.append((min(p1 + p2, 1 + min(p1, p2)), min(q1, q2)))
            else:
                ops.append(c)
        
        return max(states[-1])

统计信息

通过次数	提交次数	AC比率
875	1721	50.8%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言