[Recursion and Dynamic Programming] interview questions #14

[btakeya]

Boolean Evaluation: Given a boolean expression consisting of the symbols 0 (false), 1 (true), & (AND), | (OR), and ^ (XOR), and a desired boolean result value result, implement a function to count the number of ways of parenthesizing the expression such that it evaluates to result. EXAMPLE

• countEval("1^0|0I1", false) -> 2
• countEval("0&0&0&1^1|0", true) -> 10 Hints: #148, #168, #197, #305, #327

[tgi01054]

유사한 문제

https://www.geeksforgeeks.org/boolean-parenthesization-problem-dp-37/

접근 방법

괄호 삽입하는 경우들

• 개요 아무리 복잡한 수식이라도 괄호는

  () OPERATOR ()

  형태으로 표현 될 수 있습니다.

• 괄호 삽입 전

  0 ^ 0 & 0 ^ 1 | 1

• 괄호 삽입 후

(0) ^ (0 & 0 ^ 1 | 1)
(0 ^ 0) & (0 ^ 1 | 1) 
(0 ^ 0 & 0) ^ (1 | 1) 
(0 ^ 0 & 0 ^ 1) | (1) 

AND 연산

• 예제

  (0 ^ 0) & (0 ^ 1 | 1)

• Left: (0 ^ 0)

• Right: (0 ^ 1 | 1)

  count(left & right, true ) = count(left, true ) * count(right, true)

  위의 수식에서 * 연산은 경우의 수 계산하시 위해서 합니다.

OR 연산

AND 경우와 비슷합니다.

XOR 연산

count(left ^ right, true ) = count(left, true ) * count(right, false)
                              + count(left, false ) * count(right, true)

Code

public class QuestionA {
    public static int count = 0;
    public static boolean stringToBool(String c) {
        return c.equals("1") ? true : false;
    }

    public static int countEval(String s, boolean result) {
        count++;
        if (s.length() == 0) return 0;
        if (s.length() == 1) return stringToBool(s) == result ? 1 : 0;

        int ways = 0;

        for (int i = 1; i < s.length(); i += 2) {
            char c = s.charAt(i);
            String left = s.substring(0, i);
            String right = s.substring(i + 1, s.length());
            int leftTrue = countEval(left, true);
            int leftFalse = countEval(left, false);
            int rightTrue = countEval(right, true);
            int rightFalse = countEval(right, false);
            int total = (leftTrue + leftFalse) * (rightTrue + rightFalse);

            int totalTrue = 0;
            if (c == '^') { // required: one true and one false
                totalTrue = leftTrue * rightFalse + leftFalse * rightTrue;
            } else if (c == '&') { // required: both true
                totalTrue = leftTrue * rightTrue;
            } else if (c == '|') { // required: anything but both false
                totalTrue = leftTrue * rightTrue + leftFalse * rightTrue + leftTrue * rightFalse;
            }

            int subWays = result ? totalTrue : total - totalTrue;
            ways += subWays;
        }

        return ways;
    }

    public static void main(String[] args) {
        String expression = "0^0|1&1^1|0|1";
        boolean result = true;

        System.out.println(countEval(expression, result));
        System.out.println(count);
    }

}

개선 할 수 있는 점

같은 수식이 여러 번 사용된다면 memorization 사용 할 수 있습니다. 이 경우가 정답 version 2 입니다.

책 정답 오역

p.489 아래 7번째

• old

  countEval(0 ^ 0 & 0 ^ 1 | 1 , true) = 
                                  =   count(0 ^ 0 & 0 ^ 1 | 1 괄호가 1번 문자에 있는 경우, true) 
                                    + count(0 ^ 0 & 0 ^ 1 | 1 괄호가 3번 문자에 있는 경우, true) 
                                    + count(0 ^ 0 & 0 ^ 1 | 1 괄호가 5번 문자에 있는 경우, true) 
                                    + count(0 ^ 0 & 0 ^ 1 | 1 괄호가 7번 문자에 있는 경우, true) 

• new

  countEval(0 ^ 0 & 0 ^ 1 | 1 , true) = 
                                  =   count((0) ^ (0 & 0 ^ 1 | 1), true) 
                                    + count((0 ^ 0) & (0 ^ 1 | 1), true) 
                                    + count((0 ^ 0 & 0) ^ (1 | 1), true) 
                                    + count((0 ^ 0 & 0 ^ 1) | (1), true) 

p.489 아래 2번째

• old

  (0 ^ 0) & (0 ^ 1)

• new

  (0 ^ 0) & (0 ^ 1 | 1)