मान लीजिए कि हमारे पास एक स्ट्रिंग है जिसमें ऑपरेटरों "और" और "या" के साथ एक बूलियन अभिव्यक्ति है, इसका मूल्यांकन करें और परिणाम लौटाएं। यहां भावों में कोष्ठक हो सकते हैं, जिनका मूल्यांकन पहले किया जाना चाहिए।
इसलिए, यदि इनपुट s ="T और (F या T)" जैसा है, तो आउटपुट सही होगा
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
-
स्टैक :=एक नई सूची
-
t =रिक्त स्थान से विभाजित s के तत्वों की सूची
-
टी में प्रत्येक वी के लिए, करें
-
अगर v[0] "(" के समान है, तो
-
सही धक्का जब वी ["(" से अंत तक] की अनुक्रमणिका से "टी" के समान है, स्टैक में
-
-
अन्यथा जब ")" मिल जाए, तब
-
ct :=क्लोजिंग ब्रैकेट की संख्या ")" v
. में -
सही पुश करें जब v [इंडेक्स 0 से v - ct के आकार तक] स्टैक में "T" के समान हो
-
0 से ct-1 की श्रेणी में प्रत्येक मान के लिए, करें
-
दाएं:=स्टैक से पॉप
-
-
-
-
:=स्टैक से पॉप
-
बायां :=स्टैक से पॉप
-
ऑपरेशन करें (बाएं या दाएं) और स्टैक में पुश करें
-
अन्यथा जब v या तो "T" या "F" हो, तब
-
सही पुश करें जब v स्टैक में "T" के समान हो
-
-
अन्यथा,
-
op[v] को स्टैक में पुश करें
-
-
-
यदि तत्व स्टैक> 1 में गिना जाता है, तो
-
मैं के लिए 0 से लेकर स्टैक के आकार -1 तक, 2 से बढ़ाएँ, करें
-
स्टैक [i + 2]:=स्टैक [i + 1] (स्टैक [i], स्टैक [i + 2])
-
-
स्टैक का शीर्ष तत्व लौटाएं
-
-
स्टैक का निचला तत्व लौटाएं
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें:
उदाहरण
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
