"and" 및 "or" 연산자가 있는 부울 표현식을 포함하는 문자열 s가 있다고 가정하고 이를 평가하고 결과를 반환합니다. 여기서 표현식에는 먼저 평가되어야 하는 괄호가 있을 수 있습니다.
따라서 입력이 s ="T 및 (F 또는 T)"와 같으면 출력은 True
가 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다.
-
스택 :=새 목록
-
t =공백으로 분할된 s의 요소 목록
-
t의 각 v에 대해 수행
-
v[0]이 "("과 같으면
-
v["("의 인덱스에서 끝까지]가 "T"와 같을 때 true를 스택으로 푸시합니다.
-
-
그렇지 않으면 ")"가 발견되면
-
ct :=v에서 닫는 괄호 ")"의 수
-
v[인덱스 0에서 v - ct의 크기까지]가 스택에 "T"와 같을 때 true를 푸시합니다.
-
0에서 ct-1 범위의 각 값에 대해 수행
-
오른쪽 :=스택에서 팝
-
-
-
-
:=스택에서 팝
-
왼쪽 :=스택에서 팝
-
작업을 수행하고(왼쪽에서 오른쪽으로) 스택에 푸시합니다.
-
그렇지 않으면 v가 "T" 또는 "F"인 경우
-
v가 스택에 "T"와 같을 때 true를 푸시합니다.
-
-
그렇지 않으면
-
스택에 op[v] 푸시
-
-
-
스택의 요소 수가> 1이면
-
범위 0에서 스택 크기 - 1에 있는 i의 경우 2만큼 증가, 수행
-
스택[i + 2] :=스택[i + 1](스택[i], 스택[i + 2])
-
-
스택의 맨 위 요소 반환
-
-
스택의 맨 아래 요소 반환
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
예
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