Balancing brackets

 

Balancing brackets = checking whether every opening bracket has a matching closing bracket in the correct order.

Types usually considered:

• ()
• []
• {}

---

Core idea (stack method)

Use a stack:

1. Read characters left → right.
2. If opening bracket → push onto stack.
3. If closing bracket →
   • stack empty → invalid
   • top doesn’t match → invalid
   • else pop.
4. End → stack must be empty.

Time: O(n)
Space: O(n)

---

Example

Input:

{[()]}

Process:

{   push
[   push
(   push
)   pop
]   pop
}   pop

Stack empty → balanced.

---

Python (clean version)

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

    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in ")]}":
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()

    return len(stack) == 0

---

Edge cases people miss

• "(]" → order mismatch
• "(((" → leftover opens
• "))" → early close
• "" → balanced
• "a+(b*c)" → ignore non-brackets

---

Interview twist

If asked minimum removals to balance → count unmatched opens + closes while scanning once.

If asked longest valid parentheses → stack indexes or DP.

---

Further reading:

• Knuth — The Art of Computer Programming, Vol. 1 (stack parsing)
• Aho, Sethi, Ullman — Compilers: Principles, Techniques & Tools

Minimum C++ Question :

#include <iostream>

#include <string>

#include <stack>

#include <map>

// Function to check if a given string of brackets is balanced

bool areBracketsBalanced(const std::string& expression) {

    std::stack<char> s;

    std::map<char, char> bracket_pairs = {

        {'(', ')'},

        {'{', '}'},

        {'[', ']'}

    };

    for (char c : expression) {

        // If it's an opening bracket, push its corresponding closing bracket onto the stack

        if (bracket_pairs.count(c)) {

            s.push(bracket_pairs[c]);

        }

        // If it's a closing bracket

        else {

            // If the stack is empty or the top of the stack doesn't match the current character, it's unbalanced

            if (s.empty() || s.top() != c) {

                return false;

            }

            // Otherwise, it's a match, so pop the opening bracket's pair

            s.pop();

        }

    }

    // After traversing the string, the stack should be empty for a balanced expression

    return s.empty();

}

int main() {

    std::string str1 = "{[()]}";

    std::string str2 = "([]){}";

    std::string str3 = "[(])";

    std::string str4 = "(((";

    std::cout << str1 << " is balanced: " << (areBracketsBalanced(str1) ? "True" : "False") << std::endl;

    std::cout << str2 << " is balanced: " << (areBracketsBalanced(str2) ? "True" : "False") << std::endl;

    std::cout << str3 << " is balanced: " << (areBracketsBalanced(str3) ? "True" : "False") << std::endl;

    std::cout << str4 << " is balanced: " << (areBracketsBalanced(str4) ? "True" : "False") << std::endl;

    return 0;

}