# CS 111: Final Review Questions¶

The following notebook is intended as practice problems for the final review. Some of these questions are intended as simple reminders of concepts we have learned. Some of the questions are similar in difficulty to exam questions. Others are more challenging but are good practice and will help solidify concepts.

Disclaimer: The questions in this notebook are not intended to be a comprehensive review. You may be asked questions beyond the topics covered in this notebook. Please also consult our Final Review document for the list of topics.

Table of Content

## 1. Python Basics: Make predictions¶

Predict the value and type of the following expressions stored in the variable test in Python. To show the contents of test, we have a small function below to show you the correct result, to confirm your predictions.

In [1]:
def testTester(test):
"""Helper function to show the correct result."""
print("The value of test:", test)
print("The type of test:", type(test))


How to proceed: Below you are given some assignment statement for the variable test. Do not run the code. Try to predict what is the value and type for test and then run two notebook cells at a time to confirm your guess.

In [2]:
test = (9, 2)[1:]

In [3]:
testTester(test)

The value of test: (2,)
The type of test: <class 'tuple'>

In [4]:
test = {"a": 1}["a"] + 2

In [5]:
testTester(test)

The value of test: 3
The type of test: <class 'int'>

In [6]:
a = int("4")
test = a * "4"

In [7]:
testTester(test)

The value of test: 4444
The type of test: <class 'str'>

In [8]:
def f(x):
print(x)
test = f(1)

1

In [9]:
testTester(test)

The value of test: None
The type of test: <class 'NoneType'>

In [10]:
a = [[1], [3]]
test = a[0] + a[1]

In [11]:
testTester(test)

The value of test: [1, 3]
The type of test: <class 'list'>

In [12]:
test = "Peter"[1:-1]

In [13]:
testTester(test)

The value of test: ete
The type of test: <class 'str'>


## 2. Function Tracing¶

Predict the output of the following function calls. Test your predictions with the cells below. Note that the function below does not produce anything meaningful but is used to test important concepts like conditionals, loops, and early return.

In [14]:
def starsAndStripes(word):
"""A non-sensical function simply created to test your understanding.
"""
if len(word) == 3:
return "*-*"
else:
i = 0
mystery = ""
while i < len(word):
if i % 2 == 1:
mystery += "*"
elif i == 4:
return mystery
else:
mystery += i * "-"
i = i + 1
return mystery

In [15]:
starsAndStripes("bed")

Out[15]:
'*-*'
In [16]:
starsAndStripes("A")

Out[16]:
''
In [17]:
starsAndStripes("id")

Out[17]:
'*'
In [18]:
starsAndStripes("test")

Out[18]:
'*--*'
In [19]:
starsAndStripes("wacky")

Out[19]:
'*--*'
In [20]:
starsAndStripes("longer")

Out[20]:
'*--*'

## 3. Iteration Practice¶

