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;

}

In C++, if bracket_pairs is a map, this call:

bracket_pairs.count('(');

checks whether '(' exists as a key in the map.

std::map::count(key) → returns:

• 1 → key exists
• 0 → key absent

Example:

#include <iostream>
#include <map>
using namespace std;

int main() {
    map<char,char> bracket_pairs;

    bracket_pairs[')'] = '(';
    bracket_pairs[']'] = '[';
    bracket_pairs['}'] = '{';

    cout << bracket_pairs.count('(') << endl;
}

Output

0

Reason:
'(' is a value, not a key.

Map content:

key → value
)   → (
]   → [
}   → {

Check example:

bracket_pairs.count(')')

Output

1

Because ')' is a key.

Typical use in bracket algorithms:

if(bracket_pairs.count(ch))

Meaning:

Is this character a closing bracket?

If true → check matching opening bracket using stack.

Reference
https://en.cppreference.com/w/cpp/container/map/count

Fur