Giả sử ta có một biểu thức boolean, ta cần 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 False;
- "!(expression)", đánh giá thành NOT logic của biểu thức bên trong;
- "&(expr1,expr2,...)", đánh giá thành AND logic của 2 hoặc nhiều biểu thức bên trong;
- "|(expr1,expr2,...)", đánh giá thành OR logic của 2 hoặc nhiều biểu thức bên trong;
Ví dụ, nếu đầu vào là "|(!(t),&(t,f,t))", thì đầu ra sẽ là false, vì !(t) là false, sau đó &(t,f,t) cũng là false, nên OR của tất cả giá trị false sẽ là false.
Để giải quyết, ta thực hiện các bước sau:
- Định nghĩa solve(), nhận e, i
- Nếu e[i] bằng "f", thì:
- Trả về (False, i + 1)
- Ngược lại khi e[i] bằng "t":
- Trả về (True, i + 1)
- op := e[i], i := i + 2
- Định nghĩa một stack
- Khi e[i] không phải dấu ngoặc đóng, thực hiện:
- Nếu e[i] bằng ",", thì:
- i := i + 1
- Bỏ qua phần tiếp theo, chuyển vòng lặp tiếp theo
- res, i := solve(e, i)
- Đẩy res vào stack
- Nếu e[i] bằng ",", thì:
- Nếu op bằng "&", thì:
- Trả về true khi tất cả phần tử trong stack là true, ngược lại false, i + 1
- Ngược lại khi op bằng "|":
- Trả về true khi ít nhất một phần tử trong stack là true, ngược lại false, i + 1
- Trả về (nghịch đảo của stack[0], i + 1)
- Từ phương thức chính:
- s, y := solve(expression, 0)
- Trả về s
Hãy xem 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