Balanced Parentheses

December 31, 2023

Problem #

Given a string containing three types of parentheses ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’, write an algorithm to check if the input string is valid. A string is valid if open brackets are closed by the same type of brackets, and open brackets must be closed in the correct order.

Solution #

Here’s the Python code for checking if a string containing different types of parentheses is valid:

def isValidParentheses(s):
    """
    Check if the input string of parentheses is valid.

    Args:
    s (str): The input string containing parentheses.

    Returns:
    bool: True if the string is valid, False otherwise.
    """
    stack = []
    mapping = {")": "(", "}": "{", "]": "["}

    for char in s:
        if char in mapping:
            top_element = stack.pop() if stack else '#'
            if mapping[char] != top_element:
                return False
        else:
            stack.append(char)

    return not stack

# Example usage
input_string = "({[]})"
isValid = isValidParentheses(input_string)
print(isValid)

This code defines a function isValidParentheses which takes a string s as input and returns True if the string is a valid sequence of parentheses, and False otherwise. The function uses a stack to keep track of opening parentheses. When it encounters a closing parenthesis, it checks whether the last opened parenthesis matches the type. If it does, the pair is valid and is removed from the stack. If not, the string is immediately invalid. The string is valid if the stack is empty at the end of processing.

In the provided example, input_string = "({[]})", the function returns True, indicating that this is a valid sequence of parentheses.