Lab 13: Final Review
Due by 11:59pm on Tuesday, August 8.
Starter Files
Download lab13.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the Ok autograder.
Optional Questions
All questions on this assignment are optional. There is no submission component for this lab.
Trees
Q1: Prune Min
Write a function that prunes a Tree t mutatively. t and its branches
always have zero or two branches. For the trees with two branches, reduce the
number of branches from two to one by keeping the branch that has the smaller
label value. Do nothing with trees with zero branches.
Prune the tree in a direction of your choosing (top down or bottom up). The result should be a linear tree.
def prune_min(t):
"""Prune the tree mutatively.
>>> t1 = Tree(6)
>>> prune_min(t1)
>>> t1
Tree(6)
>>> t2 = Tree(6, [Tree(3), Tree(4)])
>>> prune_min(t2)
>>> t2
Tree(6, [Tree(3)])
>>> t3 = Tree(6, [Tree(3, [Tree(1), Tree(2)]), Tree(5, [Tree(3), Tree(4)])])
>>> prune_min(t3)
>>> t3
Tree(6, [Tree(3, [Tree(1)])])
"""
if _____________:
return
_____________
_____________
if _____________:
_____________
else:
_____________
Use Ok to test your code:
python3 ok -q prune_minQ2: Reverse Other
Write a function reverse_other that mutates the tree such that labels on
every other (odd-depth) level are reversed. For example,
Tree(1,[Tree(2, [Tree(4)]), Tree(3)]) becomes Tree(1,[Tree(3, [Tree(4)]), Tree(2)]).
Notice that the nodes themselves are not reversed; only the labels are.
def reverse_other(t):
"""Mutates the tree such that nodes on every other (odd-depth)
level have the labels of their branches all reversed.
>>> t = Tree(1, [Tree(2), Tree(3), Tree(4)])
>>> reverse_other(t)
>>> t
Tree(1, [Tree(4), Tree(3), Tree(2)])
>>> t = Tree(1, [Tree(2, [Tree(3, [Tree(4), Tree(5)]), Tree(6, [Tree(7)])]), Tree(8)])
>>> reverse_other(t)
>>> t
Tree(1, [Tree(8, [Tree(3, [Tree(5), Tree(4)]), Tree(6, [Tree(7)])]), Tree(2)])
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q reverse_otherLinked Lists
Q3: Link Pop
Implement link_pop, which is similar to the pop() method for lists.
link_pop takes in a Linked List lnk and optionally one extra argument index. If
provided a second argument, link_pop will remove the value at index from
the list and return it. If not given a second argument, link_pop will remove
the last value from the list and return it. Assume that you will never be asked
to remove an element at index 0 or at an index out of range.
Note: In the function definition,
index=-1denotes that when anindexargument is not provided, the value ofindexdefaults to-1.
def link_pop(lnk, index=-1):
'''Implement the pop method for a Linked List.
>>> lnk = Link(1, Link(2, Link(3, Link(4, Link(5)))))
>>> removed = link_pop(lnk)
>>> print(removed)
5
>>> print(lnk)
<1 2 3 4>
>>> link_pop(lnk, 2)
3
>>> print(lnk)
<1 2 4>
>>> link_pop(lnk)
4
>>> link_pop(lnk)
2
>>> print(lnk)
<1>
'''
if index == -1:
while ___________________:
___________________
removed = ___________________
___________________
else:
while ___________________:
___________________
___________________
removed = ___________________
___________________
return removedUse Ok to test your code:
python3 ok -q link_popQ4: Dr. Doudna's CRISPR Links
To simulate experiments with her recently discovered CRISPR Cas-9 technique, Nobel Laureate and UC Berkeley Professor Dr. Jennifer Doudna wishes to create a computational template for CRISPR insertions into certain genes. For this, she has approached the 61A students and staff for help in constructing a mechanism to enable these simulations. She has offered to provide a bank of test genes as well as the DNA sequence she wishes to insert into those genes.
Part A) Write a function crispr_gene_insertion that takes in a string insert, a single codon sequence of 3 characters, and a nested linked list lnk_of_genes, containing a linked list of genes. Each gene is itself a linked list containing a sequence of codons which are strings of 3 characters that represent DNA units.
Add the insert codon exactly i + 1 times after the start codon (“AUG”) in each gene, where i refers to the index of the gene in the linked list lnk_of_genes.
Definitions:
- Codon: a string of 3 characters(triplet), made from A, T, G, C, that represent DNA units (e.g. “ACG”, “GTT”)
- Gene: a sequence of codons
- Start codon: “AUG”
def crispr_gene_insertion(lnk_of_genes, insert):
"""Takes a linked list of genes and returns the genes with the INSERT codon added the correct number of times.
>>> link = Link(Link("AUG", Link("GCC", Link("ACG"))), Link(Link("ATG", Link("AUG", Link("ACG", Link("GCC"))))))
>>> print(link)
<<AUG GCC ACG> <ATG AUG ACG GCC>>
>>> crispr_gene_insertion(link, "TTA")
>>> print(link)
<<AUG TTA GCC ACG> <ATG AUG TTA TTA ACG GCC>>
>>> link = Link(Link("ATG"), Link(Link("AUG", Link("AUG")), Link(Link("AUG", Link("GCC")))))
>>> print(link)
<<ATG> <AUG AUG> <AUG GCC>>
>>> crispr_gene_insertion(link, "TTA") # first gene has no AUG so unchanged, 2nd gene has 2 AUGs but only first considered for insertion
>>> print(link)
<<ATG> <AUG TTA TTA AUG> <AUG TTA TTA TTA GCC>>
>>> link = Link.empty # empty linked list of genes returns Link.empty
>>> crispr_gene_insertion(link, "TTA")
>>> print(link)
()
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q crispr_gene_insertionPart B) Now that Dr. Doudna has got her CRISPR-edited genes, she wants to convert the DNA sequences into RNA triplets. Transcribing involves converting DNA to RNA. Write a function transcribe that takes in a string dna, and returns a new Python list representing the RNA codons (triplets) sequence obtained by transcribing the DNA sequence. Assume that the length of dna is always a multiple of 3.
Additionally, you have a dictionary dict that maps DNA bases to their corresponding RNA bases for transcription. This is already added to your function.
dict = {'A': 'U', 'T': 'A', 'G': 'C', 'C': 'G'}
Example: if dna = 'ATG':
dict['A'] = 'U'
dict['T'] = 'A'
dict['G'] = 'C'
transcribe(dna) = ['UAC']Note: It may be helpful to use the
range(start, stop, step)function — E.g.list(range(1,10,2))creates the list[1, 3, 5, 7, 9]
def transcribe(dna):
"""Takes a string of DNA and returns a Python list with the RNA codons.
>>> DNA = "TACCTAGCCCATAAA"
>>> transcribe(DNA)
['AUG', 'GAU', 'CGG', 'GUA', 'UUU']
"""
dict = {'A': 'U', 'T': 'A', 'G': 'C', 'C': 'G'}
return __________________
Use Ok to test your code:
python3 ok -q transcribeGenerators
Q5: Partition Generator
Construct the generator function partition_gen, which takes in a number n and returns an n-partition iterator. An n-partition iterator yields partitions of n, where a partition of n is a list of integers whose sum is n. The iterator should only return unique partitions; the order of numbers within a partition and the order in which partitions are returned does not matter.
Important: The skeleton code is only a suggestion; feel free to add or remove lines as you see fit.
def partition_gen(n):
"""
>>> partitions = [sorted(p) for p in partition_gen(4)]
>>> for partition in sorted(partitions): # note: order doesn't matter
... print(partition)
[1, 1, 1, 1]
[1, 1, 2]
[1, 3]
[2, 2]
[4]
"""
def yield_helper(num, segment):
if num == 0:
____________________________________________
elif ____________________________________________:
for small_part in ________________________________:
yield ____________________________________________
yield ________________________________________
yield from yield_helper(n, n)Use Ok to test your code:
python3 ok -q partition_genObjects
Election
Let's implement a game called Election. In this game, two players compete to try and earn the most votes. Both players start with 0 votes and 100 popularity.
The two players alternate turns, and the first player starts. Each turn, the current player chooses an action. There are two types of actions:
- The player can debate, and either gain or lose 50 popularity. If the player
has popularity
p1and the other player has popularityp2, then the probability that the player gains 50 popularity ismax(0.1, p1 / (p1 + p2))Note that themaxcauses the probability to never be lower than 0.1. - The player can give a speech. If the player has popularity
p1and the other player has popularityp2, then the player gainsp1 // 10votes and popularity and the other player losesp2 // 10popularity.
The game ends when a player reaches 50 votes, or after a total of 10 turns have been played (each player has taken 5 turns). Whoever has more votes at the end of the game is the winner!
Q6: Player
First, let's implement the Player class. Fill in the debate and speech
methods, that take in another Player other, and implement the correct
behavior as detailed above. Here are two additional things to keep in mind:
- In the
debatemethod, you should call the providedrandomfunction, which returns a random float between 0 and 1. The player should gain 50 popularity if the random number is smaller than the probability described above, and lose 50 popularity otherwise. - Neither players' popularity should ever become negative. If this happens, set it equal to 0 instead.
### Phase 1: The Player Class
class Player:
"""
>>> random = make_test_random()
>>> p1 = Player('Hill')
>>> p2 = Player('Don')
>>> p1.popularity
100
>>> p1.debate(p2) # random() should return 0.0
>>> p1.popularity
150
>>> p2.popularity
100
>>> p2.votes
0
>>> p2.speech(p1)
>>> p2.votes
10
>>> p2.popularity
110
>>> p1.popularity
135
>>> p1.speech(p2)
>>> p1.votes
13
>>> p1.popularity
148
>>> p2.votes
10
>>> p2.popularity
99
>>> for _ in range(4): # 0.1, 0.2, 0.3, 0.4
... p1.debate(p2)
>>> p2.debate(p1)
>>> p2.popularity
49
>>> p2.debate(p1)
>>> p2.popularity
0
"""
def __init__(self, name):
self.name = name
self.votes = 0
self.popularity = 100
def debate(self, other):
"*** YOUR CODE HERE ***"
def speech(self, other):
"*** YOUR CODE HERE ***"
def choose(self, other):
return self.speechUse Ok to test your code:
python3 ok -q PlayerQ7: Game
Now, implement the Game class. Fill in the play method, which should
alternate between the two players, starting with p1, and have each player take
one turn at a time. The choose method in the Player class returns the
method, either debate or speech, that should be called to perform the
action.
In addition, fill in the winner method, which should return the
player with more votes, or None if the players are tied.
### Phase 2: The Game Class
class Game:
"""
>>> p1, p2 = Player('Hill'), Player('Don')
>>> g = Game(p1, p2)
>>> winner = g.play()
>>> p1 is winner
True
>>> # Additional correctness tests
>>> winner is g.winner()
True
>>> g.turn
10
>>> p1.votes = p2.votes
>>> print(g.winner())
None
"""
def __init__(self, player1, player2):
self.p1 = player1
self.p2 = player2
self.turn = 0
def play(self):
while not self.game_over():
"*** YOUR CODE HERE ***"
return self.winner()
def game_over(self):
return max(self.p1.votes, self.p2.votes) >= 50 or self.turn >= 10
def winner(self):
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q GameQ8: New Players
The choose method in the Player class is boring, because it always returns
the speech method. Let's implement two new classes that inherit from Player,
but have more interesting choose methods.
Implement the choose method in the AggressivePlayer class, which returns the
debate method if the player's popularity is less than or equal to other's
popularity, and speech otherwise. Also implement the choose method in the
CautiousPlayer class, which returns the debate method if the player's
popularity is 0, and speech otherwise.
### Phase 3: New Players
class AggressivePlayer(Player):
"""
>>> random = make_test_random()
>>> p1, p2 = AggressivePlayer('Don'), Player('Hill')
>>> g = Game(p1, p2)
>>> winner = g.play()
>>> p1 is winner
True
>>> # Additional correctness tests
>>> p1.popularity = p2.popularity
>>> p1.choose(p2) == p1.debate
True
>>> p1.popularity += 1
>>> p1.choose(p2) == p1.debate
False
>>> p2.choose(p1) == p2.speech
True
"""
def choose(self, other):
"*** YOUR CODE HERE ***"
class CautiousPlayer(Player):
"""
>>> random = make_test_random()
>>> p1, p2 = CautiousPlayer('Hill'), AggressivePlayer('Don')
>>> p1.popularity = 0
>>> p1.choose(p2) == p1.debate
True
>>> p1.popularity = 1
>>> p1.choose(p2) == p1.debate
False
>>> # Additional correctness tests
>>> p2.choose(p1) == p2.speech
True
"""
def choose(self, other):
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q AggressivePlayer
python3 ok -q CautiousPlayerLists
Q9: Deck of cards
Write a list comprehension that will create a deck of cards, given a
list of suits and a list of ranks. Each
element in the list will be a card, which is represented by a 2-element list
of the form [suit, rank].
def deck(suits, ranks):
"""Creates a deck of cards (a list of 2-element lists) with the given
suits and ranks. Each element in the returned list should be of the form
[suit, rank].
>>> deck(['S', 'C'], [1, 2, 3])
[['S', 1], ['S', 2], ['S', 3], ['C', 1], ['C', 2], ['C', 3]]
>>> deck(['S', 'C'], [3, 2, 1])
[['S', 3], ['S', 2], ['S', 1], ['C', 3], ['C', 2], ['C', 1]]
>>> deck([], [3, 2, 1])
[]
>>> deck(['S', 'C'], [])
[]
"""
"*** YOUR CODE HERE ***"
return ______
Use Ok to test your code:
python3 ok -q deckQ10: Intersection - Summer 2015 MT1 Q4
Implement intersection(lst_of_lsts), which takes a list of lists and returns a list of distinct elements
that appear in all the lists in lst_of_lsts. If no number appears in all of the lists, return the empty list.
You may assume that lst_of_lsts contains at least one list.
def intersection(lst_of_lsts):
"""Returns a list of distinct elements that appear in every list in
lst_of_lsts.
>>> lsts1 = [[1, 2, 3], [1, 3, 5]]
>>> intersection(lsts1)
[1, 3]
>>> lsts2 = [[1, 4, 2, 6], [7, 2, 4], [4, 4]]
>>> intersection(lsts2)
[4]
>>> lsts3 = [[1, 2, 3], [4, 5], [7, 8, 9, 10]]
>>> intersection(lsts3) # No number appears in all lists
[]
>>> lsts4 = [[3, 3], [1, 2, 3, 3], [3, 4, 3, 5]]
>>> intersection(lsts4) # Return list of distinct elements
[3]
"""
elements = []
"*** YOUR CODE HERE ***"
return elementsUse Ok to test your code:
python3 ok -q intersectionRegex
Q11: Party Planner
You are the CEO of SchemeCorp, a company you founded after learning Scheme in CS61A. You want to plan a social for everyone who works at your company, but only your colleagues who live in Berkeley can help plan the party. You want to add all employees located in Berkeley (based on their phone number) to a party-planning group chat. Given a string representing a list of employee phone numbers for SchemeCorp, write a regular expression that matches all valid phone numbers of employees in the 314 or 510 Berkeley area codes.
In addition, a few of your colleagues are visiting from Los Angeles (area code 310) and Montreal (area code 514) and would like to help. Your regular expression should match their phone numbers as well.
Valid phone numbers can be formatted in two ways. Some employees entered their phone numbers with parentheses around the area code (for example, (786)-375-6454), while some omitted the area code (for example, 786-375-6454). A few employees also entered their phone numbers incorrectly, with either greater than or fewer than 10 digits. These phone numbers are not valid and should not be included in the group chat.
import re
def party_planner(text):
"""
Returns all strings representing valid phone numbers with 314, 510, 310, or 514 area codes.
The area code may or may not be surrounded by parentheses. Valid phone numbers
have 10 digits and follow this format: XXX-XXX-XXXX, where each X represents a digit.
>>> party_planner("(408)-996-3325, (510)-658-7400, (314)-3333-22222")
True
>>> party_planner("314-826-0705, (510)-314-3143, 408-267-7765")
True
>>> party_planner("5103143143")
False
>>> party_planner("514-300-2002, 310-265-4242") # invite your friends in LA and Montreal
True
"""
return bool(re.search(__________, text))
Use Ok to test your code:
python3 ok -q party-plannerScheme
Q12: Split
Implement split-at, which takes a list lst and a non-negative number n as
input and returns a pair new such that (car new) is the first n
elements of lst and (cdr new) is the remaining elements of lst. If n is
greater than the length of lst, (car new) should be lst and (cdr new)
should be nil.
scm> (car (split-at '(2 4 6 8 10) 3))
(2 4 6)
scm> (cdr (split-at '(2 4 6 8 10) 3))
(8 10)(define (split-at lst n)
'YOUR-CODE-HERE
)Use Ok to test your code:
python3 ok -q split-atScheme Data Abstraction
Q13: Filter Odd Tree
Write a function filter-odd which takes a tree data abstraction and returns a new tree with all even labels replaced with nil.
Consider using the
mapprocedure to apply a one-argument function to a list.
Below is a Scheme-ified data abstraction of the Tree class we've been working with this semester.
; Constructs tree given label and list of branches
(tree label branches)
; Returns the label of the tree
(label t)
; Returns the list of branches of the given tree
(branches t)(define (filter-odd t)
'YOUR-CODE-HERE
)Use Ok to test your code:
python3 ok -q filter_oddVehicles
Say we have an abstract data type for owners and vehicles.
- The
ownerabstraction keeps track of thenameof a vehicle-owner as well as theagethey got their license. - The
vehicleabstraction keeps track of themodel, theyear, andprevious-ownersof the vehicle
You can find the constructors for these classes below:
(define (make-owner name age) (cons name (cons age nil)))
(define (make-vehicle model year previous-owners) (cons model (cons year previous-owners)))Q14: Vehicles: Selectors
Implement get-model, get-year, and get-owners. These functions take in a vehicle abstraction, and return the relevant attribute. For example, get-model takes vehicle as an input and returns the model.
Note:
get-ownersreturns a list of owner objects.
(define (get-model vehicle)
'YOUR-CODE-HERE
)
(define (get-year vehicle)
'YOUR-CODE-HERE
)
(define (get-owners vehicle)
'YOUR-CODE-HERE
)Use Ok to test your code:
python3 ok -q vehicles_selectorsQ15: Old
Implement older-vehicle. This method takes in two vehicles as input and returns the model of the older one.
Be sure to keep the abstraction barrier in mind! Feel free to use the selector functions we defined in the previous question.
(define (older-vehicle vehicle1 vehicle2)
'YOUR-CODE-HERE
)Use Ok to test your code:
python3 ok -q vehicles_olderQ16: New Owner
Implement new-owner. This method takes in a vehicle and owner as input, and returns a new vehicle abstraction with the previous-owners list updated to reflect the new owner added.
Be sure to keep the abstraction barrier in mind!
(define (new-owner vehicle owner)
'YOUR-CODE-HERE
)Use Ok to test your code:
python3 ok -q vehicles_new_ownerQ17: Owner Names
Implement owners-names. This method takes in a vehicle as input and returns a list of only the names of each owner stored in the previous-owners list within the specified vehicle.
Hint: The map function could be helpful here!
(define (owners-names vehicle)
'YOUR-CODE-HERE
)Use Ok to test your code:
python3 ok -q vehicles_owners_namesSQL
Pizza
In each question below, you will define a new table based on the following
tables. The first defines the names, opening, and closing hours of great pizza
places in Berkeley. The second defines typical meal times (for college
students). A pizza place is open for a meal if the meal time is at or within
the open and close times.
Your tables should still perform correctly even if the values in these tables were to change. Don't just hard-code the output to each query.
Q18: Opening Times
You'd like to have lunch before 1pm.
Create a opening table with the names of all Pizza places that open before 1pm,
listed in reverse alphabetical order.
-- Pizza places that open before 1pm in alphabetical order
CREATE TABLE opening AS
SELECT "REPLACE THIS LINE WITH YOUR SOLUTION";
Use Ok to test your code:
python3 ok -q openingQ19: Double Pizza
If two meals are more than 6 hours apart, then there's nothing wrong with going
to the same pizza place for both, right? Create a double table with three
columns. The first columns is the earlier meal, the second is the later meal,
and the third is the name of a pizza place. Only include rows that describe two
meals that are more than 6 hours apart and a pizza place that is open for
both of the meals. The rows may appear in any order.
-- Two meals at the same place
CREATE TABLE double AS
SELECT "REPLACE THIS LINE WITH YOUR SOLUTION";
-- Example:
SELECT * FROM double WHERE name="Sliver";
-- Expected output:
-- breakfast|dinner|SliverUse Ok to test your code:
python3 ok -q doubleInterpreters
Brackulator
The following question has no okpy testing component.
The Brackulator language shares an evaluator with the Calculator language, but uses a more concise syntax. Instead of using operator names or symbols, Brackulator indicates operations using different kinds of brackets:
[]: add(): subtract<>: multiply{}: divide
Operand expressions are separated by spaces within these brackets. The following Brackulator expressions are followed by their Calculator equivalents.
<1 2 3> (* 1 2 3)
(5) (- 5)
[2{4 8}] (+ 2 (/ 4 8))
<[2{12 6}](3 4 5)> (* (+ 2 (/ 12 6)) (- 3 4 5))By solving the following problems, you will implement a parser,
brack_read, that returns an expression for the calc_eval evaluator
implemented in the Calculator example from lecture.
All of your solutions should be defined in terms of the following dictionaries of bracket types, which configure the parser to supply the correct operator for each bracket:
# A dictionary from pairs of matching brackets to the operators they indicate.
brackets = {('[', ']'): '+',
('(', ')'): '-',
('<', '>'): '*',
('{', '}'): '/'}
# A dictionary with left-bracket keys and corresponding right-bracket values.
left_to_right = {left: right for left, right in brackets}
# The set of all left and right brackets.
all_brackets = set(left_to_right.keys()).union(set(left_to_right.values()))Q20: Tokenize Expression
Complete tokenize, which splits a Brackulator expression into tokens,
and raise a ValueError if any token is not a number or a known
bracket. Hint: You can first surround each bracket with spaces using
line.replace, then split on spaces. Afterward, check each token to
ensure that it is legal. The provided coerce_to_number function may
prove useful:
def tokenize(line):
"""Convert a string into a list of tokens.
>>> tokenize('2.3')
[2.3]
>>> tokenize('(2 3)')
['(', 2, 3, ')']
>>> tokenize('<2 3)')
['<', 2, 3, ')']
>>> tokenize('<[2{12.5 6.0}](3 -4 5)>')
['<', '[', 2, '{', 12.5, 6.0, '}', ']', '(', 3, -4, 5, ')', '>']
>>> tokenize('2.3.4')
Traceback (most recent call last):
...
ValueError: invalid token 2.3.4
>>> tokenize('?')
Traceback (most recent call last):
...
ValueError: invalid token ?
>>> tokenize('hello')
Traceback (most recent call last):
...
ValueError: invalid token hello
>>> tokenize('<(GO BEARS)>')
Traceback (most recent call last):
...
ValueError: invalid token GO
"""
# Surround all brackets by spaces so that they are separated by split.
for b in all_brackets:
line = line.replace(b, ' ' + b + ' ')
# Convert numerals to numbers and raise ValueErrors for invalid tokens.
tokens = []
for t in line.split():
"*** YOUR CODE HERE ***"
return tokens
def coerce_to_number(token):
"""Coerce a string to a number or return None.
>>> coerce_to_number('-2.3')
-2.3
>>> print(coerce_to_number('('))
None
"""
try:
return int(token)
except (TypeError, ValueError):
try:
return float(token)
except (TypeError, ValueError):
return NoneQ21: Brackulator Expression Tree
Implement brack_read, which returns an expression tree for the first
valid Brackulator expression in a list of tokens. The expression tree
should contain Calculator operators that correspond to the bracket
types. Raise a SyntaxError for any malformed expression. The Pair
class and nil object from lecture appear at the bottom of this file.
This function is similar to scheme_read from Calculator's
Scheme reader file.
Hint: Introduce another function read_tail that reads the elements
in a combination until reaching a closing bracket. In brack_read
make sure that the closing bracket of an expression matches the opening
bracket. The left_to_right dictionary defined above gives you the
matching right bracket for each type of left bracket. The brackets
dictionary gives you the corresponding operator (e.g. '+' for '[' and
']').
Once you complete this problem, you can place your homework file in the
same directory as scalc.py (and its supporting files), then run
read_eval_print_loop to interact with the Brackulator language:
def brack_read(tokens):
"""Return an expression tree for the Brackulator
expression in tokens. Tokens in that expression are removed from tokens as
a side effect.
>>> brack_read(tokenize('100'))
100
>>> brack_read(tokenize('([])'))
Pair('-', Pair(Pair('+', nil), nil))
>>> print(brack_read(tokenize('<[2{12 6}](3 4 5)>')))
(* (+ 2 (/ 12 6)) (- 3 4 5))
>>> brack_read(tokenize('(1)(1)')) # More than one expression is ok
Pair('-', Pair(1, nil))
>>> brack_read(tokenize('[])')) # Junk after a valid expression is ok
Pair('+', nil)
>>> brack_read(tokenize('([]')) # Missing right bracket
Traceback (most recent call last):
...
SyntaxError: unexpected end of line
>>> brack_read(tokenize('[)]')) # Extra right bracket
Traceback (most recent call last):
...
SyntaxError: unexpected )
>>> brack_read(tokenize('([)]')) # Improper nesting
Traceback (most recent call last):
...
SyntaxError: unexpected )
>>> brack_read(tokenize('')) # No expression
Traceback (most recent call last):
...
SyntaxError: unexpected end of line
"""
if not tokens:
raise SyntaxError('unexpected end of line')
token = tokens.pop(0)
n = coerce_to_number(token)
if n != None:
return n
elif token in left_to_right:
"*** YOUR CODE HERE ***"
Support code for Brackulator (from the Calculator example):
###################################
# Support classes for Brackulator #
###################################
class Pair:
"""A pair has two instance attributes: first and second. Second must be a Pair or nil
>>> s = Pair(1, Pair(2, nil))
>>> s
Pair(1, Pair(2, nil))
>>> print(s)
(1 2)
>>> len(s)
2
>>> s[1]
2
>>> print(s.map(lambda x: x+4))
(5 6)
"""
def __init__(self, first, second):
assert isinstance(second, Pair) or second is nil
self.first = first
self.second = second
def __repr__(self):
return "Pair({0}, {1})".format(repr(self.first), repr(self.second))
def __str__(self):
s = "(" + str(self.first)
second = self.second
while isinstance(second, Pair):
s += " " + str(second.first)
second = second.second
assert second is nil
return s + ")"
def __len__(self):
n, second = 1, self.second
while isinstance(second, Pair):
n += 1
second = second.second
if second is not nil:
raise TypeError("length attempted on improper list")
return n
def __getitem__(self, k):
if k < 0:
raise IndexError("negative index into list")
y = self
for _ in range(k):
if y.second is nil:
raise IndexError("list index out of bounds")
y = y.second
return y.first
def map(self, fn):
"""Return a Scheme list after mapping Python function FN to SELF."""
mapped = fn(self.first)
return Pair(mapped, self.second.map(fn))
class nil:
"""The empty list"""
def __repr__(self):
return "nil"
def __str__(self):
return "()"
def __len__(self):
return 0
def __getitem__(self, k):
if k < 0:
raise IndexError("negative index into list")
raise IndexError("list index out of bounds")
def map(self, fn):
return self
nil = nil() # Assignment hides the nil class; there is only one instanceTo use the following function, you will need to place your homework solution in the same directory as the files from the Calculator Example:
def read_eval_print_loop():
"""Run a read-eval-print loop for the Brackulator language."""
global Pair, nil
from scheme_reader import Pair, nil
from scalc import calc_eval
while True:
try:
src = tokenize(input('brack> '))
while len(src) > 0:
expression = brack_read(src)
print(calc_eval(expression))
except (SyntaxError, ValueError, TypeError, ZeroDivisionError) as err:
print(type(err).__name__ + ':', err)
except (KeyboardInterrupt, EOFError): # <Control>-D, etc.
return