balanced parentheses Algorithm

The balanced parentheses algorithm is a fundamental computer science algorithm used to determine whether a given expression or sequence has a valid arrangement of parentheses. This algorithm is frequently employed in compilers and interpreters to validate the syntax of programs, as well as in text editors and integrated development environments (IDEs) to assist with code formatting and error detection. The algorithm works by examining the input string character by character and checking whether the parentheses – which can include various types like (), {}, and [] – are correctly balanced, meaning that each opening parenthesis has a corresponding closing parenthesis and they are properly nested. The algorithm typically utilizes a stack data structure to keep track of the opening parentheses encountered during the traversal of the input string. When an opening parenthesis is encountered, it is pushed onto the stack. When a closing parenthesis is encountered, the algorithm checks if the stack is empty or if the top of the stack contains a matching opening parenthesis. If either of these conditions is not met, the input is deemed to be unbalanced. If the closing parenthesis matches the opening one at the top of the stack, the algorithm pops the opening parenthesis off the stack and continues processing the input string. After traversing the entire string, if the stack is empty, the input is considered to have balanced parentheses. However, if the stack is not empty, this indicates that there are unmatched opening parentheses and the input is unbalanced.
from .stack import Stack

__author__ = "Omkar Pathak"


def balanced_parentheses(parentheses):
    """ Use a stack to check if a string of parentheses is balanced."""
    stack = Stack(len(parentheses))
    for parenthesis in parentheses:
        if parenthesis == "(":
            stack.push(parenthesis)
        elif parenthesis == ")":
            if stack.is_empty():
                return False
            stack.pop()
    return stack.is_empty()


if __name__ == "__main__":
    examples = ["((()))", "((())", "(()))"]
    print("Balanced parentheses demonstration:\n")
    for example in examples:
        print(example + ": " + str(balanced_parentheses(example)))

LANGUAGE:

DARK MODE: