Balanced expression with replacement

Question

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")

Answer 1

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")