สมมติว่าเรามีนิพจน์บูลีน เราต้องหาผลลัพธ์หลังจากประเมินนิพจน์นั้น
นิพจน์สามารถเป็นได้ทั้ง −
-
"t" ประเมินเป็น True;
-
"f" ประเมินเป็นเท็จ
-
"!(นิพจน์)" ประเมินตรรกะไม่ใช่ของนิพจน์ภายใน
-
"&(expr1,expr2,...)" ประเมินตรรกะ AND ของนิพจน์ภายใน 2 ตัวขึ้นไป
-
"|(expr1,expr2,...)" ประเมินเป็นตรรกะ OR ของนิพจน์ภายใน 2 ตัวขึ้นไป
ดังนั้น หากอินพุตเป็นแบบ "|(!(t),&(t,f,t))" ผลลัพธ์จะเป็นแบบ fasle นั่นเป็นเพราะ !(t) เป็นเท็จ ดังนั้น &(t,f, t) เป็นเท็จเช่นกัน ดังนั้น OR ของค่าเท็จทั้งหมดจะเป็นเท็จ
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนด Solve() นี้จะใช้เวลา e, i
-
ถ้า e[i] เหมือนกับ "f" แล้ว −
-
ผลตอบแทน (เท็จ ผม + 1)
-
-
มิฉะนั้นเมื่อ e[i] เหมือนกับ "t" −
-
กลับ (จริงฉัน + 1)
-
op :=e[i], i :=i + 2
-
กำหนดหนึ่งกอง
-
ในขณะที่ e[i] ไม่ได้ปิดวงเล็บ ให้ทำ -
-
ถ้า e[i] เหมือนกับ "," แล้ว −
-
ผม :=ผม + 1
-
ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป
-
-
res,i :=แก้ (e, i)
-
ดัน res ลงใน stack
-
-
ถ้า op เหมือนกับ "&" แล้ว −
-
คืนค่า จริง เมื่อองค์ประกอบทั้งหมดเป็นจริงในสแต็ก มิฉะนั้น เท็จ i + 1
-
-
มิฉะนั้นเมื่อ op เหมือนกับ " OR " −
-
คืนค่า จริง เมื่อองค์ประกอบอย่างน้อยหนึ่งรายการเป็นจริงในสแต็ก มิฉะนั้น เท็จ i + 1
-
-
กลับ (ผกผันของ stack[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
