Valid Parentheses

To solve this coding challenge, we need to determine if a string containing only characters '(', ')', '{', '}', '[' and ']' is valid based on certain criteria. The criteria state that open brackets must be closed by the same type of brackets, in the correct order, and every closing bracket must have a corresponding opening bracket of the same type.

Explanation

  1. Understanding the Requirements:
    • The string should be validated to ensure all open brackets are closed by the same type of brackets.
    • The closing brackets must appear in the correct sequence.
    • Every closing bracket must have a corresponding preceding open bracket of the same type.
  2. Using a Stack Data Structure:
    • A stack is a suitable data structure for this challenge because it follows the Last In, First Out (LIFO) principle. This helps in matching the most recent unclosed opening bracket with the current closing bracket.
    • Iterate through each character in the string:
      • If the character is an open bracket, push it onto the stack.
      • If the character is a closing bracket, check if it matches the type of the last opened bracket by inspecting the stack's top element.
      • If the stack is empty when a closing bracket is encountered or if there is a mismatch, the string is invalid.
    • After processing all characters, ensure the stack is empty to confirm all opening brackets have been closed properly.

    Step-by-Step Explanation

  3. Initialize an empty stack.
  4. Iterate through each character in the string:
    • For each open bracket '(', '{', '[', push it onto the stack.
    • For each closing bracket ')', '}', ']', check the stack:
      • If the stack is empty or the top of the stack does not match the corresponding opening bracket, return false.
      • If it matches, pop the top of the stack.
  5. After iterating, check the stack:
    • If the stack is empty, return true indicating all brackets were properly closed.
    • Otherwise, return false indicating there are unmatched opening brackets.

    Detailed Steps in Pseudocode:

                                                
// Function to check if the input string is valid
FUNCTION isValid(input_string):
// Initialize an empty stack to store open brackets
DECLARE stack AS EMPTY LIST

// Dictionary to match closing brackets with corresponding opening brackets
DECLARE matching_brackets AS DICTIONARY WITH ENTRIES ')': '(', ']': '[', '}': '{'

// Iterate through each character in the input string
FOR EACH character IN input_string:
IF character IS IN ['(', '[', '{']:
// If the character is an open bracket, push it onto the stack
stack.PUSH(character)
ELSE IF character IS IN [')', ']', '}']:
// If the character is a closing bracket, check the stack
IF stack IS EMPTY OR matching_brackets[character] IS NOT EQUAL TO stack.PEEK():
// If the stack is empty or top of the stack does not match, return false
RETURN false
// If it matches, pop the top element from the stack
stack.POP()

// Check if the stack is empty after processing all characters
RETURN stack IS EMPTY

    Explanation of Pseudocode:

  6. We start by initializing an empty stack using an empty list.
  7. matching_brackets
    is a dictionary that helps us identify the corresponding opening bracket for each closing bracket.
  8. We loop through each character of the input string:
    • If it's an opening bracket, we push it onto the stack.
    • If it's a closing bracket, we check two conditions:
      • The stack must not be empty.
      • The top element of the stack must be the corresponding opening bracket.
    • If either condition fails, we immediately return
      false
      .
    • Otherwise, we remove the top element from the stack.
  9. Finally, we ensure the stack is empty, indicating all open brackets are properly matched. If empty, return
    true
    ; otherwise, return
    false
    .
This detailed approach ensures the correct validation of parentheses in a string, meeting all the mentioned criteria.