Embedded Prep

The Valid Parentheses Problem is a classic example of how stack data structures can be used to solve real-world problems involving nested or paired data. The challenge is to determine whether a given string containing only brackets—(, ), {, }, [, ]—is properly balanced and well-formed.

In a valid expression:

• Every opening bracket must have a corresponding closing bracket.
• Brackets must close in the correct order, maintaining the expected nesting.

To solve this, a stack is used to keep track of opening brackets. When a closing bracket appears, the algorithm checks whether it correctly matches the most recent unclosed opening bracket by looking at the top of the stack. If it doesn’t match or the stack is empty when it shouldn’t be, the expression is invalid. If the stack is empty after processing all characters, the expression is valid.

Valid Parentheses Problem stack description:

You are given a string that contains only the characters:

'(', ')', '{', '}', '[', ']'

Your task is to check whether the given string is a valid sequence of parentheses.

A valid string must follow these rules:

1. Every opening bracket must have a corresponding closing bracket.
2. The brackets must close in the correct order.
3. Each type of bracket must match correctly (() not [(]).

Why Use a Stack?

A stack is a data structure that works on Last In, First Out (LIFO). That means:

• The last element you put in is the first one that comes out.
• This is perfect for tracking open brackets and checking if they are closed properly.

Step-by-Step Logic for Valid Parentheses Problem stack:

1. Create an empty stack.
2. Loop through each character in the string.
3. If it is an opening bracket ((, {, [), push it onto the stack.
4. If it is a closing bracket:
   • Check if the stack is empty → if yes, return false.
   • Pop the top element from the stack.
   • Check if the popped element matches the current closing bracket → if not, return false.
5. After the loop, if the stack is empty, return true (valid). If not, return false (invalid).

Example of Valid Parentheses Problem stack:

Input: "{[()]}"
Output: true
Explanation: All brackets open and close in the correct order.

Input: "{[(])}"
Output: false
Explanation: [ is not properly closed before ) comes.

Key Concepts Covered:

• Stack data structure
• Matching pairs of brackets
• Input validation
• Control flow with conditionals

Problem Statement Valid Parentheses Problem stack:

Given a string containing just the characters '(', ')', '{', '}', '[', and ']', determine if the input string is valid.

👉 A string is valid if:

1. Open brackets are closed by the same type of brackets.
2. Open brackets are closed in the correct order.
3. Every closing bracket has a corresponding open bracket.

Example:

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

Input: "({[})"
Output: false

Input: "((("
Output: false

Approach: Use a Stack

• Push opening brackets into a stack.
• For every closing bracket:
  • Check if the stack is empty → ❌ Invalid
  • Check if the top of the stack is the matching opening bracket
• In the end, the stack should be empty → ✅ Valid

C++ Code (Beginner-Friendly) | Valid Parentheses Problem stack

#include <iostream>
#include <stack>
#include <string>
using namespace std;

bool isValid(string s) {
    stack<char> st;

    for (char ch : s) {
        // Push opening brackets
        if (ch == '(' || ch == '{' || ch == '[') {
            st.push(ch);
        } else {
            // If stack is empty when closing bracket comes → invalid
            if (st.empty()) return false;

            char top = st.top();
            st.pop();

            // Check matching pairs
            if ((ch == ')' && top != '(') ||
                (ch == '}' && top != '{') ||
                (ch == ']' && top != '[')) {
                return false;
            }
        }
    }

    // Stack should be empty if all brackets matched
    return st.empty();
}

int main() {
    string str = "({[]})";
    if (isValid(str)) {
        cout << "Valid" << endl;
    } else {
        cout << "Invalid" << endl;
    }
    return 0;
}

Dry Run Example: "({[]})"

Step	Char	Stack	Action
1	(	(	Push
2	{	( {	Push
3	[	( { [	Push
4	]	( {	Pop + Match [
5	}	(	Pop + Match {
6	)	(empty)	Pop + Match (

→ Stack is empty ✅ → Valid

Python Code (Beginner-Friendly) | Valid Parentheses Problem stack

def isValid(s):
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}

    for char in s:
        if char in mapping.values():
            stack.append(char)
        elif char in mapping:
            if not stack or stack[-1] != mapping[char]:
                return False
            stack.pop()
        else:
            # In case of unexpected character
            return False

    return not stack

# Example usage
s = "{[()]}"
print("Valid" if isValid(s) else "Invalid")

Java Code (Beginner-Friendly) | Valid Parentheses Problem stack

import java.util.Stack;

public class ValidParentheses {

    public static 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();
    }

    public static void main(String[] args) {
        String s = "{[()]}";
        System.out.println(isValid(s) ? "Valid" : "Invalid");
    }
}

Beginner-Level Practice Problems

1. Basic Valid Parentheses

• 🔹 Problem: Check if the given string with only ()[]{} is valid.
• 🔹 Example: "([])" → true, "(]" → false
• 🔹 Goal: Implement the classic stack-based solution.

2. Minimum Add to Make Parentheses Valid

• 🔹 Problem: Given a string of parentheses '(' and ')', return the minimum number of additions needed to make it valid.
• 🔹 Example: "(()" → 1, "()))(" → 3
• 🔹 LeetCode #921

3. Longest Valid Parentheses

• 🔹 Problem: Given a string of '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
• 🔹 Example: "(()" → 2, ")()())" → 4
• 🔹 LeetCode #32

4. Remove Invalid Parentheses

• 🔹 Problem: Remove the minimum number of invalid parentheses to make the input string valid. Return all possible results.
• 🔹 Example: "(a)())()" → ["(a())()", "(a)()()"]
• 🔹 LeetCode #301

5. Score of Parentheses

• 🔹 Problem: Compute the score of a balanced parentheses string.
• 🔹 Rules: "()" has score 1, "AB" has score A + B, "(A)" has score 2 * A
• 🔹 Example: "(()(()))" → 6
• 🔹 LeetCode #856

Bonus Challenge

6. Validate Stack Sequences

• 🔹 Problem: Given two sequences pushed and popped, return true if they could represent the push and pop sequence of a single stack.
• 🔹 LeetCode #946

You can also Visit other tutorials of Embedded Prep 

• Structure with Pointers
• Master How to Use a Saleae Logic Analyzer with Arduino Uno (2025)
• Top 30+ I2C Interview Questions
• Bit Manipulation Interview Questions
• Structure and Union in c
• Fault Handling in Arm Cortex Mx Processor
• Merge sort algorithm

Special thanks to @mr-raj for contributing to this article on EmbeddedPrep