#!/usr/bin/env python

"""
 fpe

 a ("fully parenthesized expressions" to scheme) compiler in python.

 This is based on ./recursive_descent.py ... 
 with the parser functions returning lisp code rather than 
 the full parse tree. Since the structure of lisp reflects
 the AST (abstract syntax tree directly), and the AST
 is easy to get from the full parse tree, this compilation
 is almost trivial once we can do the parsing.

 Running it looks like this :

   $ ./fpe "((1+2)*(3+4))"
   (* (+ 1 2) (+ 3 4))

 Jim Mahoney | Nov 18 2021 | cs.bennington.college | MIT License
"""

class LexerQueue:
    """ an API for moving through the tokens of the code string """
    def __init__(self, code):
        self.code = code  # the code string to analyze i.e. "(1+2)"
        self.offset = 0   # current character is self.code[self.offset]
    def peek(self):
        """ return the next token (character) 
            or the empty string if there are no more."""
        try:
            return self.code[self.offset]
        except:
            return ""
    def pop(self):
        """ return the next token and move on to the next """
        result = self.peek()
        self.offset += 1
        return result
    def is_empty(self):
        """ return True if there are no more tokens """
        return self.peek() == ""

# -- parser ---------

digit_tokens = ('0', '1', '2', '3', '4', '5', '6', '7', '8', '9')
operator_tokens = ('+', '-', '*', '/')

def expression(lq):
    if lq.peek() == "(":
        left = lq.pop()
        expr1 = expression(lq)
        op = operator(lq)
        expr2 = expression(lq)
        right = lq.pop()
        assert left == "(" and right == ")", \
            "OOPS - didn't find expected ( or )"
        return f"({op} {expr1} {expr2})"
    else:
        return number(lq)

def operator(lq):
    op = lq.pop()
    assert op in operator_tokens, \
        "OOPS - failed to find expected operator"
    return op
        
def number(lq):
    result = digit(lq)
    while lq.peek() in digit_tokens:
        result += digit(lq)
    return result

def digit(lq):
    value = lq.pop()
    assert value in digit_tokens, \
        "OOPS - didn't find expected digit"
    return value

# -- compiler --

import sys

if len(sys.argv) < 2:
    print('Usage: ./fpe "(2*(3+4))"')
else:
    code = sys.argv[1]
    print(expression(LexerQueue(code)))