Giả sử chúng ta có một chuỗi s chứa một biểu thức boolean với các toán tử "và" và "hoặc", hãy đánh giá nó và trả về kết quả. Ở đây, các biểu thức có thể có dấu ngoặc đơn, nên được đánh giá đầu tiên.
Vì vậy, nếu đầu vào giống như s ="T và (F hoặc T)", thì đầu ra sẽ là True
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:
-
stack:=một danh sách mới
-
t =danh sách các phần tử của s được phân chia bởi dấu cách trống
-
đối với mỗi v trong t, làm
-
nếu v [0] giống với "(", thì
-
đẩy true khi v [từ chỉ mục của "(" đến end] giống như "T", vào ngăn xếp
-
-
ngược lại khi ")" được tìm thấy thì
-
ct:=số dấu ngoặc đóng ")" trong v
-
đẩy true khi v [từ chỉ số 0 đến kích thước của v - ct] giống như "T" vào ngăn xếp
-
đối với mỗi giá trị trong phạm vi từ 0 đến ct-1, hãy thực hiện
-
right:=pop from stack
-
-
-
-
:=pop from stack
-
left:=pop from stack
-
thực hiện thao tác (trái o phải) và đẩy vào ngăn xếp
-
ngược lại khi v là "T" hoặc "F" thì
-
đẩy true khi v giống "T" vào ngăn xếp
-
-
nếu không,
-
đẩy op [v] vào ngăn xếp
-
-
-
nếu số phần tử trong ngăn xếp> 1, thì
-
đối với tôi trong phạm vi 0 đến kích thước của ngăn xếp - 1, tăng thêm 2, thực hiện
-
stack [i + 2]:=stack [i + 1] (stack [i], stack [i + 2])
-
-
trả về phần tử trên cùng của ngăn xếp
-
-
trả về phần tử dưới cùng của ngăn xếp
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:
Ví dụ
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)) Đầu vào
"T and (F or T)"
Đầu ra
True