Valid Parentheses Problem - Stack Implementation in Data Structures

🧩 What is the Valid Parentheses Problem?

The Valid Parentheses problem checks whether a given string containing parentheses is balanced. This means every opening bracket must have a corresponding closing bracket in the correct order.

Example:

Input: "()[]{}"
Output: true

Input: "(]"
Output: false

Valid characters are typically (), {}, and [].

📜 Problem Statement

Given a string containing only parentheses characters, determine if the input string is valid. A valid string:

Has matching opening and closing brackets.
Closing brackets appear in the correct order.

🗂 How a Stack Helps in This Problem

A stack follows the Last-In-First-Out (LIFO) principle, which is perfect for matching parentheses because the most recent opening bracket should be closed first.

🐌 Step-by-Step Solution

Steps:

Create an empty stack to store opening brackets.
Traverse the string character by character.
If the character is an opening bracket, push it onto the stack.
If it is a closing bracket:
- Check if the stack is empty. If yes, return false (no matching opening bracket).
- Pop the top element from the stack and check if it matches the type of closing bracket.
After traversal, if the stack is empty, return true; otherwise, false.

💻 Example

import java.util.Stack;

public class ValidParentheses {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char ch : s.toCharArray()) {
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);
            } else {
                if (stack.isEmpty()) return false;
                char top = stack.pop();
                if ((ch == ')' && top != '(') ||
                    (ch == '}' && top != '{') ||
                    (ch == ']' && top != '[')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

Time Complexity: O(n)
Space Complexity: O(n) – Stack storage for brackets.

🧠 Why This Problem is Important

Builds stack manipulation skills.
Common in technical interviews.
Foundation for parsing problems in compilers and syntax validation.

📚 Summary

The Valid Parentheses problem using a stack. We discussed the problem definition, the role of stacks, step-by-step logic, and a Java code example. This problem is a classic example of how stack data structures help in syntax checking and matching problems, making it an essential topic for interviews and algorithm design.