부울 표현식이 있다고 가정하고 해당 표현식을 평가한 후 결과를 찾아야 합니다.
표현식은 다음 중 하나일 수 있습니다. -
-
"t", True로 평가됨;
-
"f", False로 평가됨,
-
"!(expression)", 내부 표현식의 논리적 NOT으로 평가,
-
"&(expr1,expr2,...)", 2개 이상의 내부 표현식의 논리적 AND로 평가,
-
"|(expr1,expr2,...)", 2개 이상의 내부 표현식의 논리적 OR로 평가,
따라서 입력이 "|(!(t),&(t,f,t))"와 같으면 출력이 fasle입니다. 이는 !(t)가 거짓이고 &(t,f, t)도 거짓이므로 모든 거짓 값의 OR은 거짓이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
solve()를 정의하면 e, i
가 필요합니다. -
e[i]가 "f"와 같으면 -
-
반환(거짓, i + 1)
-
-
그렇지 않으면 e[i]가 "t"와 같을 때 -
-
반환(True,i + 1)
-
연산 :=e[i], i :=i + 2
-
하나의 스택 정의
-
e[i]가 닫는 괄호가 아닌 동안 −
-
e[i]가 ","와 같으면 -
-
나는 :=나는 + 1
-
다음 부분은 무시하고 다음 반복으로 건너뜁니다.
-
-
res,i :=해결(e,i)
-
res를 스택에 푸시
-
-
op가 "&"와 같으면 -
-
스택의 모든 요소가 true이면 true를 반환하고 그렇지 않으면 false를 반환합니다. i + 1
-
-
그렇지 않으면 op가 " OR "과 같을 때 -
-
스택에서 적어도 하나의 요소가 true이면 true를 반환하고 그렇지 않으면 false를 반환합니다. i + 1
-
-
반환(스택[0]의 역수, i + 1)
-
기본 방법에서 다음을 수행하십시오 -
-
s,y :=해결(표현식, 0)
-
반환 s
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
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