โปรแกรมประเมินนิพจน์บูลีนจากสตริงใน Python

สมมติว่าเรามีสตริง s ที่เป็นนิพจน์บูลีน มีออเปอเรเตอร์ "and" และ "or" อาจมีวงเล็บ ต้องประเมินค่าและคืนผลลัพธ์ วงเล็บต้องประเมินก่อน

ตัวอย่าง

อินพุต: s = "T and (F or T)"

เอาต์พุต: True

ขั้นตอนการแก้ปัญหา

ใช้สแต็กและการประมวลผลทีละโทเคน (token):

1. แยกสตริงด้วยช่องว่างเป็นรายการโทเคน t
2. กำหนด dictionary op สำหรับ lambda ของ "and" และ "or"
3. วนลูปผ่านแต่ละโทเคน v:
   • ถ้าเริ่มด้วย "(" ให้ push ค่าความจริงของส่วนที่เหลือ (หลัง "(")
   • ถ้ามี ")" ให้นับจำนวน ")" แล้ว push ค่าความจริงของส่วนก่อน ")" แล้ว pop สามค่า (right, operator, left) คำนวณและ push ผลลัพธ์ ทำซ้ำตามจำนวน ")"
   • ถ้าเป็น "T" หรือ "F" ให้ push ค่าบูลีน
   • มิฉะนั้นเป็นออเปอเรเตอร์ ให้ push function จาก op
4. หลังวนลูป ถ้าสแต็กยังมีหลายค่า ให้ประเมินจากซ้ายไปขวา (left-associative)
5. คืนค่าบนสุดของสแต็ก

การนำไปใช้ใน Python

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