สมมติว่าเรามีสตริงที่มีนิพจน์บูลีนที่มีตัวดำเนินการ "และ" และ "หรือ" ประเมินและส่งคืนผลลัพธ์ ในที่นี้ นิพจน์อาจมีวงเล็บ ซึ่งควรประเมินก่อน
ดังนั้น หากอินพุตเป็น s ="T และ (F หรือ T)" ผลลัพธ์จะเป็น True
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
-
stack :=รายการใหม่
-
t =รายการองค์ประกอบของ s แบ่งตามช่องว่าง
-
สำหรับแต่ละ v ใน t ทำ
-
ถ้า v[0] เหมือนกับ "(" แล้ว
-
ดันจริงเมื่อ v[จากดัชนีของ "(" ถึง end] เหมือนกับ "T" ลงในสแต็ก
-
-
มิฉะนั้นเมื่อพบ ")" แล้ว
-
ct :=จำนวนวงเล็บปิด ")" ใน v
-
ดันจริงเมื่อ v[จากดัชนี 0 ถึงขนาดของ v - ct] เท่ากับ "T" ลงในสแต็ก
-
สำหรับแต่ละค่าในช่วง 0 ถึง ct-1 ทำ
-
ขวา :=ป๊อปจากสแต็ก
-
-
-
-
:=ป๊อปจากสแต็ก
-
ซ้าย :=ป๊อปจากสแต็ก
-
ดำเนินการ (ซ้าย o ขวา) และดันเข้าไปในกอง
-
มิฉะนั้นเมื่อ v เป็น "T" หรือ "F" ดังนั้น
-
กดจริงเมื่อ v เหมือนกับ "T" ลงในสแต็ก
-
-
มิฉะนั้น
-
ดัน op[v] ลงใน stack
-
-
-
หากองค์ประกอบนับใน stack> 1 แล้ว
-
สำหรับฉันในช่วง 0 ถึงขนาดของสแต็ก - 1 เพิ่มขึ้น 2 ทำ
-
stack[i + 2] :=stack[i + 1](stack[i], stack[i + 2])
-
-
ส่งคืนองค์ประกอบด้านบนของ stack
-
-
ส่งคืนองค์ประกอบด้านล่างของ stack
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:
ตัวอย่าง
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
