Given a string that contains only the following => ‘{‘, ‘}’, ‘(‘, ‘)’, ‘[’, ‘]’. At some places there is ‘X’ in place of any bracket. Determine whether by replacing all ‘X’s with appropriate bracket, is it possible to make a valid bracket sequence.
Examples:
Input : S = "{(X[X])}"
Output : Balanced
Input : S = "[{X}(X)]"
Output : Not balanced
I tried to work it out like this, and it works for examples above. But it doesn't work for all examples eg. (it should be balanced but it says it's not)
Input: S = "([X}])"
Output: Not balanced
I tried to work it out but i can't find a solution. Please help.
class Stack:
def __init__(self):
self.data = []
def insert(self, x):
self.data.append(x)
def empty(self):
return len(self.data) == 0
def remove(self):
if self.empty():
raise ValueError('Stack is empty.')
self.data.pop()
def top_element(self):
if self.empty():
raise ValueError('Stack is empty.')
return self.data[-1]
def is_matching(a, b):
if a == "(" and b == ")":
return True
elif a == "[" and b == "]":
return True
elif a == "{" and b == "}":
return True
elif a == "X":
return True
return False
def is_balanced(expression,elements=Stack(),ind=0):
if ind == len(expression):
return elements.empty()
pre_brackets = "([{"
post_brackets = ")]}"
char = expression[ind]
if char in pre_brackets:
elements.insert(char)
return is_balanced(expression,elements,ind+1)
elif char in post_brackets:
if elements.empty() :
return False
if not is_matching(elements.top_element(), char):
return False
elements.remove()
return is_balanced(expression,elements,ind+1)
elif char == "X":
temp = Stack()
temp.insert(char)
result = (is_balanced(expression,temp,ind+1))
if result:
return True
if elements.empty():
return False
elements.remove()
return is_balanced(expression,elements,ind+1)
expression = "([X}])"
if expression == "":
print("No brackets in expression!")
elif len(expression) % 2 != 0:
print("Not balanced")
elif is_balanced(expression):
print("Balanced")
else:
print("Not Balanced")
Final improved and optimised version that works:
class Sklad:
def __init__(self):
self.podatki = []
def vstavi(self, x):
self.podatki.append(x)
def prazen(self):
return len(self.podatki) == 0
def odstrani(self):
if self.prazen():
raise ValueError('ODSTRANI: Sklad je prazen.')
self.podatki.pop()
def vrh(self):
if self.prazen():
raise ValueError('VRH: Sklad je prazen.')
return self.podatki[-1]
def __str__(self):
izp = 'DNO'
for elt in self.podatki:
izp += ' : ' + str(elt)
return izp + ' : VRH'
def kopiraj(self):
if self.prazen():
raise ValueError('VRH: Sklad je prazen.')
obrnjen = Sklad()
nov = Sklad()
for elt in self.podatki:
obrnjen.vstavi(elt)
for elt in self.podatki:
nov.vstavi(elt)
return nov
def so_pravilno(izraz, hrani = None, nivo = 0, oklep = {"(":")","[":"]","{":"}"}):
if not hrani:
hrani = Sklad()
for i, znak in enumerate(izraz):
if znak in oklep:
hrani.vstavi(znak)
elif znak in oklep.values():
if hrani.prazen():
return False
if oklep.get(hrani.vrh()) != znak and hrani.vrh() != "X":
return False
hrani.odstrani()
elif znak == "X":
if not hrani.prazen():
tmp = hrani.kopiraj()
tmp.odstrani()
if so_pravilno(izraz[i+1:],tmp, nivo+2):
return True
else:
hrani.vstavi(znak)
return hrani.prazen()
izraz = "(XX{X)"
if len(izraz) % 2 != 0:
print("Not Balanced")
elif so_pravilno(izraz):
print("Balanced")
else:
print("Not Balanced")