Check for balanced parentheses in Python

1. Emulating stack

Method 1

class Stack:
    def __init__(self):
        self.elements = []
    
    def push(self, new_item):
        self.elements.append(new_item)
        return True
    
    def pop(self):
        return self.elements.pop()

    def size(self):
        return len(self.elements)
      
    def is_empty(self):
        return self.elements == []

    def peek(self):
        if self.is_empty:
            return None 
        else:
            return self.elements[0]

Method 2

class Node: 
    def __init__(self, data=None): 
        self.data = data 
        self.next = None 
        
class Stack2: 
    def __init__(self):
        self.top = None 
        self.size = 0 

    def push(self, data):
        node = Node(data)
        if self.top:
            node.next = self.top
            self.top = node
        else:
            self.top = node
            self.size += 1 
    
    def pop(self):
        if self.top:
            data = self.top.data
            self.size -= 1
            if self.top.next:
                self.top = self.top.next 
            else: 
                self.top = None 
            return data 
        else: 
            return None 
    def peek(self):
        if self.top:
            return self.top.data 
        else: 
            return None 

2. Checking balanced parentheses.

Example

exp1 = "(2+3)+(1-5)" # True

exp2 = "((3*2))*(7/3))" # False

exp3 = "(3*5))]" # False

Method 1

def is_valid(express):
    stack = Stack()
    opening = ['(', '[', '{']
    closing = [')', ']', '}']
    l = []
    
    for bracket in express:
        if bracket in opening:
            stack.push(bracket) 
        if bracket in closing:
            l.append(bracket)
            index1 = closing.index(bracket)
            if stack.size() > 0:
                element = stack.pop()
                index2 = opening.index(element)
                if index1 != index2:
                    return False
                l.pop()
    if len(l) == 0:
        return True
    return False

print(is_valid(exp1))
print(is_valid(exp2))
print(is_valid(exp3))

True False False

Method 2

def is_valid2(express):
    stack = Stack2()
    opening = ["[","{","("] 
    closing = ["]","}",")"] 

    for bracket in express:
        if bracket in opening:
            stack.push(bracket) 
        if bracket in closing: 
            last = stack.pop() 
            if last is '{' and bracket is '}': 
                continue
            elif last is '[' and bracket is ']':
                continue
            elif last is '(' and bracket is ')':
                continue
            else: 
                return False
    if stack.size > 0:
        return False
    else:
        return True 
    
print(is_valid2(exp1))
print(is_valid2(exp2))
print(is_valid2(exp3)) 

True False False

Method 3

def is_valid3(express):
    opening = ["[","{","("] 
    closing = ["]","}",")"] 
    stack = []
    
    for bracket in express: 
        if bracket in opening: 
            stack.append(bracket) 
        elif bracket in closing: 
            pos = closing.index(bracket) 
            if ((len(stack) > 0) and
                (opening[pos] == stack[len(stack)-1])): 
                stack.pop() 
            else: 
                return "False"
    if len(stack) == 0: 
        return "True"
    else: 
        return "False"

print(is_valid3(exp1))
print(is_valid3(exp2))
print(is_valid3(exp3))

True False False

3. Counting the number of the valid bracket pairs of an arithmetic expression

def count_pairs(exp):
    stack = Stack()  
    opening = ['(', '[', '{']  
    closing = [')', ']', '}']  
    count = 0  
    
    for bracket in exp:  
        if bracket in opening:  
            stack.push(bracket)  
        if bracket in closing:  
            index1 = closing.index(bracket)  
            if stack.size() > 0:  
                element = stack.pop()  
                index2 = opening.index(element) 
                if index1 == index2:
                    count += 1  
    return count  # return

exp1 = "(2+3)+(1-5)" # 2 pairs
exp2 = "((([()])))" # 5 pairs
exp3 = "[([])" # 2 pairs

print("Expression exp1 has", count_pairs(exp1), "pairs")
print("Expression exp2 has",count_pairs(exp2), "pairs")
print("Expression exp3 has",count_pairs(exp3), "pairs")

Expression exp1 has 2 pairs Expression exp2 has 5 pairs Expression exp3 has 2 pairs