1896. Minimum Cost to Change the Final Value of Expression
https://leetcode.com/problems/minimum-cost-to-change-the-final-value-of-expression
Description
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 is1|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 to0
.
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 ofexpression
).
ac
Last updated
Was this helpful?