Due by 11:59pm on Wednesday, 4/17
Submission. See the online submission instructions. We have provided a starter file for the questions below.
Readings. Section 3.6 of the online lecture notes.
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:
BRACKETS = {('[', ']'): '+',
('(', ')'): '-',
('<', '>'): '*',
('{', '}'): '/'}
LEFT_RIGHT = {left:right for left, right in BRACKETS.keys()}
ALL_BRACKETS = set(b for bs in BRACKETS for b in bs)
Q1. Implement 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{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
"""
"*** YOUR CODE HERE ***"
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 None
Q2. Implement isvalid, which tests whether a prefix of a list of tokens is a well-formed Brackulator expression. A matching right bracket must appear after each left bracket, and if two left brackets appear in sequence, then the matching right bracket of the first must appear after the matching right bracket of the second. Any token that is not a left or right bracket must be a number. For an empty sequence of tokens, you should return False.
Hint: This function is similar to scheme_read from Calculator, but doesn't need to build an expression (that's problem 3):
def isvalid(tokens):
"""Return whether some prefix of tokens represent a valid Brackulator
expression. Tokens in that expression are removed from tokens as a side
effect.
>>> isvalid(tokenize('([])'))
True
>>> isvalid(tokenize('([]')) # Missing right bracket
False
>>> isvalid(tokenize('[)]')) # Extra right bracket
False
>>> isvalid(tokenize('([)]')) # Improper nesting
False
>>> isvalid(tokenize('')) # No expression
False
>>> isvalid(tokenize('100'))
True
>>> isvalid(tokenize('<(( [{}] [{}] ))>'))
True
>>> isvalid(tokenize('<[2{12 6}](3 4 5)>'))
True
>>> isvalid(tokenize('()()')) # More than one expression is ok
True
>>> isvalid(tokenize('[])')) # Junk after a valid expression is ok
True
"""
"*** YOUR CODE HERE ***"
Q3. 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.
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 first well-formed 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
"""
"*** YOUR CODE HERE ***"
Q4. The Python Challenge is a website designed to teach people the many features of the Python Library. Each page of the site is a puzzle that can be solved simply in Python. The solution to each puzzle gives the URL of the next.
To complete your homework, include your solution to puzzle 4 (the one with the picture of a wood carving). You will have to complete puzzles 0, 1, 2, and 3 to reach 4.
http://www.pythonchallenge.com/pc/def/0.html
Some hints:
Puzzle 1. Try str.maketrans to make a dictionary and str.translate to generate a new string. Letters are listed in the string module.
>>> 'Borkozoy'.translate(str.maketrans('oz', 'el'))
'Berkeley'
>>> import string
>>> string.ascii_lowercase
'abcdefghijklmnopqrstuvwxyz'
Puzzles 2 & 3. To view the source code of a web page in a browser, use
Uppercase letters are also in the string module.
>>> string.ascii_uppercase 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
Puzzle 4. Here's an example of fetching the source of a web page in Python. The address below links to an archive of the first WWW site.
>>> base = 'http://www.w3.org/History/19921103-hypertext/hypertext'
>>> addr = base + '/WWW/TheProject.html'
>>> from urllib.request import urlopen
>>> contents = urlopen(addr).read().decode()
>>> contents.split('\n')[1]
'<TITLE>The World Wide Web project</TITLE>'
As you work on this puzzle, make sure to print the result of each step.
The comments on the puzzle page say: "urllib may help. DON'T TRY ALL NOTHINGS, since it will never end. 400 times is more than enough."
Include your solution to puzzle 4 below:
from urllib.request import urlopen
def puzzle_4():
"""Return the soluton to puzzle 4."""
"*** YOUR CODE HERE ***"
Support code for Brackulator (from the Calculator example):
class Pair(object):
"""A pair has two instance attributes: first and second. For a Pair to be
a well-formed list, second is either a well-formed list or nil. Some
methods only apply to well-formed lists.
>>> 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):
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
if second is not nil:
s += " . " + str(second)
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")
elif not isinstance(y.second, Pair):
raise TypeError("ill-formed list")
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)
if self.second is nil or isinstance(self.second, Pair):
return Pair(mapped, self.second.map(fn))
else:
raise TypeError("ill-formed list")
class nil(object):
"""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 instance
To 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('> '))
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