Skip to content

Instantly share code, notes, and snippets.

@krupenik
Last active July 18, 2020 03:27
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save krupenik/3de1c7e0f67e1c82fe73733830fc5e29 to your computer and use it in GitHub Desktop.
Save krupenik/3de1c7e0f67e1c82fe73733830fc5e29 to your computer and use it in GitHub Desktop.
shunting-yard parser in python3
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