from RA_stack import RA_stack

# Defintion: a "token" is either an integer or a string.
# If it is a string, it can either be an operator character,
# a parenthesis -- '(' or ')' -- or the end-of-input marker,
# '$'.

def evaluate(expression):
    """Return the numeric value of an expression.
    argument: expression -- the string to evaluate"""
    
    expr_stack = RA_stack()
    expr_stack.push('$')
    tokens = tokenize(expression)
    token_number = 0
    while True:
        next_token = tokens[token_number]
        if should_accept(expr_stack, next_token):
            return expr_stack.top_minus(0)
        elif should_reduce(expr_stack, next_token):
            reduce(expr_stack)
        elif should_shift(expr_stack, next_token):
            expr_stack.push(next_token)
            token_number += 1
        else:
            raise Exception, 'evaluate: syntax error: ' + str(expr_stack) + ' ' + str(next_token)

def should_accept(expr_stack, next_token):
    """Returns a boolean: whether to accept, given the current stack and next token.
    arguments:
      expr_stack -- the current state of the evaluation stack
      next_token -- the next token"""

    if isinstance(expr_stack.top_minus(0), int) and next_token == '$':
        return expr_stack.top_minus(1) == '$'
    else:
        return False

def should_reduce(expr_stack, next_token):
    """Returns a boolean: whether to reduce, given the current stack and next token.
    arguments:
      expr_stack -- the current state of the evaluation stack
      next_token -- the next token"""

    stack_top = expr_stack.top_minus(0)
    if isinstance(stack_top, int):
        stack_second = expr_stack.top_minus(1)
        if next_token == '$':
            return is_operator(stack_second)
        elif is_operator(next_token):
            return is_operator(stack_second) and not lower_precedence(stack_second, next_token)
        elif next_token == ')':
            return is_operator(stack_second)
        else:
            return False
    elif stack_top == ')':
        return next_token == '$' or is_operator(next_token) or next_token == ')'
    else:
        return False

def should_shift(expr_stack, next_token):
    """Returns a boolean: whether to shift, given the current stack and next token.
    arguments:
      expr_stack -- the current state of the evaluation stack
      next_token -- the next token"""

    stack_top = expr_stack.top_minus(0)
    if is_operator(stack_top) or stack_top in ['$', '(']:
        return isinstance(next_token, int) or next_token == '('
    elif isinstance(stack_top, int):
        stack_second = expr_stack.top_minus(1)
        if is_operator(next_token):
            return (not is_operator(stack_second)) or lower_precedence(stack_second, next_token)
        elif next_token == ')':
            return stack_second == '('
        else:
            return False
    else:
        return False

def reduce(expr_stack):
    """Performs a reduction, updating the evaluation stack.
    arguments:
      expr_stack -- the current state of the evaluation stack"""

    if expr_stack.top_minus(0) == ')':
        value = expr_stack.top_minus(1)
        expr_stack.pop()  # remove right parenthesis
        expr_stack.pop()  # remove the value
        expr_stack.pop()  # remove left parenthesis
        expr_stack.push(value)
    else: # a simple arithmetic operation
        left_operand = expr_stack.top_minus(2)
        operator = expr_stack.top_minus(1)
        right_operand = expr_stack.top_minus(0)
        expr_stack.pop()  # remove the right operand
        expr_stack.pop()  # remove the operator
        expr_stack.pop()  # remove the left operand
        expr_stack.push(operate(operator, left_operand, right_operand))

def operate(operator, left, right):
    """Returns the numeric result of an arithmetic operation
    arguments:
       operator -- a string indicating the operation to perform
       left -- a number, the left operand
       right -- a number, the right operand"""

    if operator == '+':
        return left + right
    elif operator == '-':
        return left - right
    elif operator == '*':
        return left * right
    elif operator == '/':
        return left / right
    else:
        raise Exception, 'Unknown operator: ' + operator

def is_operator(token):
    """Returns a boolean: whether a token is an operator
    arguments:
      token -- the token"""

    return token in ['+','-','*','/']

def lower_precedence(op1, op2):
    """Returns a boolean: whether op1 is lower precedence than op2
    arguments:
      op1 -- one operator token
      op2 -- the other operator token"""

    return (op1 in ['+', '-']) and (op2 in ['*', '/'])
    
import re  # "regular expression" module used in tokenization

def tokenize(expression):
    """Return a string of tokens ending with $.
    argument: expression -- a string to break into tokens"""

    # the first step is some magic to break the expression into strings
    strings = [s for s in re.split('([0-9]+|[^0-9])', expression+'$')
               if s!='' and not s.isspace()]
    # then we use a more straightforward loop to convert digit strings
    # into actual integers
    result = []
    for s in strings:
        if s.isdigit():
            result.append(int(s))
        else:
            result.append(s)
    return result