Last active
December 21, 2019 00:11
-
-
Save Who23/53c0ed2bf139ca90298435dd1b2d37ea to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # 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!") |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment