Python Programming

Let us try to look at an example application where you can try to apply list methods.

Let’s assume that you can have expressions that are made up of only open or closing parentheses, i.e. ( and ).

Let’s say you want to check whether the parentheses in an expression are balanced (has the same number of opening and closing parenthesis, and in the correct position).

Examples of balanced parentheses:

• ()
• (())
• ()()()
• ()(())

Examples of imbalanced parentheses:

• (
• (()
• )(
• ()())
• )()(

Write a function is_parenthesis_balanced() that takes a str consisting of only parenthesis (or an empty string), and returns True if the parentheses are balanced, and False otherwise. An empty string should also return True.

A stack solution

One possible solution is to use a data structure called stacks to keep track of the opening parentheses currently seen.

A stack is like a list, but is constrained so that you can only add new elements to the end of a list, and you can only remove elements from the end of a list (first in last out). Think of stacking lego blocks - you are only allowed to put things on top of a stack, and can only remove items from the top of a stack.

A possible algorithm could be to go through each character in sequence:

• If it is an opening parenthesis (, add the character to the stack, and continue to the next character.
• If it is a closing parenthesis ), then you would expect to have an opening parenthesis on the stack if this were a balanced expression.
  • If there is nothing on the stack, this means that the expression is imbalanced, and you can immediately return False.
  • If there is a ( on the stack, then you can pop the latest ( off the stack. This opening parenthesis is paired with the closing parenthesis that you have just seen. Then continue on with the next character.
• Once you are at the end of the string, then you would expect the stack to be empty (all parentheses are paired up). In this case, it means that the expression is balanced. If the stack is not empty, then there are some extra open parentheses, which means the expression is imbalanced.

You could of course increment/decrement a counter instead to track the number of open parenthesis, but try implementing this stack version instead as a practice. This stack method is more useful if you were to extend the program to incorporate square brackets or curly braces e.g. (([{}][])), but I wanted to keep this exercise simple! You can try this in your spare time though as an extra challenge! 💪😃

Sample usage

>>> is_parenthesis_balanced("()")
True
>>> is_parenthesis_balanced("(()(()))")
True
>>> is_parenthesis_balanced("())")
False
>>> is_parenthesis_balanced(")(()")
False
>>> is_parenthesis_balanced("")
True