Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

Python으로 부울 표현식 파싱하기: 재귀적 해석 방법 완벽 가이드

문제 개요

부울 표현식이 주어졌을 때, 해당 표현식을 평가한 결과를 구하는 문제입니다. 표현식은 다음과 같은 형태로 구성될 수 있습니다.

  • 't' — True로 평가됩니다.
  • 'f' — False로 평가됩니다.
  • '!(expression)' — 내부 표현식의 논리 NOT 결과를 반환합니다.
  • '&(expr1, expr2, ...)' — 2개 이상의 내부 표현식에 대한 논리 AND 결과를 반환합니다.
  • '|(expr1, expr2, ...)' — 2개 이상의 내부 표현식에 대한 논리 OR 결과를 반환합니다.

예를 들어 입력이 |(!(t),&(t,f,t))라면 출력은 False가 됩니다. 그 이유는 !(t)가 False이고, &(t,f,t) 역시 False이기 때문에, 모두 False인 값들의 OR 연산 결과는 False가 되기 때문입니다.

해결 접근 방법

이 문제는 재귀(Recursion)를 활용해 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  1. solve(e, i) 함수를 정의합니다. 여기서 e는 표현식 문자열, i는 현재 탐색 위치입니다.
  2. 현재 문자가 'f'라면 (False, i + 1)을 반환합니다.
  3. 현재 문자가 't'라면 (True, i + 1)을 반환합니다.
  4. 그 외의 경우 현재 문자는 연산자(!, &, |)이므로, op에 저장하고 인덱스를 2만큼 앞으로 이동합니다(연산자와 여는 괄호 건너뛰기).
  5. 결과를 저장할 스택(stack)을 하나 생성합니다.
  6. 닫는 괄호 )를 만날 때까지 반복하며 다음을 수행합니다.
    • 현재 문자가 쉼표 ,라면 인덱스를 1 증가시키고 건너뜁니다.
    • 그렇지 않으면 solve(e, i)를 재귀 호출하여 결과와 새 인덱스를 받아온 뒤, 결과를 스택에 push합니다.
  7. 반복이 끝나면 연산자에 따라 결과를 계산합니다.
    • op가 &라면 — 스택의 모든 요소가 True일 때만 True를 반환합니다(Python의 all() 활용).
    • op가 |라면 — 스택의 요소 중 하나라도 True이면 True를 반환합니다(Python의 any() 활용).
    • op가 !라면 — 스택의 첫 번째 요소를 반전(not)하여 반환합니다.
  8. 메인 메서드에서는 solve(expression, 0)을 호출하여 최종 결과를 반환합니다.

각 하위 표현식을 재귀적으로 평가하면서 인덱스를 함께 갱신하는 방식이므로, 중첩된 괄호 구조도 자연스럽게 처리할 수 있다는 점이 이 알고리즘의 핵심입니다.

구현 예제

아래 코드를 통해 더 자세히 이해해 보겠습니다.

class Solution(object):
    def parseBoolExpr(self, expression):
        s, y = self.solve(expression, 0)
        return s

    def solve(self, e, i):
        if e[i] == "f":
            return False, i + 1
        elif e[i] == "t":
            return True, i + 1
        op = e[i]
        i = i + 2
        stack = []
        while e[i] != ")":
            if e[i] == ",":
                i += 1
                continue
            res, i = self.solve(e, i)
            stack.append(res)
        if op == "&":
            return all(stack), i + 1
        elif op == "|":
            return any(stack), i + 1
        return not stack[0], i + 1

ob = Solution()
print(ob.parseBoolExpr("|(!(t),&(t,f,t))"))

입력

|(!(t),&(t,f,t))

출력

False

동작 과정 상세 분석

입력 |(!(t),&(t,f,t))가 어떻게 처리되는지 단계별로 살펴보겠습니다.

  1. 최상위 연산자는 |이므로, 괄호 안의 두 표현식을 차례로 평가합니다.
  2. 첫 번째 표현식 !(t): 연산자 !를 만나 내부의 t를 평가하면 True가 되고, NOT 연산으로 False가 됩니다.
  3. 두 번째 표현식 &(t,f,t): 연산자 &를 만나 세 값(True, False, True)을 평가합니다. 하나라도 False가 있으므로 AND 결과는 False입니다.
  4. 최종적으로 False OR False = False가 되어 출력은 False입니다.

시간 및 공간 복잡도

  • 시간 복잡도: O(n) — 각 문자를 최대 한 번씩만 방문합니다.
  • 공간 복잡도: O(n) — 재귀 호출 깊이와 스택 저장 공간이 표현식 길이에 비례합니다.

마무리

이 문제는 컴파일러의 파서(parser) 설계에서 자주 등장하는 재귀 하강 파싱(recursive descent parsing) 기법을 간단하게 체험할 수 있는 좋은 예제입니다. Python의 내장 함수인 all()과 any()를 활용하면 AND/OR 연산 로직을 매우 깔끔하게 구현할 수 있습니다. 중첩된 표현식을 다루는 유사한 문제(수식 계산기, JSON 파서 등)에도 동일한 접근 방식을 응용할 수 있으니 꼭 기억해 두시기 바랍니다.