8.14 불린 값 계산

문제

0(false), 1(True), &(and), |(or), ^(xor)로 구성된 불린 표현식과 원하는 계산 결과가 주어졌을때 , 표현식에 괄호를 적절하게 추가하여 그 값이 원하는 결과값과 같게 만들 수 있는 모든 경우의 갯수를 출력하는 메서드를 구현하라.

 

접근법

1. 무식한 방법

표현식이 0^0&0^1|1이고 원하는 결과가 true인 경우를 생각해보자, countEval( 0^0&0^1|1, true)를 어떻게 쪼갤 수 있을까?

countEval( 0^0&0^1|1, true) = countEval( 0^0&0^1|1 괄호가 1번 위치에 있을때 , true) + 

                                                 countEval( 0^0&0^1|1 괄호가 3번 위치에 있을때 , true) + 

                                                 countEval( 0^0&0^1|1 괄호가 5번 위치에 있을때 , true) + 

                                                 countEval( 0^0&0^1|1 괄호가 7번 위치에 있을때 , true) 

이런식으로 쪼개 지겠죠

그러면 만약 괄호가 3번 위치에 있다고 한다면 (0^0) & (0^1|1)  이렇게 쪼개질 것이고

(0^0) 를 왼쪽이라고 , (0^1|1)를 오른쪽이라고 하면 

&연산에서는 왼쪽과 오른쪽이 모두 true여야만 true가 될 것이다.

그러면 countEval( 왼쪽 & 오른쪽 , true)  = countEval( 왼쪽  , true )  + countEval( 오른쪽 , true ) 일 것이다.

이런식으로 재귀적으로 확인해 가면서 갯수를 샐 수 있을 것이다.

 

추가적으로 메모이제이션을 진행하면 반복되는 재귀를 막을 수 있다.

def countEval(s, result , memo):
    if len(s) == 0 :
        return 0
    if len(s) == 1 :
        return 1 if toBool(s) == result else 0
    if (s,result) in memo :
        return memo[(s,result)]

    way = 0
    for i in range(1, range(len(s)), 2):
        c = s[i]
        left = s[:i]
        right = s[i+1:]

        leftTrue = countEval(left, True)
        leftFalse = coutEval(left, False)
        rightTrue = coutEval(right, True)
        rightFalse = coutEval(right, False)
        total = (leftTrue+ leftFalse) + (rightTrue + rightFalse)

        totalTrue = 0
        if c == "^":
            totalTrue = (leftTrue * rightFalse) + (leftFalse * rightTrue)
        elif c == "&":
            totalTrue = (leftTrue * rightTrue)
        elif c =="|":
            totalTrue = (leftTrue * rightTrue) + (leftTrue * rightFalse) + (leftFalse & rightTrue)
        subways = totalTrue if result else total - totalTrue
        way += subways
    memo[(s, result)] = way
    return way