#!/usr/bin/env python3
"""
parse_tree.py
Parses mathematical expressions from fully-parenthesized strings.
"""

__author__ = "Richard White"
__version__ = "2019-04-11"

from atds import Stack, BinaryTree

def build_parse_tree(fpexpr):
    """Creates a binary tree from the fully-parenthesized
    expression. We'll do this by pushing the current tree
    (current_focus) onto a stack when we descend to its 
    subtree to edit that subtree), then pop the stack
    to get back to previous parent trees when we've completed
    filling out the subtree.
    """
    
    # split the parenthesized expression up into tokens

    # create the parse tree as an empty binary tree

    # create an empty stack which will track the current parent

    # Push the current (empty) binary tree onto the stack         

    # Set current focus as our parse tree

    
    # Go through all the tokens, one at a time   

        # print("DEBUG: Parsing", token)
        if token == "(":
            # begin a new expression
        


        elif token == ")":
            # end expression. Move back up to parent

        elif token in "+-*/":

        else:   # it must be a number (or an error!)



    return pt


def evaluate(parse_tree):
    """Now that the binary parse tree has been assembled, we can
    traverse through it recursively, using the values of each 
    node to calculate the final result of the mathematical expression.
    
    Because we'll be recursing, what is the base case? How will we know 
    when we need to return a result?
    """
    
    # Get the tree's left child

    # Get the tree's right child

    # If we don't have left and right values

        # return the numeric value of this root value

    else:
   
        # Check the root value to find out what the sign is
        # and perform the mathematical operation on the
        # evaluation of the left and right subtrees (recursion)


def main():
    EPSILON = 0.001     # Used to accept results of limited precision
    tests = [("( 2 + 3 )", 5)]

    '''
    Add these tests laster on once the first test is working:
             ("( 1 / 3 )", 1/3),
             ("( ( 3 + 5 ) * 2 )", 16),
             ("( 3 + ( 5 * 2 ) )", 13),
             ("( ( 2 + ( 6 * 7 ) ) - 1 )", 43),
             ("( ( ( ( 4 / 1 ) - ( 4 / 3 ) ) + ( 4 / 5 ) ) - ( 4 / 7 ) )", 3.1416)]
    '''

    for i in range(len(tests)):
        # Build the parse tree based on fully-parenthesized 
        # expression
        print("Testing expression",tests[i][0])
        pt = build_parse_tree(tests[i][0])
        # print("DEBUG:",pt)
        # Now evaluate the expression, recursively!
        # result = evaluate(pt)
        # print("DEBUG:",result)
        print("Result:",evaluate(pt))
        if abs(evaluate(pt) - tests[i][1]) < EPSILON:
            print("Test",i + 1,"passed")
        else:
            print("Test",i + 1,"failed")
    print("""Test 6 should fail. It's an attempt to calculate pi that doesn't 
get very far.""")

if __name__ == "__main__":
    main()