Checking Brackets Algorithm

Question

While studying the data structure, I am making checking brackets algorithm myself. I wrote the python code as shown below, but if ')', '}', ']' are used, always comes out 'No' as output... How can I fix the code?

• Condition 1) The number of left and right brackets must be the same.
• Condition 2) The left bracket must precede the right bracket.
• Condition3) Only inclusion relationships exist between brackets.

Stack

class Stack:
    def __init__(self):
        self.top = []

    def isEmpty(self): 
        return len(self.top) == 0

    def size(self):
        return len(self.top)

    def clear(self):
        self.top = []

    def push(self, item):
        self.top.append(item)

    def pop(self):
        if not self.isEmpty():
            return self.top.pop()

    def peek(self):
        if not self.isEmpty():
            return self.top[-1] 

Checking Brackets function

def check(statement):
    stack = Stack()
    msg = ""

    for ch in statement:
        if ch in ('{', '[', '('):
            stack.push(ch)
            msg = "Yes"
            return msg, stack
        elif ch in ('}', ']', ')'):
            if stack.isEmpty():     # Condition 2
                msg = "No"
                return msg, stack
            else:
                left = stack.pop(-1)
                if (ch == "}" and left != "{") or \
                        (ch == "]" and left != "[") or \
                        (ch == ")" and left != "(") :   # Condition 3
                        msg = "No"
                        return msg, stack
                else:
                    msg = "Yes"
                    return msg, stack
    
    if (stack.isEmpty() == 0):  # Condition 1
        msg = "No"
        return msg, stack

    msg = "Yes"
    return msg, stack

main

text = input()
count = 0
result = "Yes"
messages = []

for t in text:
    message = check(t)[0]
    if (t in ['(',')','{','}','[',']']):
        messages.append(message)

for message in messages:
    count += 1
    if message == "No":
        result = "No"
    
print(result + '_' + str(count))
print(messages)

Input

(2*{137+(8-2)/2} + [9*{14-5* (8-1)}])

Output

No_12
['Yes', 'Yes', 'Yes', 'No', 'No', 'Yes', 'Yes', 'Yes', 'No', 'No', 'No', 'No']

Expected output

Yes_12
['Yes', 'Yes', 'Yes', 'Yes', 'Yes', 'Yes', 'Yes', 'Yes', 'Yes', 'Yes', 'Yes', 'Yes']

Answer 1

I think you've made this more complex than it really is. Ultimately you need to know just two things. 1) That all brackets match - i.e., equal number of left/right brackets of each type and 2) That there's no right bracket (of any type) when there's no corresponding (preceding) left bracket.

Therefore:

class Brackets:
    left = '([{'
    right = ')]}'
    def __init__(self):
        self.brackets = []
    def isvalid(self):
        return len(self.brackets) == 0
    def add(self, b):
        if b in Brackets.left:
            self.brackets.append(b)
        else:
            if b in Brackets.right:
                i = Brackets.right.index(b)
                if self.brackets[-1] != Brackets.left[i]:
                    raise ValueError 
                self.brackets.pop(-1)


brackets = Brackets()

input_ = '(2*{137+(8-2)/2} + [9*{14-5* (8-1)}])'

for c in input_:
    brackets.add(c)

print(brackets.isvalid())

The output of this will be

True

If the string contains a pattern whereby a right-bracket is observed and the previous entry in the list was not the corresponding left-bracket then a ValueError exception will be raised.

If the string contains a right-bracket and the list is empty then an IndexError will be raised