'''stack3.py

   Jed Yang, 2016-11-06

   Evaluate arithmetic expressions using stacks.
'''

from stack import Stack

# We were able to check things like
#     ((1+2)*3+(4*5)+6-7)*(8*9)
# are correctly parenthesized.  We can even deal with using multiply types of
# brackets.  Let's now try to evaluate the arithmetic expression.

# For simplicity, we implement operators +, -, and *, each taking two numbers
# (one before and after).  We will put a single pair of parentheses around such
# an expression.
#     good: (1+2), (2-4), (4*8)
#     bad: 1+2, ((1+2)), (1), (1+2+3)
# We can nest good expressions in other constructions, like so:
#     good: ((1+2)+3)
goodExpr = '((((1+2)*3)+((4*5)+(6-7)))*(8*9))'
#     bad: (1+2)+3
# But we always need to explicitly put parentheses around the expressions.  We
# call these FULLY PARENTHESIZED EXPRESSIONS.  They make the task easier for
# us.

# Our algorithm to evaluate is roughly thus:
#     - When we see an operator, push it onto a stack of operators.  
#     - When we see a number, push it onto a stack of values.
#     - When we see a closing paren ), we evaluate (num1 op num2) by popping
#       two numbers and an operator from their respective stacks, perform the
#       operation, and *PUSH* the result back onto the stack of values.
# To make parsing easier, let us put spaces between elements:
goodExpr = '( ( ( ( 1 + 2 ) * 3 ) + ( ( 4 * 5 ) + ( 6 - 7 ) ) ) * ( 8 * 9 ) )'

def evalFullyParen(exprStr):
   '''Evaluate a fully parenthesized expression delimited by spaces.'''
   expr = exprStr.split()
   values = Stack()
   operators = Stack()
   for token in expr:
      if token == '(':
         pass # we don't actually need these, why?
      elif token == '+' or token == '*' or token == '-':
         # we store these and evaluate when we see its corresponding ')'
         operators.push(token)
      elif token == ')':
         # we use the last operator
         op = operators.pop()
         # and the last two values
         b = values.pop() # why b first?
         a = values.pop()
         # think: (a op b)
         if   op == '+': val = a + b
         elif op == '*': val = a * b
         elif op == '-': val = a - b
         # store this value on the stack
         values.push(val)
      else:
         # treat this current token as a number
         values.push(int(token))
   # if we got a valid fully parenthesized expression
   # operators should be empty and values should have a single number
   if not operators.isEmpty() or values.isEmpty():
      print('Faulty expression.')
   else:
      ans = values.pop()
      if not values.isEmpty():
         print('Faulty expression.')
      else:
         return ans

print(evalFullyParen(goodExpr))

# Read the code above, understand how it works.  Then explain why we can let
# the operator "float" around within its parenthesized group.  That is, why are
# the following three expressions all valid and give the same answer?
#     ( 1 + 2 )
#     ( + 1 2 )
#     ( 1 2 + )
# In fact, we can even do this in other levels of nesting.  The following
# expressions will all work (try them!).
goodExpr  = '( ( ( ( 1 + 2 ) * 3 ) + ( ( 4 * 5 ) + ( 6 - 7 ) ) ) * ( 8 * 9 ) )'
floating1 = '( ( ( ( 1 2 + ) * 3 ) + ( ( * 4 5 ) + ( 6 7 - ) ) ) * ( * 8 9 ) )'
floating2 = '( ( ( * ( 1 2 + ) 3 ) + ( ( * 4 5 ) ( 6 7 - ) + ) ) * ( * 8 9 ) )'
floating3 = '( ( ( ( 1 2 + ) 3 * ) ( ( 4 5 * ) ( 6 7 - ) + ) + ) ( 8 9 * ) * )'
#print(evalFullyParen(floating1))

# For the last one, I have "floated" each operator as far right as possible.
# So each operator is *after* its two arguments and followed by its
# corresponding closing parenthesis.  We can delete the parentheses and let the
# operators trigger the operations!  (Remember that we did not ever pay
# attention to the opening parentheses.)  This is what we get:
postfix = '1 2 + 3 * 4 5 * 6 7 - + + 8 9 * *'

# Here are some other smaller examples:
#     (1+2)          -->  1 2 +
#     ((1+2)*3)      -->  1 2 + 3 *
#     ((1+2)*(3-4))  -->  1 2 + 3 4 - *
#     (1+((2*3)-4))  -->  1 2 3 * 4 - +
#
# This is known as reverse Polish notation, or ``postfix''.  Even though
# expressions look funny, this notation eliminates the need for parentheses and
# the evaluation is a lot easier:
#     - encounter a number? push it on to a stack of values
#     - encounter an operator? pop two numbers, perform operation, and push the
#       answer back onto the stack
# That's it!  There's no need for a second stack to store operators, because
# the operators come when we are actually ready to peform the operation.

# Your task: implement a function to evaluate postfix expressions.

# This looks scary, but it's actually not bad.  Start with a (correctly
# working) copy of evalFullyParen().  You essentially just need to DELETE some
# lines of code (you shouldn't mention parentheses any more) and make a few
# small changes.  Not counting whole line deletions, I only had to change three
# lines, two of those were partial line deletions.

def evalPostfix(exprStr):
   '''Evaluate postfix arithmetic expression.'''
   pass

# Extra Time:
#     - Implement an operator that takes only one value (instead of two).  For
#       example: (sqrt 25) should evaluate to 5.  How would that look in
#       postfix?
#     - Write a function that turns fully parenthesized expressions into
#       postfix, and another function that converts the opposite direction.
#     - Make evalFullyParen() friendlier by allowing expressions NOT delimited
#       by spaces.  Single-digit version is easy.  But how to parse (12+34)?
#     - What about non-fully parenthesized expressions like (12+34+5)*6-7?