"""
Reverse Polish notation converter and calculator

Handles arithmetic and parentheses

Example:

1 + (2*3)
==>
1 2 3 * +
7
"""

ops = '+-x*/'
digits = '0123456789'


def tokenize_simple(expression):
    tokens = []
    current_token = ''
    for char in expression:
        if not current_token:
            if char in ops:
                tokens.append(char)
            elif char in digits:
                current_token += char
            elif char != ' ':
                raise ValueError
        else:
            if char in digits:
                current_token += char
            else:
                tokens.append(current_token)
                current_token = ''
                if char in ops:
                    tokens.append(char)
                elif char != ' ':
                    raise ValueError
    if current_token:
        tokens.append(current_token)

    return tokens


def tokenize(expression):
    index = 0
    tokens = []
    current_token = ''
    while index < len(expression):
        char = expression[index]
        # Numbers: The only multi-character tokens
        if char in digits:
            current_token += char
        else:
            if current_token:
                tokens.append(current_token)
                current_token = ''
            if char == '(':
                phrase, offset = tokenize(expression[index + 1:])
                tokens.append(phrase)
                index += offset
            elif char == ')':
                return tokens, index + 1
            elif char in ops:
                tokens.append(char)
        index += 1
    if current_token:
        tokens.append(current_token)
    return tokens


def rpn(expression):
    tokens = tokenize(expression) if isinstance(
        expression, str) else expression
    if len(tokens) == 1:
        return tokens[0]
    val1 = rpn(tokens[0]) if isinstance(tokens[0], list) else tokens[0]
    val2 = rpn(tokens[2]) if isinstance(tokens[2], list) else tokens[2]
    op = tokens[1]
    rpn_expr = ' '.join([val1, val2, op])
    if len(tokens) > 3:
        rpn_expr = [rpn_expr]
        rpn_expr.extend(tokens[3:])
        return rpn(rpn_expr)
    return rpn_expr


def evaluate_rpn(expression):
    # Assume RPN was generated by above method
    stack = []
    for token in expression.split():
        if token in ops:
            op = '*' if token == 'x' else token
            val2 = stack.pop()
            val1 = stack.pop()
            stack.append(eval(str(val1) + op + str(val2)))
        else:
            stack.append(token)
    if len(stack) != 1:
        raise ValueError('Invalid RPN')
    return stack[0]

if __name__ == '__main__':
    expressions = [
        "0+1",
        "20-18",
        " 3               x                  1   ",
        " 100    /                25",
        " 5000         /  ((1+1) / 2) * 1000",
        " 10 * 6 x 10 / 100",
        " (1 + 7 x 7) / 5 - 3  ",
        "10000 / ( 9 x 9 + 20 -1)-92",
        "4+5 * (333x3 /      9-110                                      )",
        " 0 x (2000 / 4 * 5 / 1 * (1 x 10))"]
    
    for expression in expressions:
        expr = rpn(expression)
        print(expr)
        print('==>', evaluate_rpn(expr))
