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**

- Python Basics: Make predictions
- Function Tracing
- Iteration Practice: write functions

3.1`length`

3.2`allSameVowels`

3.3`guessingGame`

3.4`replaceVowelSequences`

3.5 Number tables:`hasIncreasingRows`

- Data Structures

4.1 Rotate lists

4.2 Memory diagrams

4.3 Same keys

4.4 Dictionary Inversion - Working with music albums data
- Recursion Practice

6.1 Wacky tracing

6.2`mult`

6.3`integer`

- Challenge: Balancing Act

7.1`isBracket`

7.2`filterBrackets`

7.3`areBracketsBalanced`

7.4 Super Challenge: Efficient Recursive Version

7.5`isBalanced`

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)
```

In [4]:

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

In [5]:

```
testTester(test)
```

In [6]:

```
a = int("4")
test = a * "4"
```

In [7]:

```
testTester(test)
```

In [8]:

```
def f(x):
print(x)
test = f(1)
```

In [9]:

```
testTester(test)
```

In [10]:

```
a = [[1], [3]]
test = a[0] + a[1]
```

In [11]:

```
testTester(test)
```

In [12]:

```
test = "Peter"[1:-1]
```

In [13]:

```
testTester(test)
```

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]:

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).

`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]:

In [23]:

```
length({'a':2, 'b': 3}) # should return 2
```

Out[23]:

In [24]:

```
length(range(40)) # should return 40
```

Out[24]:

In [25]:

```
length((1, )) # should return 1
```

Out[25]:

`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]:

In [29]:

```
allSameVowels("science") # returns False
```

Out[29]:

In [30]:

```
allSameVowels("tsk") # returns True
```

Out[30]:

In [31]:

```
allSameVowels("eye") # returns True
```

Out[31]:

In [32]:

```
allSameVowels("a") # returns True
```

Out[32]:

In [33]:

```
allSameVowels("disestablishmentarianism") # returns False
```

Out[33]:

`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()
```

`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'` |

`replaceVowelSequences`

¶In the following iteration tables, explain:

**State Variables:**What are the meanings of the state variables`resultSoFar`

and`inVowelSequence`

?*Answer:*`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?*Answer:*- 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 the previous
- If
`char`

is not a vowel, add`char`

to the end of`resultSoFar`

- If
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())
```

`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]:

In [41]:

```
hasIncreasingRows([[1, 4, 9], [0, 2], [1],
[-9, -1, 17, 89]]) # should return True
```

Out[41]:

In [42]:

```
hasIncreasingRows([[1, 1]]) # should return False
```

Out[42]:

In [43]:

```
hasIncreasingRows([[0, 1], [2, 1]]) # should return False
```

Out[43]:

In [44]:

```
hasIncreasingRows([[1, 3, 8, 9]]) # should return True
```

Out[44]:

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

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]:

In [47]:

```
test = ["a"]
rotate(test)
test # should be ["a"]
```

Out[47]:

In [48]:

```
test = []
rotate(test)
test # should be []
```

Out[48]:

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]:

In [51]:

```
a[1][0]
```

Out[51]:

In [52]:

```
a[1][1]
```

Out[52]:

In [53]:

```
a[2][1][0]
```

Out[53]:

In [54]:

```
b[0][0]
```

Out[54]:

In [55]:

```
c
```

Out[55]:

In [56]:

```
b[0] is a[1]
```

Out[56]:

In [57]:

```
b == a[2]
```

Out[57]:

In [58]:

```
b is a[2]
```

Out[58]:

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)
```

**Hint:** Draw a memory diagram of the lists.

In [60]:

```
a[0][0]
```

Out[60]:

In [61]:

```
b[0][0][0]
```

Out[61]:

In [62]:

```
a[1]
```

Out[62]:

In [63]:

```
b[0][1]
```

Out[63]:

In [64]:

```
b[0] is a
```

Out[64]:

In [65]:

```
b is a
```

Out[65]:

In [66]:

```
a
```

Out[66]:

In [67]:

```
a[0][1]
```

Out[67]:

In [68]:

```
a is a[0][1]
```

Out[68]:

In [69]:

```
a[0][1][0][1][1]
```

Out[69]:

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]:

In [72]:

```
haveSameKeys({}, {"a": 1}) # should return False
```

Out[72]:

In [73]:

```
haveSameKeys({"a": 1, "b": 2}, {"b": 7, "a": 4}) # should return True
```

Out[73]:

In [74]:

```
haveSameKeys({}, {}) # should return True
```

