patternpythonMinor
Balanced Parentheses checker in Python
Viewed 0 times
balancedparenthesescheckerpython
Problem
I'd appreciate feedback on the code itself (style, performance optimization (both space and time)), and also on the algorithm (because I think this is typically implemented using a stack).
The assumption I'm making here is that there are only two constraints to having balanced parentheses; one is that there be the same number of opening and closing parentheses, the other one that there not be at any point more closing parentheses than opening ones.
With this in mind, I implement my balanced parentheses checker using a simple counter, which is incremented with each opening paren, and decremented with each closing paren.
The two "checks" within the function are that the counter never go negative (return False if it does at any point), and that at the end the counter be 0.
The assumption I'm making here is that there are only two constraints to having balanced parentheses; one is that there be the same number of opening and closing parentheses, the other one that there not be at any point more closing parentheses than opening ones.
With this in mind, I implement my balanced parentheses checker using a simple counter, which is incremented with each opening paren, and decremented with each closing paren.
The two "checks" within the function are that the counter never go negative (return False if it does at any point), and that at the end the counter be 0.
def paren_checker(string):
counter = 0
for c in string:
if c == '(':
counter += 1
elif c == ')':
counter -= 1
if counter < 0:
return False
if counter == 0:
return True
return FalseSolution
Here is a somewhat improved version of the algorithm that allows for the three types:
Of course, this still doesn't cover the case of
def add_vectors(a, b):
for i, x in enumerate(b):
a[i] += x # a is a list, so it supports item assignment
return a
def is_balanced(string):
# ( [ {
counts = [0, 0, 0]
# dict of tuples to add based on char (like a switch statement)
d = {'(': ( 1, 0, 0), '[': ( 0, 1, 0), '{': ( 0, 0, 1),
')': (-1, 0, 0), ']': ( 0,-1, 0), '}': ( 0, 0,-1)}
for char in string:
try:
counts = add_vectors(counts, d[char])
except KeyError: # char is not in dict, so it isn't '(', '{', etc.
continue
if -1 in counts: # close without open
return False
return counts == [0, 0, 0] # will resolve to initial state if correctOf course, this still doesn't cover the case of
{[}] as is common in non-stack implementations.Code Snippets
def add_vectors(a, b):
for i, x in enumerate(b):
a[i] += x # a is a list, so it supports item assignment
return a
def is_balanced(string):
# ( [ {
counts = [0, 0, 0]
# dict of tuples to add based on char (like a switch statement)
d = {'(': ( 1, 0, 0), '[': ( 0, 1, 0), '{': ( 0, 0, 1),
')': (-1, 0, 0), ']': ( 0,-1, 0), '}': ( 0, 0,-1)}
for char in string:
try:
counts = add_vectors(counts, d[char])
except KeyError: # char is not in dict, so it isn't '(', '{', etc.
continue
if -1 in counts: # close without open
return False
return counts == [0, 0, 0] # will resolve to initial state if correctContext
StackExchange Code Review Q#153078, answer score: 4
Revisions (0)
No revisions yet.