문제 정의
문자열 s에 "and"와 "or" 연산자로 구성된 부울 표현식이 담겨 있다고 가정해 보겠습니다. 이 표현식을 평가하여 그 결과를 반환하는 것이 목표입니다. 단, 표현식에는 괄호가 포함될 수 있으며, 괄호 안의 식은 항상 가장 먼저 계산해야 한다는 점에 유의해야 합니다.
예를 들어 입력이 s = "T and (F or T)"라면, 괄호 안의 "F or T"가 먼저 참으로 평가되고, 이어서 "T and True"가 계산되어 최종 출력은 True가 됩니다.
해결 전략: 스택 활용
이 문제는 스택(stack) 자료구조를 활용하면 깔끔하게 해결할 수 있습니다. 연산자는 미리 람다 함수 형태로 정의해 두고, 피연산자와 연산자를 토큰 단위로 스택에 쌓은 뒤 닫는 괄호를 만날 때마다 값을 꺼내 연산을 수행하는 방식입니다.
구체적인 알고리즘은 다음과 같습니다.
- 스택을 새 리스트로 초기화하고, 입력 문자열 s를 공백 기준으로 분리한 토큰 리스트를 준비합니다.
- 각 토큰 v에 대해 아래 작업을 반복합니다.
- v가 여는 괄호 "("로 시작하는 경우: 괄호를 제거한 나머지 부분이 "T"인지 검사한 부울 결과를 스택에 push합니다.
- v에 닫는 괄호 ")"가 포함된 경우: 닫는 괄호의 개수를 ct라 할 때, 괄호를 제외한 부분이 "T"인지 검사한 결과를 스택에 push합니다. 이후 ct번 반복하면서 스택에서 오른쪽 피연산자(right), 연산자(o), 왼쪽 피연산자(left)를 차례로 pop하고, 연산 결과(left o right)를 다시 스택에 push합니다.
- v가 "T" 또는 "F"인 경우: v == "T"의 평가 결과를 스택에 push합니다.
- 그 외의 경우(연산자): 미리 정의한 op 딕셔너리에서 해당 연산자 함수를 꺼내 스택에 push합니다.
- 모든 토큰 처리 후 스택에 요소가 2개 이상 남아 있으면, 왼쪽부터 두 칸씩 건너뛰며 인접한 세 요소(피연산자, 연산자, 피연산자)에 연산을 적용해 스택을 하나의 값으로 접습니다(fold).
- 마지막으로 스택에 남은 최상단 요소를 반환합니다.
예제 코드
아래 구현을 통해 동작 방식을 더 잘 이해할 수 있습니다.
class Solution:
def solve(self, s):
stack = []
op = {
"or": lambda x, y: x or y,
"and": lambda x, y: x and y,
}
for v in s.split():
if v[0] == "(":
stack.append(v[v.count("(") :] == "T")
elif v.count(")") > 0:
ct = v.count(")")
stack.append(v[:-ct] == "T")
for _ in range(ct):
right = stack.pop()
o = stack.pop()
left = stack.pop()
stack.append(o(left, right))
elif v in ["T", "F"]:
stack.append(v == "T")
else:
stack.append(op[v])
if len(stack) > 1:
for i in range(0, len(stack) - 1, 2):
stack[i + 2] = stack[i + 1](stack[i], stack[i + 2])
return stack[-1]
return stack[0]
ob = Solution()
s = "T and (F or T)"
print(ob.solve(s))입력
"T and (F or T)"
출력
True
정리
이 접근법의 핵심은 연산자를 일급 객체(람다 함수)로 취급해 스택에 함께 저장한다는 점입니다. 덕분에 닫는 괄호를 만나는 시점에 즉시 하위 표현식을 평가할 수 있고, 복잡한 재귀 호출 없이도 중첩된 괄호 표현식을 효율적으로 처리할 수 있습니다. 공백으로 구분된 간단한 부울 표현식 파서가 필요하다면 이 패턴을 그대로 응용해 보시기 바랍니다.