"""Homework 11: Parsers and the Client-Server Architecture.

Due Friday, 11/18, at 5pm.
"""

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

class Exp(object):
    """A call expression in Calculator or Brackulator.
    
    >>> Exp('add', [1, 2])
    Exp('add', [1, 2])
    """

    def __init__(self, operator, operands):
        self.operator = operator
        self.operands = operands

    def __repr__(self):
        return 'Exp({0}, {1})'.format(repr(self.operator), repr(self.operands))

"""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 = {('[', ']'): 'add',
            ('(', ')'): 'sub',
            ('<', '>'): 'mul',
            ('{', '}'): 'div'}
LEFT_RIGHT = {left:right for left, right in BRACKETS.keys()}


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

def tokenize(line):
    """Convert a string into a list of tokens.

    >>> tokenize('<[2{12 6}](3 4 5)>')
    ['<', '[', '2', '{', '12', '6', '}', ']', '(', '3', '4', '5', ')', '>']
    """
    "*** YOUR CODE HERE ***"


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

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

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('([GO BEARS])')) # Unrecognized token(s)
    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 ***"


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

def analyze(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.

    >>> analyze(tokenize('([])'))
    Exp('sub', [Exp('add', [])])
    >>> analyze(tokenize('([]')) # Missing right bracket
    Traceback (most recent call last):
        ...
    SyntaxError: unexpected end of line
    >>> analyze(tokenize('[)]')) # Extra right bracket
    Traceback (most recent call last):
        ...
    SyntaxError: unexpected )
    >>> analyze(tokenize('([)]')) # Improper nesting
    Traceback (most recent call last):
        ...
    SyntaxError: unexpected )
    >>> analyze(tokenize('([GO BEARS])')) # Unrecognized token(s)
    Traceback (most recent call last):
        ...
    SyntaxError: unexpected GO
    >>> analyze(tokenize('')) # No expression
    Traceback (most recent call last):
        ...
    SyntaxError: unexpected end of line
    >>> analyze(tokenize('100'))
    100
    >>> analyze(tokenize('(1)(1)')) # More than one expression is ok
    Exp('sub', [1])
    >>> analyze(tokenize('[])')) # Junk after a valid expression is ok
    Exp('add', [])
    >>> analyze(tokenize('<[2{12 6}](3 4 5)>'))
    Exp('mul', [Exp('add', [2, Exp('div', [12, 6])]), Exp('sub', [3, 4, 5])])
    >>> calc_eval(analyze(tokenize('<[2{12 6}](3 4 5)>')))
    -24.0
    """
    "*** YOUR CODE HERE ***"


"""4) 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

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

from urllib.request import urlopen

def puzzle_4():
    """Return the soluton to puzzle 4."""
    "*** YOUR CODE HERE ***"


"""The Calculator/Brackulator evaluator from lecture is copied below.  No
changes are required. To run a Brackulator REPL, call read_eval_print_loop."""

from functools import reduce
from operator import mul
try:
    import readline  # Enables access to previous expressions in the REPL
except ImportError:
    pass # Readline is not necessary; it's just a convenience

def read_eval_print_loop():
    """Run a read-eval-print loop for calculator."""
    while True:
        try:
            expression_tree = brack_parse(input('Bra<[<u}at()r> '))
            print(calc_eval(expression_tree))
        except (SyntaxError, TypeError, ZeroDivisionError) as err:
            print(type(err).__name__ + ':', err)
        except (KeyboardInterrupt, EOFError):  # <Control>-D, etc.
            print('Calculation completed.')
            return

def calc_eval(exp):
    """Evaluate a Calculator expression.

    >>> calc_eval(Exp('add', [2, Exp('mul', [4, 6])]))
    26
    """
    if type(exp) in (int, float):
        return exp
    if type(exp) == Exp:
        arguments = list(map(calc_eval, exp.operands))
        return calc_apply(exp.operator, arguments)

def calc_apply(operator, args):
    """Apply the named operator to a list of args.
    
    >>> calc_apply('+', [1, 2, 3])
    6
    >>> calc_apply('-', [10, 1, 2, 3])
    4
    >>> calc_apply('*', [])
    1
    >>> calc_apply('/', [40, 5])
    8.0
    """
    if operator in ('add', '+'):
        return sum(args)
    if operator in ('sub', '-'):
        if len(args) == 0:
            raise TypeError(operator + 'requires at least 1 argument')
        if len(args) == 1:
            return -args[0]
        return sum(args[:1] + [-arg for arg in args[1:]])
    if operator in ('mul', '*'):
        return reduce(mul, args, 1)
    if operator in ('div', '/'):
        if len(args) != 2:
            raise TypeError(operator + ' requires exactly 2 arguments')
        numer, denom = args
        return numer/denom

def brack_parse(line):
    """Parse a line of Brackulator input and return an expression tree."""
    tokens = tokenize(line)
    expression_tree = analyze(tokens)
    if len(tokens) > 0:
        raise SyntaxError('Extra token(s): ' + ' '.join(tokens))
    return expression_tree