Last active
July 18, 2020 03:27
-
-
Save krupenik/3de1c7e0f67e1c82fe73733830fc5e29 to your computer and use it in GitHub Desktop.
shunting-yard parser in python3
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
import math | |
import operator | |
import re | |
functions = { | |
"sqrt": math.sqrt, | |
"lg": math.log10, | |
"ln": math.log, | |
"log": math.log, | |
} | |
operators = { | |
"**": (operator.pow, 30), | |
"*": (operator.mul, 20), | |
"/": (operator.truediv, 20), | |
"+": (operator.add, 10), | |
"-": (operator.sub, 10), | |
} | |
def _parse(expr="", result=[], op_stack=[]): | |
tokens = [m[0] for m in re.findall(r'(\d+(\.\d+)?|\+|\-|\*+|\/|\w+|\(|\)|,)', expr)] | |
for token in tokens: | |
if re.match(r'\d+(\.\d+)?', token): | |
result.append(float(token)) | |
elif token in functions.keys() or token == "(": | |
op_stack.append(token) | |
elif token in operators.keys(): | |
while op_stack and op_stack[-1] in operators.keys() and (operators[op_stack[-1]][1] > operators[token][1] or (token != "**" and operators[op_stack[-1]][1] == operators[token][1])): | |
result.append(op_stack.pop()) | |
op_stack.append(token) | |
elif token == ")": | |
while op_stack[-1] != "(": | |
result.append(op_stack.pop()) | |
if op_stack[-1] == "(": | |
op_stack.pop() | |
else: | |
raise "mismatched parentheses" | |
if op_stack and op_stack[-1] in functions.keys(): | |
result.append(op_stack.pop()) | |
elif token == ",": | |
while op_stack[-1] != "(": | |
result.append(op_stack.pop()) | |
else: | |
raise "wtf" | |
while op_stack: | |
if op_stack[-1] == "(": | |
raise "mismatched parentheses" | |
result.append(op_stack.pop()) | |
return result | |
def _compute(seq, op_stack=[]): | |
for item in seq: | |
if isinstance(item, float): | |
op_stack.append(item) | |
elif item == "log": | |
op2 = op_stack.pop() | |
op1 = op_stack.pop() | |
op_stack.append(functions["log"](op1, op2)) | |
elif item in operators.keys(): | |
op2 = op_stack.pop() | |
op1 = op_stack.pop() | |
op_stack.append(operators[item][0](op1, op2)) | |
elif item in functions.keys(): | |
op_stack.append(functions[item](op_stack.pop())) | |
else: | |
raise "wtf" | |
return op_stack.pop() | |
def calc(expr=""): | |
return _compute(_parse(expr)) | |
print(calc("2+2*2+lg(10)-log((2+2)**3**2, 16)")) | |
print(calc("log(10*10, 10)")) | |
print(calc("4**3**2")) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment