Solving the Balancing Parentheses Problem Using Stacks | Data Structures and Algorithms Day #7

In this article, we’ll explore the balancing parentheses problem, a common coding challenge that tests your understanding of data structures and algorithms. We’ll learn how to efficiently solve this problem using stacks, demonstrate implementations in Python and JavaScript, and discuss time complexity considerations. Whether you are preparing for interviews or sharpening your coding skills, mastering this problem is essential.

---

What Is the Balancing Parentheses Problem?

The balancing parentheses problem involves determining whether a given string containing parentheses ( ), square brackets [ ], or curly braces { } is properly nested and balanced. A balanced string ensures that:

1. Every opening symbol (e.g., (, [, {) has a matching closing symbol.

2. The order of symbols respects the Last-In-First-Out (LIFO) structure—meaning the most recent open bracket must be closed first.

Why Is It Important?

Balancing parentheses is essential for:

• Expression parsing: Many programming languages require correctly nested expressions for compilation.

• Syntax validation: Checking if user input (like formulas or code snippets) is properly structured.

• Algorithm design: It helps build logic for problems involving nested structures, such as trees or XML parsing.

A stack is the perfect data structure for this problem because it allows tracking the most recent opening symbol and validating each closing one in sequence.

---

How Does a Stack Help Solve the Problem?

A stack follows the LIFO principle—meaning elements are added (pushed) and removed (popped) from the same end. Here’s how a stack can be used to check if parentheses are balanced:

1. Push each opening symbol ((, [, {) onto the stack.

2. When encountering a closing symbol (), ], }):

   • Check if the top of the stack has the matching opening symbol.

   • If it matches, pop the top element off the stack.

   • If it doesn’t match or the stack is empty, the expression is unbalanced.

3. At the end, if the stack is empty, the expression is balanced. If not, it’s unbalanced.

---

Code Examples: Balancing Parentheses with Stacks

Python Code Example

def is_balanced(expression):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}

    for char in expression:
        if char in pairs.values():  # Opening symbols
            stack.append(char)
        elif char in pairs.keys():  # Closing symbols
            if stack and stack[-1] == pairs[char]:
                stack.pop()
            else:
                return False
    return len(stack) == 0

# Test cases
print(is_balanced("({[]})"))  # Output: True
print(is_balanced("{[}]"))    # Output: False

---

JavaScript Code Example

function isBalanced(expression) {
    const stack = [];
    const pairs = { ')': '(', ']': '[', '}': '{' };

    for (const char of expression) {
        if (Object.values(pairs).includes(char)) {
            stack.push(char);
        } else if (Object.keys(pairs).includes(char)) {
            if (stack.length && stack[stack.length - 1] === pairs[char]) {
                stack.pop();
            } else {
                return false;
            }
        }
    }
    return stack.length === 0;
}

// Test cases
console.log(isBalanced("({[]})")); // Output: true
console.log(isBalanced("{[}]"));   // Output: false

---

Visualizing Stack Operations

Step-by-Step Example for "({[]})"

1. Push ( onto the stack → Stack: [ ( ]

2. Push { → Stack: [ (, { ]

3. Push [ → Stack: [ (, {, [ ]

4. Encounter ] → Match top [, pop → Stack: [ (, { ]

5. Encounter } → Match top {, pop → Stack: [ ( ]

6. Encounter ) → Match top (, pop → Stack: []

Since the stack is empty, the expression is balanced.

---

Time and Space Complexity of the Solution

• Time Complexity: O(n) – We iterate over the input string once.

• Space Complexity: O(n) – In the worst case, the stack holds all opening symbols.

---

Common Mistakes to Avoid

1. Ignoring unmatched symbols: Simply counting open and close symbols isn’t enough; order matters.

2. Assuming fixed symbol types: Be prepared for mixed parentheses, brackets, and braces.

3. Forgetting to check stack at the end: Even if all symbols match, an incomplete stack means the expression is not balanced.

---

Comparison Table: Iterative vs. Recursive Reversal

---

Real-World Applications of the Balancing Parentheses Problem

The balancing parentheses problem isn’t just an academic exercise. Here are some real-world use cases:

1. Compilers and Interpreters: Programming languages use parentheses, brackets, and braces to define code blocks, function calls, and arrays. Compilers must validate that these are correctly nested.

2. Expression Evaluation: Calculators and parsers use this logic to evaluate arithmetic expressions with nested parentheses.

3. HTML/XML Parsing: Ensuring that tags are properly opened and closed follows a similar pattern to balancing brackets.

4. Undo Functionality: Many software applications rely on stacks to keep track of user actions and enable the undo feature.

---

FAQs

1. How do you use a stack to balance parentheses?

A stack helps by storing opening symbols as they appear and removing them when a matching closing symbol is found. If the stack is empty at the end of the expression, the parentheses are balanced.

2. What is the time complexity of checking valid parentheses?

The time complexity is O(n), where n is the length of the input string. Each symbol is processed once, making the algorithm linear in time.

3. Can you reverse a string with nested parentheses using recursion?

Yes! Recursive solutions are possible, but they may encounter stack overflow for deeply nested structures. Iterative solutions are often more efficient for real-world applications.

4. What happens if I mix different types of brackets?

The solution using stacks can handle multiple types of brackets as long as they follow the correct nesting rules. For example, "([{}])" would be considered valid.

5. Is there an easier way to solve the problem without using a stack?

Using a stack is the most efficient and intuitive approach. Other methods would be more complex and less readable for this particular problem.

---

Conclusion

Solving the balancing parentheses problem using stacks is an essential skill for any programmer. It demonstrates the power of LIFO data structures and provides a practical way to manage nested operations.

Try implementing the solution on your own, modifying it to handle different types of matching symbols or more complex expressions. Understanding how stacks operate will enhance your ability to solve parsing problems, expression evaluations, and algorithm challenges.