Back to Study Material Data Structures and Algorithms

Balanced Parentheses

The balanced parentheses problem asks whether every opening bracket in a string has a corresponding closing bracket of the same type, and whether they are ...

Balanced Parentheses

Checking Bracket Balance Using a Stack

The balanced parentheses problem asks whether every opening bracket in a string has a corresponding closing bracket of the same type, and whether they are properly nested. This is a foundational stack problem that appears in compilers, text editors, code linters, and virtually every technical interview.

The algorithm uses a single stack. Scan the input string character by character from left to right. If the character is an opening bracket, specifically (, [, or {, push it onto the stack. If the character is a closing bracket, check whether the stack is empty. If it is empty, the string is unbalanced because there is no matching opener, so return false immediately. If the stack is not empty, pop the top element and verify that it matches the current closing bracket: ) must match (, ] must match [, and } must match {. If the pair does not match, return false. If the pair matches, continue scanning. After processing all characters, return true only if the stack is empty. A non-empty stack means some opening brackets were never closed.

Time complexity is O(n) where n is the length of the string, since each character is processed exactly once. Space complexity is O(n) in the worst case, occurring when the entire string consists of opening brackets all pushed onto the stack before any closing bracket is seen.

A common variant asks for the minimum number of bracket additions needed to balance a string. Maintain a counter for unmatched opening brackets and a counter for unmatched closing brackets. For each character, a closing bracket either matches a pending opener (decrement the open counter) or adds to unmatched closers (increment the close counter). The answer is the sum of both counters after scanning.

Worked example: check whether the string { [ ( ) ] } is balanced. Push {, push [, push (. Encounter ): pop (, match confirmed. Encounter ]: pop [, match confirmed. Encounter }: pop {, match confirmed. Stack is empty, return true.

Interview tip: handle the three bracket types in a lookup map rather than chained if-else statements. Writing something like matching = {')': '(', ']': '[', '}': '{'} and checking whether the popped value equals matching[char] is cleaner and easier to extend to new bracket types.

Variants: Minimum Additions and Longest Valid Substring

Once you master the basic balance check, interviewers often present harder variants that require tracking more information during the scan. Two of the most common are minimum bracket additions to fix an unbalanced string and the longest valid parentheses substring.

For minimum additions, consider only standard parentheses for simplicity. Maintain two counters: open_needed counts the number of unmatched closing parentheses seen so far, and close_needed counts unmatched opening parentheses. Scan left to right. For each ( encountered, increment close_needed. For each ) encountered, if close_needed is greater than zero, decrement it (this ) matched a previous (); otherwise increment open_needed because this ) has no opener. After the scan, the minimum number of additions is open_needed plus close_needed. This runs in O(n) time and O(1) space.

For longest valid parentheses, use a stack initialized with -1 as a base sentinel. Scan left to right. For each ( push its index. For each ) pop the stack. If the stack is empty after popping, push the current index as a new base. Otherwise, update the maximum length as the current index minus the value now on top of the stack. This approach works because the sentinel tracks the starting boundary of the current valid substring.

Time complexity for longest valid parentheses is O(n). Space complexity is O(n) in the worst case when all characters are opening parentheses and are pushed onto the stack.

An alternative O(n) time and O(1) space solution for longest valid parentheses uses two passes: left to right counting left and right brackets and resetting when rights exceed lefts, then right to left with the same logic. The maximum valid length found in either pass is the answer.

Worked example for longest valid: string ) ( ( ) ) ( ). Initialize stack with -1. Index 0, ): pop -1, stack empty, push 0. Index 1, (: push 1. Index 2, (: push 2. Index 3, ): pop 2, stack top is 1, length = 3-1 = 2. Index 4, ): pop 1, stack top is 0, length = 4-0 = 4. Index 5, (: push 5. Index 6, ): pop 5, stack top is 0, length = 6-0 = 6. Maximum is 6.

Interview tip: for the longest valid parentheses problem, clarify whether the input contains only parentheses or other characters too. Other characters always break a valid substring, which simplifies boundary detection.

Generalized Bracket Matching in Compiler Design

In real compilers and interpreters, bracket matching extends beyond checking source code strings to validating nested language constructs such as function calls, array subscripts, template parameters, and block statements. Understanding how compilers handle this gives context for why the stack-based algorithm is so fundamental.

A lexer tokenizes source code into a stream of tokens. The parser then validates the structure of these tokens against a grammar. For bracket matching, the parser maintains a stack of expected closing tokens. When a function call opening token is seen, the corresponding closing token is pushed onto an expectation stack. As the parser advances through tokens, it checks whether the next closing token matches the top of the expectation stack. If it does, the stack is popped. If it does not, the parser generates a syntax error pinpointing the mismatch location.

Error recovery is an important extension. A simple matching algorithm aborts at the first mismatch, but production compilers attempt to continue parsing after an error to report as many distinct errors as possible in a single compilation run. Common recovery strategies include discarding tokens until a synchronization point such as a semicolon is found, or popping the stack until a matching opener is found and resuming from there.

Nested template parameters in languages like C++ create ambiguous token streams because the greater-than character serves as both a comparison operator and a closing template bracket. Modern C++ compilers use context-sensitive parsing to distinguish >> in vector<vector<int>> from the right-shift operator, a non-trivial extension of basic bracket matching.

Worked example: the expression func(arr[i], obj.method()) is tokenized as func, (, arr, [, i, ], ,, obj, ., method, (, ), ). The bracket-checking stack sees ( from func call and pushes it, sees [ and pushes it, sees ] and matches [, sees ( from method and pushes it, sees ) and matches (, sees ) and matches the outer (, stack empty, expression is valid.

Interview tip: when discussing compiler applications in an interview, mention error recovery as an important real-world consideration beyond correctness checking. It shows awareness that production systems must handle malformed input gracefully.