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 ).
Return the minimum cost to change the final value of expression.
The cost of changing the final value of an expression is the number of operations performed on the expression. The allowed operations are:
- Turn a
1into a0. - Turn a
0into a1. - Turn a
&into a|. - Turn a
|into a&.
Note: & does not take precedence over | in the order of calculation. Evaluate parentheses first, then evaluate operations in left-to-right order.
Example 1
Input
expression = "1&(0|1)"Output
1Changing the
| in 1&(0|1) to & makes the expression evaluate to 0 using 1 operation.Example 2
Input
expression = "(0&0)&(0&0&0)"Output
3Changing
(0&0)&(0&0&0) into (0|1)|(0&0&0) uses 3 operations and makes the expression evaluate to 1.Constraints
- 1 <= expression.length <= 10^5
- 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).