Giả sử chúng ta có một biểu thức boolean, chúng ta phải tìm kết quả sau khi đánh giá biểu thức đó.
Một biểu thức có thể là -
-
"t", đánh giá thành True;
-
"f", đánh giá thành Sai;
-
"! (biểu thức)", đánh giá theo logic KHÔNG của biểu thức bên trong;
-
"&(expr1, expr2, ...)", đánh giá theo logic AND của 2 hoặc nhiều biểu thức bên trong;
-
"| (expr1, expr2, ...)", đánh giá theo lôgic HOẶC của 2 hoặc nhiều biểu thức bên trong;
Vì vậy, nếu đầu vào giống như "| (! (T), &(t, f, t))", thì đầu ra sẽ là Fasle, điều này là do! (T) là false, khi đó &(t, f, t) cũng sai, vì vậy OR của tất cả các giá trị sai sẽ là sai.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
định nghĩa giải quyết (), điều này sẽ mất e, i
-
nếu e [i] giống với "f" thì -
-
return (Sai, i + 1)
-
-
Ngược lại khi e [i] giống với "t" -
-
return (Đúng, i + 1)
-
op:=e [i], i:=i + 2
-
Xác định một ngăn xếp
-
trong khi e [i] không đóng ngoặc, hãy làm -
-
nếu e [i] giống với "," thì -
-
i:=i + 1
-
Bỏ qua phần sau, chuyển sang phần tiếp theo
-
-
res, i:=giải quyết (e, i)
-
đẩy res vào ngăn xếp
-
-
nếu op giống như "&", thì -
-
trả về true khi tất cả các phần tử đều đúng trong ngăn xếp, ngược lại là false, i + 1
-
-
ngược lại khi op giống như "OR" -
-
trả về true khi ít nhất một phần tử là true trong ngăn xếp, nếu không, false, i + 1
-
-
return (nghịch đảo của ngăn xếp [0], i + 1)
-
Từ phương thức chính, thực hiện như sau -
-
s, y:=giải quyết (biểu thức, 0)
-
trả lại s
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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))")) Đầu vào
"|(!(t),&(t,f,t))"
Đầu ra
False