Editor

Python Program to Check Balanced Parentheses Using a Stack

Intermediate · Data structures

An expression has balanced brackets when every opening bracket, (, [ or {, is closed by the matching kind in the right order, so "{[()]}" is balanced but "(]" and "((a)" are not. A stack is the natural tool: push each opening bracket, and when a closing bracket arrives, the bracket on top of the stack must be its partner.

Program

balanced_parentheses.py
def is_balanced(expression):
pairs = {")": "(", "]": "[", "}": "{"} # each closer and its opener
stack = []
for ch in expression:
if ch in "([{":
stack.append(ch) # push every opening bracket
elif ch in ")]}":
if len(stack) == 0:
return False # a closer with nothing to close
if stack.pop() != pairs[ch]:
return False # closed by the wrong kind
return len(stack) == 0 # anything left was never closed
tests = ["(a + b) * [c - d]", "{[()()]}", "((a + b)", "(a + b]", "a + b)", ""]
for expr in tests:
if is_balanced(expr):
print(f'"{expr}" is balanced')
else:
print(f'"{expr}" is not balanced')
Output
"(a + b) * [c - d]" is balanced
"{[()()]}" is balanced
"((a + b)" is not balanced
"(a + b]" is not balanced
"a + b)" is not balanced
"" is balanced

How it works

  1. The stack holds the opening brackets that have not been closed yet, with the most recent one on top.
  2. Each opening bracket is pushed, and each closing bracket must match the bracket popped from the top of the stack, which pairs looks up: pairs[")"] is "(".
  3. A closing bracket that arrives when the stack is empty, like the ) in "a + b)", has nothing to close, so the expression is not balanced.
  4. At the end the stack must be empty, and in "((a + b)" one ( is left over, so that one is not balanced either.
  5. Letters and operators are skipped, and the empty string counts as balanced because it has nothing to match.

Other ways to write it

Finding where the problem is

Finding where the problem is
def check(expression):
pairs = {")": "(", "]": "[", "}": "{"}
stack = [] # holds (bracket, position) pairs
for pos, ch in enumerate(expression):
if ch in "([{":
stack.append((ch, pos))
elif ch in ")]}":
if not stack or stack[-1][0] != pairs[ch]:
return f"unexpected {ch} at position {pos}"
stack.pop()
if stack:
return f"{stack[-1][0]} at position {stack[-1][1]} is never closed"
return "balanced"
for expr in ["{[()]}", "(a + b]", "((a + b)"]:
print(expr, "->", check(expr))
Output
{[()]} -> balanced
(a + b] -> unexpected ] at position 6
((a + b) -> ( at position 0 is never closed

Storing each bracket together with its position lets the program say exactly which character is wrong, the way a code editor highlights an unmatched bracket.

By removing pairs

By removing pairs
for expr in ["{[()()]}", "{[(])}"]:
text = expr
while "()" in text or "[]" in text or "{}" in text:
text = text.replace("()", "").replace("[]", "").replace("{}", "")
print(expr, "is balanced" if text == "" else "is not balanced")
Output
{[()()]} is balanced
{[(])} is not balanced

Deleting matched pairs like () over and over leaves an empty string only when the brackets are balanced, which is short to write but slower, and it only works on strings made of brackets alone.

Try it yourself

Add angle brackets < and > as a fourth kind of pair.

Edit the program above and press Run, or open it in the full editor to save it and share it. To watch it run line by line, open it in the visualizer.

Related programs

All Python programs · CBSE class 12 practical file · Python exercises