CS61A Homework 12

Due by 11:59 PM on (that is, the end of) Tuesday, 7/31

This homework must be submitted online. We do not require a paper copy. If you would like a reader to give you written feedback on your homework, submit a paper copy to the homework box.

To turn in the electronic copy, submit all of your answers in files named hw12.py. Follow the instructions here to submit the electronic copy.

If you would like, you can use the template files hw12.py. To copy this file to your lab account you can run the command:

      cp ~cs61a/lib/hw/hw12/hw12.py .

to copy them into your current directory.

In homeworks, we have three different categories of questions:

Core Questions — Questions that we believe test a core concept of the course and should be your highest priority when attempting the homework.
Reinforcement Questions — Questions that we believe have material that is either covered by other questions in this homework or in past homeworks, and can therefore be considered second priority after the core questions have been completed.
Extra for Experts — As in earlier homeworks, these problems are completely optional. You are encouraged to try these questions once you have completed questions from the other two categories. However, these are questions that we consider either more difficult than what we would ask you on an exam or that focus on ideas we are not concerned with in this course, so please do not be discouraged if you do not solve them.

It is our hope that these categories will help guide you in deciding how to divide your time when working on the homeworks.

Core Questions

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>              mul(1, 2, 3)
      (5)                  sub(5)
      [2{4 8}]             add(2, div(4, 8))
      <[2{12 6}](3 4 5)>   mul(add(2, div(12, 6)), sub(3, 4, 5))

By solving the following problems, you will implement a parser, brack_parse, that returns an expression tree for the calc_eval evaluator from lecture, but which parses a Brackulator expression. The evaluator and read-eval-print loop for Calculator appear at the end of this file so that you can experiment with Brackulator once you have implemented the parser. The Exp class is unchanged.

Q1. Implement tokenize, which splits a Brackulator expression into tokens. Each number and bracket is its own token.

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; the provided coerce_to_number function may prove useful.

Hint: This function is similar to analyze from Calculator, but doesn't need to build an expression tree (that's problem 3).

Q3. Implement analyze, 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 appropriate syntax errors for any malformed expressions.

Once you complete this problem, your Brackulator implementation should work.

Reinforcement Questions

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. Start from Puzzle 0

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:

      Chrome:   View > Developer > View Page Source
      Firefox:  Tools > Web Developer > Page Source
      Safari:   View > View Source

(the option exists in other browsers as well)

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.

Extra for Experts