Create a program which parses and evaluates arithmetic expressions.

Requirements

 An abstract-syntax tree (AST) for the expression must be created from parsing the input. 
 The AST must be used in evaluation, also, so the input may not be directly evaluated (e.g. by calling eval or a similar language feature.) 
 The expression will be a string or list of symbols like "(1+3)*7". 
 The four symbols + - * / must be supported as binary operators with conventional precedence rules. 
 Precedence-control parentheses must also be supported.


Note

For those who don't remember, mathematical precedence is as follows:

 Parentheses
 Multiplication/Division (left to right)
 Addition/Subtraction (left to right)


C.f
 
 24 game Player.
 Parsing/RPN calculator algorithm.
 Parsing/RPN to infix conversion.


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
 