The Self-Taught Computer Scientist

Data Structures
124
A better way to solve this problem is to use a stack. First, you iterate through each character in the 
string, and if a parenthesis is open, you put it on the stack. If it is closed, you check to see whether 
an open parenthesis is already on the stack. If there isn’t, it means the string is not balanced. If there 
is, you pop an open parenthesis off the stack. If there are an equal number of opening and closing 
parentheses in the string, the stack will be empty at the end of your loop. If the stack is not empty, 
then there are not equal numbers of opening and closing parentheses.
Let’s check out the code:
def check_parentheses(a_string):
stack = []
for c in a_string:
if c == "(":
stack.append(c)
if c == ")":
if len(stack) == 0:
return False
else:
stack.pop()
return len(stack) == 0
Your 
check_parentheses
function accepts the string to check for balanced parentheses as a 
parameter:
def check_parentheses(a_string):
Inside your function, you create a stack using a list:
stack = []
You use a 
for
loop to iterate through the characters in 
a_string
:
for c in a_string:
If the character is an opening parenthesis, you push it onto your stack:
if c == "(":
stack.append(c)
If the symbol is a closing parenthesis and the stack is empty, you return 
False
because there is no 
matching opening parenthesis on your stack, which means the string is not balanced. If there are 
opening parentheses in the stack, you pop one off to match the closing parenthesis.
if c == ")":
if len(stack) == 0:
return False
else:
stack.pop()

---

Chapter 11 Stacks
125
Once your 
for
loop finishes, you return whether or not the length of your stack is zero:
return len(stack) == 0
If your function returns 
True
, the parentheses are balanced; otherwise, they are not.
Understanding how to solve this problem is not just useful for technical interviews. The compilers 
for languages like Python and Java have code like this for parsing and evaluating expressions. If you 
ever need to write your own programming language or write code to parse data with opening and 
closing symbols, you can write code like this to evaluate it.
Vocabulary