Parsing A Boolean Expression ใน Python: ประเมินนิพจน์บูลีนแบบ Toi Đệ Quy

ได้นิพจน์บูลีนในรูปแบบสตริง ประเมินค่า True/False รูปแบบ: "t" (True), "f" (False), "!(expr)" (NOT), "&(expr1,expr2,...)" (AND), "|(expr1,expr2,...)" (OR)

ตัวอย่าง

"|(!(t),&(t,f,t))" → !(t) = False, &(t,f,t) = False, |(False,False) = False

ขั้นตอนการแก้ปัญหา (Recursive Descent Parser)

1. ฟังก์ชัน solve(e, i) ประเมินนิพจน์ตั้งแต่ดัชนี i คืน (value, next_index)
2. Base Case: 't' → (True, i+1), 'f' → (False, i+1)
3. Operator: อ่าน op (!, &, |) ข้าม '('
4. วนอ่าน Sub-expressions (ขั่นด้วย ',') จนเจอ ')' เรียก solve ซ้อน เก็บผลใน Stack
5. ประเมินตาม Operator: & = all(), | = any(), ! = not stack[0]

การติดตั้งใน Python

class Solution:
    def parseBoolExpr(self, expression):
        val, _ = self._parse(expression, 0)
        return val

    def _parse(self, e, i):
        if e[i] == 't':
            return True, i + 1
        if e[i] == 'f':
            return False, i + 1
        op = e[i]
        i += 2  # skip op and '('
        stack = []
        while e[i] != ')':
            if e[i] == ',':
                i += 1
                continue
            val, i = self._parse(e, i)
            stack.append(val)
        if op == '&':
            return all(stack), i + 1
        if op == '|':
            return any(stack), i + 1
        return not stack[0], i + 1  # op == '!'

ob = Solution()
print(ob.parseBoolExpr("|(!(t),&(t,f,t))"))  # False

อินพุต / เอาต์พุต

Input: "|(!(t),&(t,f,t))"
Output: False