1896. Minimum Cost to Change the Final Value of Expression Hard

1/**
2 * [1896] Minimum Cost to Change the Final Value of Expression
3 *
4 * You are given a valid boolean expression as a string expression consisting of the characters '1','0','&' (bitwise AND operator),'|' (bitwise OR operator),'(', and ')'.
5 * 
6 * 	For example, "()1|1" and "(1)&()" are not valid while "1", "(((1))|(0))", and "1|(0&(1))" are valid expressions.
7 * 
8 * Return the minimum cost to change the final value of the expression.
9 * 
10 * 	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.
11 * 
12 * 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:
13 * 
14 * 	Turn a '1' into a '0'.
15 * 	Turn a '0' into a '1'.
16 * 	Turn a '&' into a '|'.
17 * 	Turn a '|' into a '&'.
18 * 
19 * Note: '&' does not take precedence over '|' in the order of calculation. Evaluate parentheses first, then in left-to-right order.
20 *  
21 * Example 1:
22 * 
23 * Input: expression = "1&(0|1)"
24 * Output: 1
25 * Explanation: We can turn "1&amp;(0<u>|</u>1)" into "1&amp;(0<u>&amp;</u>1)" by changing the '|' to a '&amp;' using 1 operation.
26 * The new expression evaluates to 0. 
27 * 
28 * Example 2:
29 * 
30 * Input: expression = "(0&amp;0)&amp;(0&amp;0&amp;0)"
31 * Output: 3
32 * Explanation: We can turn "(0<u>&amp;0</u>)<u>&amp;</u>(0&amp;0&amp;0)" into "(0<u>|1</u>)<u>|</u>(0&amp;0&amp;0)" using 3 operations.
33 * The new expression evaluates to 1.
34 * 
35 * Example 3:
36 * 
37 * Input: expression = "(0|(1|0&amp;1))"
38 * Output: 1
39 * Explanation: We can turn "(0|(<u>1</u>|0&amp;1))" into "(0|(<u>0</u>|0&amp;1))" using 1 operation.
40 * The new expression evaluates to 0.
41 *  
42 * Constraints:
43 * 
44 * 	1 <= expression.length <= 10^5
45 * 	expression only contains '1','0','&amp;','|','(', and ')'
46 * 	All parentheses are properly matched.
47 * 	There will be no empty parentheses (i.e: "()" is not a substring of expression).
48 * 
49 */
50pub struct Solution {}
51
52// problem: https://leetcode.com/problems/minimum-cost-to-change-the-final-value-of-expression/
53// discuss: https://leetcode.com/problems/minimum-cost-to-change-the-final-value-of-expression/discuss/?currentPage=1&orderBy=most_votes&query=
54
55// submission codes start here
56
57impl Solution {
58    pub fn min_operations_to_flip(expression: String) -> i32 {
59        0
60    }
61}
62
63// submission codes end
64
65#[cfg(test)]
66mod tests {
67    use super::*;
68
69    #[test]
70    fn test_1896() {
71    }
72}
73