If you are writing a hobby language, you will hit the expression problem early: 1 + 2 * 3 must parse as 1 + (2 * 3), and 2 ^ 3 ^ 2 must group to the right. Many people reach for a parser generator or a stack of grammar rules, one per precedence level. There is a smaller way, usually called Pratt parsing or precedence climbing: give every operator a pair of binding powers and recurse.
BP = {"+": (1, 2), "-": (1, 2), "*": (3, 4), "/": (3, 4), "^": (6, 5)}
def parse(tokens, min_bp=0):
tok = tokens.pop(0)
if tok == "(":
lhs = parse(tokens)
tokens.pop(0) # the ")"
else:
lhs = int(tok)
while tokens and tokens[0] in BP:
left, right = BP[tokens[0]]
if left < min_bp:
break
op = tokens.pop(0)
rhs = parse(tokens, right)
lhs = (op, lhs, rhs)
return lhs
print(parse("1 + 2 * 3".split())) # ('+', 1, ('*', 2, 3))
print(parse("2 ^ 3 ^ 2".split())) # ('^', 2, ('^', 3, 2))
print(parse("1 - 2 - 3".split())) # ('-', ('-', 1, 2), 3)
The trick is the two numbers. If left < right, the operator is left-associative (the right side binds a bit tighter, so the next operator of the same level will not be swallowed). If left > right, it is right-associative. min_bp says how strongly the thing to my left is already pulling on my left operand.
Prefix operators, function calls and ternaries all fit in the same loop with a few more lines. The linguist in me finds it beautiful that precedence is just a number and not a grammar.