Another Rosetta Code task led to this fun little program: an expression parser (Try It!). You type in some expression composed of numbers, +, -, *, /, and parentheses, and it cranks out an answer.
I kept it very simple for the sake of the example; it doesn't even handle negative numbers. But it does correctly handle operator precedence and parentheses. Here's the code:
Expr = {}
Expr.eval = 0
BinaryExpr = new Expr
BinaryExpr.eval = function()
if self.op == "+" then return self.lhs.eval + self.rhs.eval
if self.op == "-" then return self.lhs.eval - self.rhs.eval
if self.op == "*" then return self.lhs.eval * self.rhs.eval
if self.op == "/" then return self.lhs.eval / self.rhs.eval
end function
binop = function(lhs, op, rhs)
e = new BinaryExpr
e.lhs = lhs
e.op = op
e.rhs = rhs
return e
end function
parseAtom = function(inp)
tok = inp.pull
if tok >= "0" and tok <= "9" then
e = new Expr
e.eval = val(tok)
while inp and inp[0] >= "0" and inp[0] <= "9"
e.eval = e.eval * 10 + val(inp.pull)
end while
else if tok == "(" then
e = parseAddSub(inp)
inp.pull // swallow closing ")"
return e
else
print "Unexpected token: " + tok
exit
end if
return e
end function
parseMultDiv = function(inp)
next = @parseAtom
e = next(inp)
while inp and (inp[0] == "*" or inp[0] == "/")
e = binop(e, inp.pull, next(inp))
end while
return e
end function
parseAddSub = function(inp)
next = @parseMultDiv
e = next(inp)
while inp and (inp[0] == "+" or inp[0] == "-")
e = binop(e, inp.pull, next(inp))
end while
return e
end function
while true
s = input("Enter expression: ").replace(" ","")
if not s then break
inp = split(s, "")
ast = parseAddSub(inp)
print ast.eval
end while
A bit long, but pretty simple for what it does! The start of the parsing is in parseAddSub, which is looking for an expression, followed by + or -, followed by another expression. Those other expressions it's looking for? It finds them by calling parseMultDiv, which is the next highest level of precedence. And that does basically the same thing, except that its next highest level of precedence is parseAtom, which is responsible for parsing numbers... or, if it sees a parenthesis, it calls parseAtom, recursing to get the whole expression inside parentheses.
Could you figure out how to add the ^ operator to this? Hint: it should have higher precedence than multiplication and division, but lower precedence than atoms (numbers and parentheses). Give it a try!
