expression.py

# A calculator based on the Shunting-Yard algorithm
# https://en.wikipedia.org/wiki/Shunting-yard_algorithm
# https://en.wikipedia.org/wiki/Reverse_Polish_notation

OP_PRECEDENCE = {"(": 1,
                 ")": 1,
                 "+": 2,
                 "-": 2,
                 "*": 3,
                 "/": 3,
                 "^": 4}

# 0 is left, 1 is right
OP_ASSOCIATION_RIGHT = {"+": 0,
                        "-": 0,
                        "*": 0,
                        "/": 0,
                        "^": 1}

OP_FUNCTIONS = {"+": lambda a, b: a + b,
                "-": lambda a, b: a - b,
                "*": lambda a, b: a * b,
                "/": lambda a, b: a / b,
                "^": lambda a, b: a ** b}

while True:
    try:
        raw_infix = input(">>> ")

        ############# Create Infix #############
        # Creates infix with each token in a list.

        pending_char = ""
        infix = []
        for char in raw_infix:
            if char in ["1", "2", "3", "4", "5", "6", "7", "8", "9", "0"]:
                pending_char += char
            elif char in ["+", "-", "*", "/", "^", "(", ")"]:
                # operators come before and after parens, so pending_char would be ""
                if pending_char == "" and not (char == "(" or infix[-1] == ")"):
                    print("Invalid expression!")
                    raise Exception("Invalid Expression!")

                if pending_char != "":
                    infix.append(float(pending_char))
                infix.append(char)

                pending_char = ""

        # add the remaining number if it is not blank
        if pending_char != "":
            infix.append(float(pending_char))

        ############# shunting yard algorithm #############

        opStack = []
        output = []

        for token in infix:
            if isinstance(token, float):
                output.append(token)
            elif token in ["+", "-", "*", "/", "^"]:
                # pop higher precedence operators to output. Then add itself to the opstack.
                if opStack:
                    if OP_ASSOCIATION_RIGHT[token]:
                        while opStack and OP_PRECEDENCE[opStack[-1]] > OP_PRECEDENCE[token]:
                            output.append(opStack.pop())
                    else:
                        while opStack and OP_PRECEDENCE[opStack[-1]] >= OP_PRECEDENCE[token]:
                            output.append(opStack.pop())

                opStack.append(token)

            elif token == "(":
                opStack.append(token)
            elif token == ")":
                # pop operators until a left paren is reached
                while output[-1] != "(":
                    output.append(opStack.pop())

                # pop left paren
                output.pop()

        # pop remaining operators to output.
        output += opStack[::-1]

        ############# rpn evaluation #############

        evalStack = []
        for token in output:
            if isinstance(token, float):
                evalStack.append(token)
            if token in ["+", "-", "*", "/", "^"]:
                a = evalStack.pop()
                b = evalStack.pop()

                evalStack.append(OP_FUNCTIONS[token](b, a))

        # print output.
        print(evalStack[0])
    except KeyboardInterrupt:
        print()
        quit()
    except:
        print("Invalid expression!")