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

@bbbbbbbbb I think if you make the first `X` a `[` and the second a `]` it balances, i.e. `{([[]])}`. — Tom Karzes, Oct 30 '22 at 07:22

score -1 · Answer 1 · answered Oct 30 '22 at 12:50

You can do it by recursively testing all possible replacements for an X:

def can_be_balanced(expr):
    pairs = "{}[]()"
    opening_brackets = pairs[::2]
    closing_brackets = pairs[1::2]
    closer = {o:c for o, c in zip(opening_brackets, closing_brackets)}
    opener = {c:o for o, c in zip(opening_brackets, closing_brackets)}
    
    stack = []
    for item in expr:
        if item in opening_brackets:
            # we append opening brackets to the stack
            stack.append(item)

        elif item in closing_brackets:
            if not stack or stack[-1] != opener[item]:
                # the closing bracket doesn't match the top of the stack
                return False
            else:
                # if it does, we remove the matching opening bracket
                stack.pop()
        
        elif item == 'X':
            # X could be any of the opening brackets,
            possible = list(opening_brackets)
            if stack and stack[-1] in opening_brackets:
                # or the closing bracket matching the top of the stack
                possible.append(closer[stack[-1]])
            for pos in possible:
                # we replace this X, the first one remaining in expr 
                test_expr = expr.replace('X', pos, 1)
                if can_be_balanced(test_expr):
                    # This is just in order to print the working solution we just found,
                    # you may remove these two lines
                    if not 'X' in test_expr:
                        print(test_expr)
                    
                    return True
                    
            # None of the replacements for X gave a balanced expression 
            return False
            
        else:
            raise ValueError(f'Invalid item {item} in {expr}')
    
    # The expression is balanced if and only if the stack ends up empty
    return not stack

Testing on your sample data:

tests = [("[{X}(X)]", False),
         ("{(X[X])}", True),
         ("([X}])", True),
        ]

for test in tests:
    print(test[0], ': should be', test[1])
    print(can_be_balanced(test[0]))
    print('-'*20)

correctly outputs (with the balanced expression in case it can be done):

[{X}(X)] : should be False
False
--------------------
{(X[X])} : should be True
{([[]])}
True
--------------------
([X}]) : should be True
([{}])
True
--------------------

Note that a major problem in your code is that you only test the end of the expression, starting at the position of the X. Beware also of the mutable default argument elements=Stack() that would leave you with the remnants of the previous call to the function instead of a fresh, empty Stack object.

score -1 · Accepted Answer · answered Apr 30 '23 at 16:22

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

Balanced expression with replacement

2 Answers2