Out[74]:

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]:

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]:

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]:

In [79]:

```
invert({}) # should return {}
```

Out[79]:

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]:

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]:

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]:

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]:

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]:

`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]:

In [98]:

```
mult(4, 5) # should return 20
```

Out[98]:

In [99]:

```
mult(8, 1) # should return 8
```

Out[99]:

In [100]:

```
mult(3, 0) # should return 0
```

Out[100]:

In [101]:

```
mult(0, 3) # should return 0
```

Out[101]:

`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]:

In [105]:

```
integer("-9")
```

Out[105]:

In [106]:

```
integer("9831")
```

Out[106]:

In [107]:

```
integer("0")
```

Out[107]:

In [108]:

```
integer("-432")
```

Out[108]:

In [109]:

```
integer("007")
```

Out[109]:

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:

`[`

`}`

`{[}`

`{][}`

`([)]`

`((({}[]))`

`(({}((}))))`

`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]:

In [112]:

```
isBracket("}") # should return True
```

Out[112]:

In [113]:

```
isBracket(")") # should return True
```

Out[113]:

In [114]:

```
isBracket("(") # should return True
```

Out[114]:

In [115]:

```
isBracket("[") # should return True
```

Out[115]:

In [116]:

```
isBracket("]") # should return True
```

Out[116]:

In [117]:

```
isBracket("a") # should return False
```

Out[117]:

In [118]:

```
isBracket("9") # should return False
```

Out[118]:

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]:

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]:

`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.

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]:

In [133]:

```
areBracketsBalanced("{}") # should return True
```

Out[133]:

In [134]:

```
areBracketsBalanced("()") # should return True
```

Out[134]:

In [135]:

```
areBracketsBalanced("[]") # should return True
```

Out[135]:

In [136]:

```
areBracketsBalanced("(") # should return False
```

Out[136]:

In [137]:

```
areBracketsBalanced(")") # should return False
```

Out[137]:

In [138]:

```
areBracketsBalanced("}") # should return False
```

Out[138]:

In [139]:

```
areBracketsBalanced("[") # should return False
```

Out[139]:

In [140]:

```
areBracketsBalanced("{[}]") # should return False
```

Out[140]:

In [141]:

```
areBracketsBalanced("()[]") # should return True
```

Out[141]:

In [142]:

```
areBracketsBalanced("{[][()[]]}") # should return True
```

Out[142]:

In [143]:

```
areBracketsBalanced("(]{})") # should return False
```

Out[143]:

In [144]:

```
areBracketsBalanced("((((((((((((([)))))))))))))") # should return False
```

Out[144]:

In [145]:

```
areBracketsBalanced("(((((())))))") # should return True
```

Out[145]:

In [146]:

```
areBracketsBalanced("(([](((())))))") # should return True
```

Out[146]:

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]:

In [149]:

```
areBracketsBalanced("{}") # should return True
```

Out[149]:

In [150]:

```
areBracketsBalanced("()") # should return True
```

Out[150]:

In [151]:

```
areBracketsBalanced("[]") # should return True
```

Out[151]:

In [152]:

```
areBracketsBalanced("(") # should return False
```

Out[152]:

In [153]:

```
areBracketsBalanced(")") # should return False
```

Out[153]:

In [154]:

```
areBracketsBalanced("}") # should return False
```

Out[154]:

In [155]:

```
areBracketsBalanced("[") # should return False
```

Out[155]:

In [156]:

```
areBracketsBalanced("{[}]") # should return False
```

Out[156]:

In [157]:

```
areBracketsBalanced("()[]") # should return True
```

Out[157]:

In [158]:

```
areBracketsBalanced("{[][()[]]}") # should return True
```

Out[158]:

In [159]:

```
areBracketsBalanced("(]{})") # should return False
```

Out[159]:

In [160]:

```
areBracketsBalanced("((((((((((((([)))))))))))))") # should return False
```

Out[160]:

In [161]:

```
areBracketsBalanced("(((((())))))") # should return True
```

Out[161]:

In [162]:

```
areBracketsBalanced("(([](((())))))") # should return True
```

Out[162]:

`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]:

In [169]:

```
isBalanced("a = 4") # should return True
```

Out[169]:

In [170]:

```
isBalanced("num = ((3) + 2) - (1 + a[1]))") # should return False
```

Out[170]:

In [171]:

```
isBalanced("num = ((3) + 2) - (1 + a[1])") # should return True
```

Out[171]:

In [172]:

```
isBalanced("(a + }") # should return False
```

Out[172]:

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).