Below there are multiple functions for you to write. They all involve iteration (that is, loops) and iterables (values over which it's possible to iterate).

### 3.1 length¶

Write a function called length that implements the len function for any iterable (i.e., dictionary, list, tuple, range, string, ... etc.). Your function should accept any iterable and return its appropriate length. Obviously, your function cannot use len in its implementation.

In [21]:
def length(iterable):
"""A function that takes an iterable and returns its length.
"""
# Your code here
count = 0
for _ in iterable:
count += 1
return count

In [22]:
length([1, 2, 6])       # should return 3

Out[22]:
3
In [23]:
length({'a':2, 'b': 3}) # should return 2

Out[23]:
2
In [24]:
length(range(40))       # should return 40

Out[24]:
40
In [25]:
length((1, ))           # should return 1

Out[25]:
1

### 3.2 allSameVowels¶

Write a function called allSameVowels that returns True if the string contains all of the same vowels and False otherwise. If the word contains no vowels, then it is vacuously true that the string contains all of the same vowels. In this case, you should return True. Learn more about vacuous truths here if you are curious: https://en.wikipedia.org/wiki/Vacuous_truth.

In [26]:
def isVowel(let):
"""Helper function: returns true if a letter is a vowel.
"""
return let.lower() in "aeiou"

In [27]:
def allSameVowels(word):
"""Given a word, return True if all vowels are the same or there are no vowels.
"""
# Your code here
firstVowel = None
for let in word:
if isVowel(let):
if firstVowel is None:
firstVowel = let
elif firstVowel != let:
return False
return True

In [28]:
allSameVowels("kayak")      # returns True

Out[28]:
True
In [29]:
allSameVowels("science")    # returns False

Out[29]:
False
In [30]:
allSameVowels("tsk")        # returns True

Out[30]:
True
In [31]:
allSameVowels("eye")        # returns True

Out[31]:
True
In [32]:
allSameVowels("a")          # returns True

Out[32]:
True
In [33]:
allSameVowels("disestablishmentarianism") # returns False

Out[33]:
False

### 3.3 guessingGame¶

Write a function called guessingGame that chooses a random number between 1 and 100 (inclusive) and asks the user to guess the answer. Here's some sample output of how the game should work:

Guess a number between 1 and a 100: 50
Try a little lower

Guess a number between 1 and a 100: 25
Try a little higher

Guess a number between 1 and a 100: 35
Try a little lower

Guess a number between 1 and a 100: 30
Try a little lower

Guess a number between 1 and a 100: 28
Try a little higher

Guess a number between 1 and a 100: 29
You got it!


To get the random number for the user to guess, use random.randint(a, b) which chooses a random number between a and b, inclusive.

In [34]:
import random

def guessingGame():
"""A function that will first generate a random number between
1 and 100, and prompt the user to guess it by providing hints
along the way.
"""
# Your code here
num = random.randint(1, 100)
guess = None

while guess != num:
guess = int(input("Guess a number between 1 and a 100: "))
if guess > num:
print("Try a little lower\n")
elif guess < num:
print("Try a little higher\n")

print("You got it!")

In [35]:
guessingGame()

Guess a number between 1 and a 100:

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-35-e70ac9879ca5> in <module>
----> 1 guessingGame()

<ipython-input-34-f48d614b9ed5> in guessingGame()
11
12     while guess != num:
---> 13         guess = int(input("Guess a number between 1 and a 100: "))
14         if guess > num:
15             print("Try a little lower\n")

ValueError: invalid literal for int() with base 10: ''

### 3.4 replaceVowelSequences¶

Define a function replaceVowelSequences that takes a string as its single input, and returns a version of the string in which each sequence of consecutive vowels is replaced by the asterisk character, '*'. The following table shows the output of replaceVowelSequences for some input strings:

Input Output
'section' 's*ct*n'
'conscientious' 'c*nsc*nt*s'
'audacious' '*d*c*s'
'amnesia' '*mn*s*'
'strengths' 'str*ngths'
'wryly' 'wryly'

#### Some sample iteration tables for replaceVowelSequences¶

In the following iteration tables, explain:

• State Variables: What are the meanings of the state variables resultSoFar and inVowelSequence?

• resultSoFar is the prefix of the final result string determined by the characters processed so far.
• inVowelSequence indicates whether the current char is a vowel. It is helpful, because it can be used in the next row to determine if the previous character was a value.
• Iteration Rules:

• How is resultSoFar in a row determined from (1) char in that row (2) resultSoFar from the previous row and (3) inVowelSequence from the previous row?

• If char is a vowel:
• If the previous inVowelSequence is False, add '*' to the end of resultSoFar
• If the previous inVowelSequence is True, resultSoFar is unchanged
• If char is not a vowel, add char to the end of resultSoFar
• How is inVowelSequence in a row determined from char in that row?

Answer: inVowelSequence is True if char is a vowel and False otherwise.

char resultSoFar inVowelSequence
'' False
's' 's' False
'e' 's*' True
'c' 's*c' False
't' 's*ct' False
'i' 's*ct*' True
'o' 's*ct*' True
'n' 's*ct*n' False
char resultSoFar inVowelSequence
'' False
'a' '*' True
'u' '*' True
'd' '*d' False
'a' '*d*' True
'c' '*d*c' False
'i' '*d*c*' True
'o' '*d*c*' True
'u' '*d*c*' True
's' '*d*c*s' False
In [36]:
def isVowel(char):
"""Helper function: returns true if a letter is a vowel.
"""
return char.lower() in 'aeiou'


Now that you have analyzed the iteration table above and examined possible state variables, write a function called replaceVowelSequences.

In [37]:
def replaceVowelSequences(word):
"""A function that replaces the occurrences of vowels or consecutive vowels
with an asterisk.
"""
# Your code here
resultSoFar = ''
inVowelSequence = False
for char in word:
if isVowel(char):
if not inVowelSequence:
resultSoFar += '*'
inVowelSequence = True
else:
resultSoFar += char
inVowelSequence = False
return resultSoFar

In [38]:
def testReplaceVowelSequences(words):
"""Helper function to test the function outputs.
"""
for word in words:
print(f"replaceVowelSequences('{word}') => '{replaceVowelSequences(word)}'")

testReplaceVowelSequences('section conscientious audacious amensia strenghts wryly'.split())

replaceVowelSequences('section') => 's*ct*n'
replaceVowelSequences('conscientious') => 'c*nsc*nt*s'
replaceVowelSequences('audacious') => '*d*c*s'
replaceVowelSequences('amensia') => '*m*ns*'
replaceVowelSequences('strenghts') => 'str*nghts'
replaceVowelSequences('wryly') => 'wryly'


### 3.5 Number Tables: hasIncreasingRows¶

Let's define a number table as a list of lists whose inner lists contain numbers. Below is an example of such a table:

[[1, 2], [4, 5, 6]]


Write a function called hasIncreasingRows that takes a number table and returns True if all the rows in the table have increasing numbers and False otherwise. The table above would return True if passed to hasIncreasingRows because 1 and 2 are in increasing order and 4, 5, and 6 are in increasing order.

In [39]:
def hasIncreasingRows(numTable):
"""Given a number table, returns True if all the rows in the table
have increasing numbers and False otherwise
"""
# Your code here
for row in numTable:
prevNum = row[0]
for num in row[1:]:
if num <= prevNum:
return False
prevNum = num
return True

In [40]:
hasIncreasingRows([[1, 4], [2, 3]])      # should return True

Out[40]:
True
In [41]:
hasIncreasingRows([[1, 4, 9], [0, 2], [1],
[-9, -1, 17, 89]])    # should return True

Out[41]:
True
In [42]:
hasIncreasingRows([[1, 1]])              # should return False

Out[42]:
False
In [43]:
hasIncreasingRows([[0, 1], [2, 1]])      # should return False

Out[43]:
False
In [44]:
hasIncreasingRows([[1, 3, 8, 9]])        # should return True

Out[44]:
True

## 4. Data Structures¶

The following problems give you practice with lists and dictionaries. They are known as data structures, because they contain other values.

### 4.1 Rotate List¶

Write a function called rotate which takes a list and rotates if by one position. Given a list of elements, a rotation simply shifts all the elements in the list to the right by one position and places the last element at the front of the list. The function should mutate the list in place and not return a new list.
Hint: Use list methods such as pop and insert to mutate the list.

In [45]:
def rotate(lst):
"""Return a given list rotated by one position.
It does not create a new list.
"""
# Your code here
if lst == []: return
last = lst.pop()
lst.insert(0, last)
return lst

In [46]:
test = [1, 2, 3]
rotate(test)
test            # should be [3, 1, 2]

Out[46]:
[3, 1, 2]
In [47]:
test = ["a"]
rotate(test)
test            # should be ["a"]

Out[47]:
['a']
In [48]:
test = []
rotate(test)
test # should be []

Out[48]:
[]

### 4.2 Memory Diagrams¶

Consider the following snippet of code below.

In [49]:
a = [1, [3, 4]]
b = [[2]]
a.append(b)
b.insert(0, a[1])
c = a[1].pop(-1)
b[0].append(5)
b[1][0] = 6


Predict what the following expressions will evaluate to before evaluating.
Hint: Draw a memory diagram of the lists.

In [50]:
a[0]

Out[50]:
1
In [51]:
a[1][0]

Out[51]:
3
In [52]:
a[1][1]

Out[52]:
5
In [53]:
a[2][1][0]

Out[53]:
6
In [54]:
b[0][0]

Out[54]:
3
In [55]:
c

Out[55]:
4
In [56]:
b[0] is a[1]

Out[56]:
True
In [57]:
b == a[2]

Out[57]:
True
In [58]:
b is a[2]

Out[58]:
True

Here is another snippet of code.

In [59]:
a = [[1]]
b = []
b.append(a)
a[0].append(a)
a[0][1][0][0] = 2
b[0].append(3)


Predict what the following expressions will evaluate to before evaluating.
Hint: Draw a memory diagram of the lists.

In [60]:
a[0][0]

Out[60]:
2
In [61]:
b[0][0][0]

Out[61]:
2
In [62]:
a[1]

Out[62]:
3
In [63]:
b[0][1]

Out[63]:
3
In [64]:
b[0] is a

Out[64]:
True
In [65]:
b is a

Out[65]:
False
In [66]:
a

Out[66]:
[[2, [...]], 3]
In [67]:
a[0][1]

Out[67]:
[[2, [...]], 3]
In [68]:
a is a[0][1]

Out[68]:
True
In [69]:
a[0][1][0][1][1]

Out[69]:
3

### 4.3 Same keys¶

Write a function that determines whether two dictionaries have the same keys.

In [70]:
def haveSameKeys(dict1, dict2):
"""Return a boolean value indicating whether two dictionaries
have the same keys.
"""
# Your code here
return dict1.keys() == dict2.keys()

In [71]:
haveSameKeys({"a": 1, "b": 2}, {"a": 7, "b": 4})      # should return True

Out[71]:
True
In [72]:
haveSameKeys({}, {"a": 1})                            # should return False

Out[72]:
False
In [73]:
haveSameKeys({"a": 1, "b": 2}, {"b": 7, "a": 4})      # should return True

Out[73]:
True
In [74]:
haveSameKeys({}, {})                                  # should return True

Out[74]:
True

### 4.4 Dictionary Inversion¶

Consider dictionaries whose keys are names and whose values are the number of times those names appear in some text. Here's an example of such a dictionary:

{"Andy": 4, "Sohie": 2, "Peter": 2, "Carolyn": 3, "Eni": 3, "Lyn": 3}


Write a function that inverts the dictionary such that the keys are values and the values are keys. The names should be kept in a list. Here's what happens to the above dictionary when inverted:

{4: ["Andy"], 2: ["Sohie", "Peter"], 3: ["Carolyn", "Eni", "Lyn"]}


Write a function called invert which takes a dictionary and inverts it. The function should return a new dictionary and not mutate the original.

In [75]:
def invert(nameDict):
"""Returns a new dictionary where the values of the provided
nameDict dictionary parameter are converted to keys and the keys
to values.
"""
# Your code here
inversionDict = {}
for name in nameDict:
occurrence = nameDict[name]
if occurrence not in inversionDict:
inversionDict[occurrence] = [name]
else:
inversionDict[occurrence].append(name)
return inversionDict

In [76]:
invert({"Andy": 4, "Sohie": 2, "Peter": 2,
"Carolyn": 3, "Eni": 3, "Lyn": 3}) # should return {4: ['Andy'],
# 2: ['Sohie', 'Peter'],
# 3: ['Carolyn', 'Eni', 'Lyn']}

Out[76]:
{4: ['Andy'], 2: ['Sohie', 'Peter'], 3: ['Carolyn', 'Eni', 'Lyn']}
In [77]:
invert({"Andy": 1, "Sohie": 1, "Peter": 1,
"Carolyn": 1, "Eni": 1, "Lyn": 1}) # should return
# {1: ['Andy', 'Sohie', 'Peter', 'Carolyn', 'Eni', 'Lyn']}

Out[77]:
{1: ['Andy', 'Sohie', 'Peter', 'Carolyn', 'Eni', 'Lyn']}
In [78]:
invert({"Andy": 10, "Sohie": 5, "Peter": 15,
"Carolyn": 30, "Eni": 20, "Lyn": 25}) # should return
# {10: ['Andy'], 5: ['Sohie'],
# 15: ['Peter'], 30: ['Carolyn'],
# 20: ['Eni'], 25: ['Lyn']}

Out[78]:
{10: ['Andy'],
5: ['Sohie'],
15: ['Peter'],
30: ['Carolyn'],
20: ['Eni'],
25: ['Lyn']}
In [79]:
invert({}) # should return {}

Out[79]:
{}

## 5. Working With Music Albums Data¶

Consider the albums dictionary below whose keys are album names and whose values are dictionaries containing information about each album.

In [80]:
albums = {
"Blue": {
"artist": "Joni Mitchell",
"year": 1971,
"label": "Reprise",
"tracks": ["All I Want", "My Old Man", "Little Green", "Carey", "Blue", "California", "This Flight Tonight", "River", "A Case of You", "The Last Time I Saw Richard"]
},
"Houses of the Holy": {
"artist": "Led Zeppelin",
"year": 1973,
"label": "Atlantic",
"tracks": ["The Song Remains the Same", "The Rain Song", "Over the Hills and Far Away", "The Crunge", "Dancing Days", "D'yer Mak'er", "No Quarter", "The Ocean"]
},
"Jailbreak": {
"artist": "Thin Lizzy",
"year": 1976,
"label": "Vertigo",
"tracks": ["Jailbreak", "Angel from the Coast", "Running Back", "Romeo and the Lonely Girl", "Warriors", "The Boys Are Back in Town", "Fight or Fall", "Cowboy Song", "Emerald"]
},
"Diana": {
"artist": "Diana Ross",
"year": 1980,
"label": "Motown",
"tracks": ["Upside Down", "Tenderness", "Friend to Friend", "I'm Coming Out", "Have Fun (Again)", "My Old Piano", "Now That You're Gone", "Give Up"]
},
"Presence": {
"artist": "Led Zeppelin",
"year": 1976,
"label": "Swan Song",
"tracks": ["Achilles Last Stand", "For Your Life", "Royal Orleans", "Nobody's Fault but Mine", "Candy Store Rock", "Hots On for Nowhere", "Tea for One"]
}
}


Write a function that creates a list of all the unique artists in the albums dictionary.

In [81]:
def uniqueArtists(albums):
"""Return a list of unique artists from the given dictionary.
"""
# Your code here
artistList = []
for album in albums:
albumDict = albums[album]
artist = albumDict["artist"]
if artist not in artistList:
artistList.append(artist)
return artistList

In [82]:
uniqueArtists(albums) # should return ['Joni Mitchell', 'Led Zeppelin', 'Thin Lizzy', 'Diana Ross']

Out[82]:
['Joni Mitchell', 'Led Zeppelin', 'Thin Lizzy', 'Diana Ross']

Write a function that returns a list of all the albums with more than 8 tracks.

In [83]:
def moreThanEight(albums):
"""Return a list of album names that have more than 8 tracks.
"""
# Your code here
longAlbums = []
for album in albums:
albumDict = albums[album]
tracks = albumDict["tracks"]
if len(tracks) > 8:
longAlbums.append(album)
return longAlbums

In [84]:
moreThanEight(albums) # should return ['Blue', 'Jailbreak']

Out[84]:
['Blue', 'Jailbreak']

Write a function that returns a list of all the tracks that are single words.

In [85]:
def singleWords(albums):
"""Return a list of all the tracks that are single words
"""
# Your code here
singleWordAlbums = []
for album in albums:
albumDict = albums[album]
tracks = albumDict["tracks"]
for track in tracks:
if len(track.split()) == 1:
singleWordAlbums.append(track)
return singleWordAlbums

In [86]:
singleWords(albums) # should return ['Carey', 'Blue', 'California', 'River', 'Jailbreak', 'Warriors', 'Emerald', 'Tenderness']

Out[86]:
['Carey',
'Blue',
'California',
'River',
'Jailbreak',
'Warriors',
'Emerald',
'Tenderness']

Write a function that returns a dictionary whose keys are album years and whose values are a list of all the albums that came out in that year.

In [88]:
def albumYearDict(albums):
"""Return a dictionary whose keys are album years and whose values
are a list of all the albums that came out in that year.
"""
# Your code here
yearDict = {}
for album, albumDict in albums.items():
year = albumDict["year"]
if year not in yearDict:
yearDict[year] = [album]
else:
yearDict[year].append(album)
return yearDict

In [89]:
albumYearDict(albums) # should return {1971: ['Blue'], 1973: ['Houses of the Holy'], 1976: ['Jailbreak', 'Presence'], 1980: ['Diana']}

Out[89]:
{1971: ['Blue'],
1973: ['Houses of the Holy'],
1976: ['Jailbreak', 'Presence'],
1980: ['Diana']}

## 6. Recursion Practice¶

### 6. 1 Wacky Tracing¶

Consider the following code below. Predict what happens when wacky is invoked with the following arguments. Check your answers by evaluating the cell block.

In [90]:
def wacky(word):
"""Non-sensical recursive function for practice.
"""
if word == "":
return ":)"
elif word[0] == word[-1]:
return "^" + wacky(word[1:-1]) + "^"
else:
return "->" + wacky(word[1:])

In [91]:
wacky("")

Out[91]:
':)'
In [92]:
wacky("a")

Out[92]:
'^:)^'
In [93]:
wacky("eye")

Out[93]:
'^^:)^^'
In [94]:
wacky("test")

Out[94]:
'^->^:)^^'
In [95]:
wacky("abc")

Out[95]:
'->->^:)^'

### 6.2 mult¶

Write a fruitful recursive function called mult that takes two numbers and returns the result of the two numbers multiplied. Certainly this is easy to do with * operator. But we can think about multiplication as a recursive form of addition. This problem is very similar to factorial. In this function, only use the +, -, and == operators and no other operators. You can assume the inputs are all non-negative integers.

In [96]:
def mult(num1, num2):
"""A recursive function that generates the product of its two parameters.
"""
# Your code here
if num2 == 0 or num1 == 0:
return 0
else:
return num1 + mult(num1, num2 - 1)

In [97]:
mult(3, 2) # should return 6

Out[97]:
6
In [98]:
mult(4, 5) # should return 20

Out[98]:
20
In [99]:
mult(8, 1) # should return 8

Out[99]:
8
In [100]:
mult(3, 0) # should return 0

Out[100]:
0
In [101]:
mult(0, 3) # should return 0

Out[101]:
0

### 6.3 integer¶

Write a fruitful recursive function called integer that should implement the functionality of the built-in function int. For example, integer("314") should return 314 as an int. integer should also handle negative numbers as well. The behavior of integer is undefined for strings that are not whole numbers such as decimal numbers or strings with letters. You should use the dictionary numMapping to convert each digit to its actual integer representation.

In [102]:
numMapping = {
"0": 0,
"1": 1,
"2": 2,
"3": 3,
"4": 4,
"5": 5,
"6": 6,
"7": 7,
"8": 8,
"9": 9
}

In [103]:
def integer(numStr):
"""A recursive function that will convert an appropriate string to an integer.
"""
# Your code here
if numStr == "":
return 0
elif numStr[0] == "-":
return -1 * integer(numStr[1:])
else:
digit = numMapping[numStr[0]]
return digit * 10 ** (len(numStr) - 1) + integer(numStr[1:])

In [104]:
integer("314")

Out[104]:
314
In [105]:
integer("-9")

Out[105]:
-9
In [106]:
integer("9831")

Out[106]:
9831
In [107]:
integer("0")

Out[107]:
0
In [108]:
integer("-432")

Out[108]:
-432
In [109]:
integer("007")

Out[109]:
7

## 7. Challenge: Balancing Act¶

This is a challenging exercise, particularly for the second to last function areBracketsBalanced. The earlier functions are more reasonable and we expect you to be able to complete those on the exam. areBracketsBalanced is more of a problem-set-like question but is good recursion practice.

The goal is to be able to check whether a given line of code has a balanced set of parentheses. We know from working on problem sets that a stray parenthesis can lead to a syntax error. Python, like human language, has certain syntatical rules that must be obeyed in order to create a well-formed snippet of Python code. One of the rules is that every open bracket (i.e., {, (, [) must be matched by its respective closing bracket (i.e., }, ), ]). For example, the following bit of Python code demonstrates well-balanced brackets:

a = len([1, 2, 3] * 4)

If we remove all the characters except the brackets, we get ([]). It's easy to see from this view that all the brackets are balanced.

Brackets are balanced if they meet two specific criteria:

• Every open bracket can be matched by a corresponding closed bracket somewhere to its right.
• The subset within any matched pair of brackets must also be balanced.

For example, [{]} is not balanced because even though each open bracket has a corresponding bracket to its right because the second criteria is not satisfied. Within a matching pair of brackets, say [{], we have an unmatched bracket {.

Before continuing on you should check whether you understand what sequence of brackets is balanced and what is not balanced.

The following are balanced:

''
{}
[]
()
{()}
[]{}
{[]()[(){}]}

The following are not balanced:

[
}
{[}
{][}
([)]
((({}[]))
(({}((}))))

### 7.1 isBracket¶

To start out, let's write a simple function that determines whether a character is indeed a bracket. This should be very similar to isVowel.

In [110]:
def isBracket(char):
"""Return a boolean to indicate if a character is a bracket.
"""
# Your code here
return char in "(){}[]"

In [111]:
isBracket("{") # should return True

Out[111]:
True
In [112]:
isBracket("}") # should return True

Out[112]:
True
In [113]:
isBracket(")") # should return True

Out[113]:
True
In [114]:
isBracket("(") # should return True

Out[114]:
True
In [115]:
isBracket("[") # should return True

Out[115]:
True
In [116]:
isBracket("]") # should return True

Out[116]:
True
In [117]:
isBracket("a") # should return False

Out[117]:
False
In [118]:
isBracket("9") # should return False

Out[118]:
False

### 7.2 filterBrackets¶

#### Iterative Version¶

Write a function that takes a line of code represented as a string and returns a string of only its brackets. Use the function isBracket that you wrote before. Use iteration to solve this problem.

In [119]:
def filterBrackets(string):
"""An iterative function that takes a line of code represented as a string
and returns a string of only its brackets.
"""
# Your code here
result = ""
for char in string:
if isBracket(char):
result += char
return result

In [120]:
filterBrackets("((3 + 2) * 4)") # should return '(())'

Out[120]:
'(())'
In [121]:
filterBrackets("{'a':[1, 2], 'b':[(1, ), [3, 4]]}") # should return '{[][()[]]}'

Out[121]:
'{[][()[]]}'
In [122]:
filterBrackets("(") # should return '('

Out[122]:
'('
In [123]:
filterBrackets("(e]{a}ce)") # should return '(]{})'

Out[123]:
'(]{})'
In [124]:
filterBrackets("testing") # should return the empty string

Out[124]:
''

#### Recursive Version¶

Write a recursive implementation of filterBrackets. You should again make use of isBracket from before.

In [125]:
def filterBrackets(string):
"""A recursive function that takes a line of code represented as a string
and returns a string of only its brackets.
"""
# Your code here
if string == "":
return ""
elif isBracket(string[0]):
return string[0] + filterBrackets(string[1:])
else:
return filterBrackets(string[1:])

In [126]:
filterBrackets("((3 + 2) * 4)") # should return '(())'

Out[126]:
'(())'
In [127]:
filterBrackets("{'a':[1, 2], 'b':[(1, ), [3, 4]]}") # should return '{[][()[]]}'

Out[127]:
'{[][()[]]}'
In [128]:
filterBrackets("(") # should return '('

Out[128]:
'('
In [129]:
filterBrackets("(e]{a}ce)") # should return '(]{})'

Out[129]:
'(]{})'
In [130]:
filterBrackets("testing") # should return the empty string

Out[130]:
''

### 7.3 areBracketsBalanced¶

After we have filtered our code to keep only brackets, we now need to write a function to determine whether a string of brackets is indeed balanced.

#### Recursive Version¶

Let's write a recursive version of areBracketsBalanced. Any attempt at a recursive function should begin with an analysis of what is recursive about the problem.

Here's one way to visualize whether a sequence of brackets is balanced. Consider the string below:

'[{}()]' # remove any existing balanced pair in the string (i.e., '{}')
'[()]'   # remove any existing balanced pair in the string (i.e., '()')
'[]'     # remove any existing balanced pair in the string (i.e., '[]')
''       # the string is balanced

Consider an alternative

'[(){]'  # remove any existing balanced pair in the string (i.e., '()')
'[{]'    # no balanced pairs -> not balanced

Using this logic, implement areBracketsBalanced. You will likely want to use the .index method and the in operator to check if a balanced pair exists in the string.

In [131]:
def areBracketsBalanced(brackets):
"""A recursive function to determine whether a string of brackets is indeed balanced.
It returns a boolean.
"""
# Your code here
if brackets == "":
return True
else:
for pair in ["{}", "()", "[]"]:
if pair in brackets:
i = brackets.index(pair)
return areBracketsBalanced(brackets[:i] + brackets[i + 2:])
return False

In [132]:
areBracketsBalanced("") # should return True

Out[132]:
True
In [133]:
areBracketsBalanced("{}") # should return True

Out[133]:
True
In [134]:
areBracketsBalanced("()") # should return True

Out[134]:
True
In [135]:
areBracketsBalanced("[]") # should return True

Out[135]:
True
In [136]:
areBracketsBalanced("(") # should return False

Out[136]:
False
In [137]:
areBracketsBalanced(")") # should return False

Out[137]:
False
In [138]:
areBracketsBalanced("}") # should return False

Out[138]:
False
In [139]:
areBracketsBalanced("[") # should return False

Out[139]:
False
In [140]:
areBracketsBalanced("{[}]") # should return False

Out[140]:
False
In [141]:
areBracketsBalanced("()[]") # should return True

Out[141]:
True
In [142]:
areBracketsBalanced("{[][()[]]}") # should return True

Out[142]:
True
In [143]:
areBracketsBalanced("(]{})") # should return False

Out[143]:
False
In [144]:
areBracketsBalanced("((((((((((((([)))))))))))))") # should return False

Out[144]:
False
In [145]:
areBracketsBalanced("(((((())))))") # should return True

Out[145]:
True
In [146]:
areBracketsBalanced("(([](((())))))") # should return True

Out[146]:
True

### 7.4 Super Challenge: Efficient Recursive Version¶

Do not attempt this unless you have a lot of free time. This is a really hard problem and you should put your focus to studying other course content. Nevertheless, this is a great challenge and you actually have all the tools to complete this problem. Note this would be a hard problem even in CS230! You will not find anything close to this difficulty on the final.

Your solution above likely made use of the in operator. The in operator can become expensive if used over and over again (you can learn more about this in CS231) either in a loop or in a series of recursive calls. In this super challenge, write an recursive implementation of areBracketsBalanced without using a loop, the in operator, or the index method. areBracketsBalanced should call a helper function that does the bulk of the work recursively. The goal of this recursive helper function should be to reduce the input string down to the empty string by removing balanced pairs.

In [147]:
def areBracketsBalanced(code):
# Your code here
result = areBracketsBalancedHelper(code)
return result == ""

def areBracketsMatched(firstChar, secondChar):
return firstChar == "{" and secondChar == "}" or \
firstChar == "(" and secondChar == ")" or \
firstChar == "[" and secondChar == "]"

def areBracketsBalancedHelper(brackets):
if brackets == "":
return brackets
else:
firstChar = brackets[0]
subStr = areBracketsBalancedHelper(brackets[1:])

# attempt to excise the brackets if balanced
if len(subStr) > 0:
secondChar = subStr[0]
if areBracketsMatched(firstChar, secondChar):
return subStr[1:] # excise balanced parentheses

return firstChar + subStr

In [148]:
areBracketsBalanced("") # should return True

Out[148]:
True
In [149]:
areBracketsBalanced("{}") # should return True

Out[149]:
True
In [150]:
areBracketsBalanced("()") # should return True

Out[150]:
True
In [151]:
areBracketsBalanced("[]") # should return True

Out[151]:
True
In [152]:
areBracketsBalanced("(") # should return False

Out[152]:
False
In [153]:
areBracketsBalanced(")") # should return False

Out[153]:
False
In [154]:
areBracketsBalanced("}") # should return False

Out[154]:
False
In [155]:
areBracketsBalanced("[") # should return False

Out[155]:
False
In [156]:
areBracketsBalanced("{[}]") # should return False

Out[156]:
False
In [157]:
areBracketsBalanced("()[]") # should return True

Out[157]:
True
In [158]:
areBracketsBalanced("{[][()[]]}") # should return True

Out[158]:
True
In [159]:
areBracketsBalanced("(]{})") # should return False

Out[159]:
False
In [160]:
areBracketsBalanced("((((((((((((([)))))))))))))") # should return False

Out[160]:
False
In [161]:
areBracketsBalanced("(((((())))))") # should return True

Out[161]:
True
In [162]:
areBracketsBalanced("(([](((())))))") # should return True

Out[162]:
True

### 7.5 isBalanced¶

The last stage is to combine the filtering and the balance checking into one predicate that can determine whether a string has a set of balanced parentheses. This function is straightforward and should simply call the functions you wrote earlier to determine whether a line of code contains balanced parentheses.

In [167]:
def isBalanced(code):
# Your code here
brackets = filterBrackets(code)
return areBracketsBalanced(brackets)

In [168]:
isBalanced("{'a':[1, 2], 'b':[(1, ), [3, 4]]}") # should return True

Out[168]:
True
In [169]:
isBalanced("a = 4") # should return True

Out[169]:
True
In [170]:
isBalanced("num = ((3) + 2) - (1 + a[1]))") # should return False

Out[170]:
False
In [171]:
isBalanced("num = ((3) + 2) - (1 + a[1])") # should return True

Out[171]:
True
In [172]:
isBalanced("(a + }") # should return False

Out[172]:
False

In essence, you have done some of the work of what Python needs to do to check whether your code is valid Python. You can learn a lot more about how we can validate the syntax of a program in a course like CS251 (Programming Languages) or CS301 (Compilers).