Balanced Parenthesis Checker: Stack-Based Solution With Code

A balanced parenthesis checker validates that every opening bracket in an expression has a matching closing bracket of the same type, in the correct order.

That is the full problem statement. Input: a string. Output: 1 if balanced, -1 if not. Simple to state, easy to get wrong on edge cases.

What “balanced” means (and what it doesn’t)

Three bracket types matter: parentheses (), square brackets [], and curly braces {}. An expression is balanced when every opening bracket has a corresponding closing bracket, pairs close in the reverse order they opened (last opened, first closed), and no closing bracket appears when the stack is empty.

Some test cases to fix the definition:

Expression	Result	Reason
((()))	1	Opens 3, closes 3, correct order
{[()]}	1	Three types, correctly nested
()((	-1	Two unclosed ( remain
{(})	-1	Mis-nested: ) closes before }
][	-1	Closing bracket with empty stack
(empty)	1	Nothing to mismatch

The mis-nesting case {(}) deserves attention. It has equal counts of opening and closing brackets, yet it is unbalanced. A counter-based check would wrongly return 1 here. The stack-based check handles it correctly, which is why interviewers reach for this example.

Stack-based approach

A stack’s LIFO property (last in, first out) maps directly to bracket nesting. The algorithm:

• When you encounter an opening bracket ((, [, {), push it onto the stack.
• When you encounter a closing bracket (), ], }), check the stack:
  • Stack is empty: return -1 (no matching open bracket exists).
  • Top of stack matches: pop the top.
  • Top of stack does not match: return -1 (wrong bracket type).
• After scanning the full expression: return 1 if the stack is empty, -1 if not.

Python implementation

def is_balanced(expression):
    stack = []
    matching = {')': '(', ']': '[', '}': '{'}
    open_brackets = set(matching.values())

    for char in expression:
        if char in open_brackets:
            stack.append(char)
        elif char in matching:
            if not stack or stack[-1] != matching[char]:
                return -1
            stack.pop()

    return 1 if not stack else -1

Verify against the table:

print(is_balanced("((()))"))  # 1
print(is_balanced("{[()]}"))  # 1
print(is_balanced("()(("))    # -1
print(is_balanced("{(})"))    # -1
print(is_balanced(""))        # 1

Python’s built-in list works as a stack here. append() is push, pop() is pop, both O(1) amortised. The Python documentation on using lists as stacks covers this in detail.

Java implementation

import java.util.Stack;

public class BalancedParenthesis {
    public static int isBalanced(String expression) {
        Stack<Character> stack = new Stack<>();

        for (char ch : expression.toCharArray()) {
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            } else if (ch == ')' || ch == ']' || ch == '}') {
                if (stack.isEmpty()) return -1;
                char top = stack.pop();
                if ((ch == ')' && top != '(') ||
                    (ch == ']' && top != '[') ||
                    (ch == '}' && top != '{')) {
                    return -1;
                }
            }
        }

        return stack.isEmpty() ? 1 : -1;
    }
}

The logic is identical to the Python version. Java’s Stack<Character> is from java.util; push(), pop(), and isEmpty() are the three methods you need.

Counter-based approach (single bracket type only)

For expressions with only parentheses (), a counter replaces the stack:

• Start with count = 0.
• Increment on (, decrement on ).
• If count drops below 0 at any point, return -1 immediately.
• After the full scan: return 1 if count == 0, else -1.

Python implementation

def is_balanced_counter(expression):
    count = 0
    for char in expression:
        if char == '(':
            count += 1
        elif char == ')':
            count -= 1
            if count < 0:
                return -1
    return 1 if count == 0 else -1

This uses O(1) space: no auxiliary data structure is needed. The tradeoff is that it cannot distinguish bracket types. Feed it {(}) and it returns 1 (equal counts) instead of -1 (mis-nested). That is wrong.

Use the counter method only when:

• The problem explicitly guarantees a single bracket type.
• The question asks about space optimisation and confirms single-type input.

Prefer the stack method in every other case. The GeeksforGeeks reference on balanced parentheses also covers the edge cases where counter methods produce wrong answers.

Time and space complexity

Approach	Time complexity	Space complexity
Stack-based	O(n)	O(n)
Counter-based	O(n)	O(1)

Both approaches scan each character exactly once, so time complexity is O(n) for both. The difference is space: the stack can hold up to n characters in the worst case (all opening brackets, no closing bracket before end), while the counter is a single integer. For a deeper look at how auxiliary space affects algorithm selection, see FACE Prep’s guide on space complexity of algorithms.

One practical note: the O(n) space for the stack is linear in the length of the expression, not a fixed overhead. The stack grows with input size: a worst-case expression of all opening brackets fills the stack to capacity. The counter stays at one integer regardless of input size. If the problem gives a tight memory constraint, that is when the counter trade-off becomes relevant, and the problem statement will tell you it is single-bracket type.

Where this appears in placement tests

The balanced parenthesis problem is a standard moderate-difficulty question in coding rounds. It tests three things simultaneously: stack manipulation, edge-case awareness, and clean implementation under time pressure.

Common formats:

• Direct “write the function” with multiple test cases including empty strings and mis-nested inputs.
• A sub-problem inside an expression evaluator or a simple syntax validator.
• A variant asking for the index of the first unmatched bracket rather than 1/-1.

Practise this alongside similar single-pass traversal problems. The equilibrium index problem builds the same left-to-right scan instinct. Problems like finding symmetric pairs in an array build the hash-map and stack pattern recognition that appears across multiple coding-round question types.

Write both the stack and counter versions from scratch until you can produce them in under five minutes without looking anything up. That is the standard for a coding section under time pressure, where you do not get to Google edge cases mid-exam.

The same stack logic that validates {[()]} in a placement coding round is what parses JSON bracket structure in LLM API responses. If you want to see that in practice as a working project, TinkerLLM puts live API calls in your hands for ₹299, and the resulting parser or structured-output validator is something you can actually show in an interview when a recruiter asks what you have shipped.