Check if a String is a Valid Parentheses String

Validating parentheses is a classic computer science problem with applications in various areas, from compiler design to evaluating mathematical expressions. This post will look at how to efficiently check if a given string containing parentheses ((), [], {}) is valid in Python. A valid string means that all opening parentheses have corresponding closing parentheses of the same type, and they are nested correctly.

Understanding the Problem

The core idea is to use a stack data structure. As we iterate through the string:

Opening Parenthesis: If we encounter an opening parenthesis ((, [, {), we push it onto the stack. This essentially “remembers” that we need a closing parenthesis of the same type later.
Closing Parenthesis: If we encounter a closing parenthesis (), ], }), we check the top of the stack. If the stack is empty or the top element doesn’t match the closing parenthesis, the string is invalid. If they match, we pop the top element from the stack.
End of String: After processing the entire string, if the stack is empty, it means all opening parentheses have been matched with their corresponding closing parentheses, and the string is valid. Otherwise, it’s invalid.

Python Code Implementation

Here’s a Python function that implements this logic:

def is_valid_parentheses(s):
    """
    Checks if a string containing parentheses is valid.

    Args:
      s: The input string.

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

    for char in s:
        if char in mapping:  # Closing parenthesis
            top_element = stack.pop() if stack else '#' # Handle empty stack case
            if mapping[char] != top_element:
                return False
        else:  # Opening parenthesis
            stack.append(char)

    return not stack  # True if stack is empty (all parentheses matched)


# Example usage:
print(is_valid_parentheses("()"))  # True
print(is_valid_parentheses("()[]{}"))  # True
print(is_valid_parentheses("(]"))  # False
print(is_valid_parentheses("([)]"))  # False
print(is_valid_parentheses("{[]}"))  # True
print(is_valid_parentheses("((()))")) #True
print(is_valid_parentheses("(()")) #False

This code uses a dictionary mapping to efficiently check for matching parenthesis pairs. The else block handles opening parentheses by pushing them onto the stack. The if block handles closing parentheses, performing matching and stack manipulation. The final return not stack cleverly checks for the empty stack condition, indicating a valid string.

Handling Edge Cases

The code above efficiently handles many edge cases:

Empty String: An empty string is considered valid because it contains no unmatched parentheses.
Mismatched Parentheses: The code correctly identifies strings with mismatched parenthesis types (e.g., (]).
Unclosed Parentheses: The return not stack statement effectively catches strings with unclosed opening parentheses.

Time and Space Complexity

The time complexity of this solution is O(n), where n is the length of the input string, because we iterate through the string once. The space complexity is also O(n) in the worst case, as the stack could potentially store all opening parentheses if they are deeply nested. However, in many practical scenarios, the space used will be less than O(n).