Arithmetic evaluation
You are encouraged to solve this task according to the task description, using any language you may know.
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
Ada
ALGOL 68
<lang algol68>INT base=10; MODE FIXED = LONG REAL; # numbers in the format 9,999.999 #
- IF build abstract syntax tree and then EVAL tree #
MODE AST = UNION(NODE, FIXED); MODE NUM = REF AST; MODE NODE = STRUCT(NUM a, PROC (FIXED,FIXED)FIXED op, NUM b);
OP EVAL = (NUM ast)FIXED:(
CASE ast IN (FIXED num): num, (NODE fork): (op OF fork)(EVAL( a OF fork), EVAL (b OF fork)) ESAC
);
OP + = (NUM a,b)NUM: ( HEAP AST := NODE(a, (FIXED a,b)FIXED:a+b, b) ); OP - = (NUM a,b)NUM: ( HEAP AST := NODE(a, (FIXED a,b)FIXED:a-b, b) ); OP * = (NUM a,b)NUM: ( HEAP AST := NODE(a, (FIXED a,b)FIXED:a*b, b) ); OP / = (NUM a,b)NUM: ( HEAP AST := NODE(a, (FIXED a,b)FIXED:a/b, b) ); OP **= (NUM a,b)NUM: ( HEAP AST := NODE(a, (FIXED a,b)FIXED:a**b, b) );
- ELSE simply use REAL arithmetic with no abstract syntax tree at all # CO
MODE NUM = FIXED, AST = FIXED; OP EVAL = (FIXED num)FIXED: num;
- FI# END CO
MODE LEX = PROC (TOK)NUM; MODE MONADIC =PROC (NUM)NUM; MODE DIADIC = PROC (NUM,NUM)NUM;
MODE TOK = CHAR; MODE ACTION = UNION(STACKACTION, LEX, MONADIC, DIADIC); MODE OPVAL = STRUCT(INT prio, ACTION action); MODE OPITEM = STRUCT(TOK token, OPVAL opval);
[256]STACKITEM stack; MODE STACKITEM = STRUCT(NUM value, OPVAL op); MODE STACKACTION = PROC (REF STACKITEM)VOID;
PROC begin = (REF STACKITEM top)VOID: prio OF op OF top -:= +10; PROC end = (REF STACKITEM top)VOID: prio OF op OF top -:= -10;
OP ** = (COMPL a,b)COMPL: complex exp(complex ln(a)*b);
[8]OPITEM op list :=(
- OP PRIO ACTION #
("^", (8, (NUM a,b)NUM: a**b)),
("*", (7, (NUM a,b)NUM: a*b)),
("/", (7, (NUM a,b)NUM: a/b)),
("+", (6, (NUM a,b)NUM: a+b)),
("-", (6, (NUM a,b)NUM: a-b)),
("(",(+10, begin)),
(")",(-10, end)),
("?", (9, LEX:SKIP))
);
PROC op dict = (TOK op)REF OPVAL:(
- This can be unrolled to increase performance #
REF OPITEM candidate; FOR i TO UPB op list WHILE candidate := op list[i];
- WHILE # op /= token OF candidate DO
SKIP OD; opval OF candidate
);
PROC build ast = (STRING expr)NUM:(
INT top:=0;
PROC compress ast stack = (INT prio, NUM in value)NUM:(
NUM out value := in value;
FOR loc FROM top BY -1 TO 1 WHILE
REF STACKITEM stack top := stack[loc];
# WHILE # ( top >= LWB stack | prio <= prio OF op OF stack top | FALSE ) DO
top := loc - 1;
out value :=
CASE action OF op OF stack top IN
(MONADIC op): op(value OF stack top), # not implemented #
(DIADIC op): op(value OF stack top,out value)
ESAC
OD;
out value
);
NUM value := NIL; FIXED num value; INT decimal places;
FOR i TO UPB expr DO
TOK token = expr[i];
REF OPVAL this op := op dict(token);
CASE action OF this op IN
(STACKACTION action):(
IF prio OF thisop = -10 THEN
value := compress ast stack(0, value)
FI;
IF top >= LWB stack THEN
action(stack[top])
FI
),
(LEX):( # a crude lexer #
SHORT INT digit = ABS token - ABS "0";
IF 0<= digit AND digit < base THEN
IF NUM(value) IS NIL THEN # first digit #
decimal places := 0;
value := HEAP AST := num value := digit
ELSE
NUM(value) := num value := IF decimal places = 0
THEN
num value * base + digit
ELSE
decimal places *:= base;
num value + digit / decimal places
FI
FI
ELIF token = "." THEN
decimal places := 1
ELSE
SKIP # and ignore spaces and any unrecognised characters #
FI
),
(MONADIC): SKIP, # not implemented #
(DIADIC):(
value := compress ast stack(prio OF this op, value);
IF top=UPB stack THEN index error FI;
stack[top+:=1]:=STACKITEM(value, this op);
value:=NIL
)
ESAC
OD;
compress ast stack(-max int, value)
);
test:(
printf(($" euler's number is about: "g(-long real width,long real width-2)l$,
EVAL build ast("1+1+(1+(1+(1+(1+(1+(1+(1+(1+(1+(1+(1+(1+(1+1/15)/14)/13)/12)/11)/10)/9)/8)/7)/6)/5)/4)/3)/2")));
SKIP EXIT
index error:
printf(("Stack over flow"))
)</lang> Output:
euler's number is about: 2.71828182845899446428546958
AutoHotkey
<lang AutoHotkey>/* hand coded recursive descent parser expr : term ( ( PLUS | MINUS ) term )* ; term : factor ( ( MULT | DIV ) factor )* ; factor : NUMBER | '(' expr ')';
- /
calcLexer := makeCalcLexer() string := "((3+4)*(7*9)+3)+4" tokens := tokenize(string, calcLexer) msgbox % printTokens(tokens) ast := expr() msgbox % printTree(ast) msgbox % expression := evalTree(ast) filedelete expression.ahk fileappend, % "msgbox % " expression, expression.ahk run, expression.ahk return
expr()
{
global tokens
ast := object(1, "expr")
if node := term()
ast._Insert(node)
loop
{
if peek("PLUS") or peek("MINUS")
{
op := getsym()
newop := object(1, op.type, 2, op.value)
node := term()
ast._Insert(newop)
ast._Insert(node)
}
Else
Break
}
return ast
}
term() {
global tokens
tree := object(1, "term")
if node := factor()
tree._Insert(node)
loop
{
if peek("MULT") or peek("DIV")
{
op := getsym()
newop := object(1, op.type, 2, op.value)
node := factor()
tree._Insert(newop)
tree._Insert(node)
}
else
Break
}
return tree
}
factor() {
global tokens
if peek("NUMBER")
{
token := getsym()
tree := object(1, token.type, 2, token.value)
return tree
}
else if peek("OPEN")
{
getsym()
tree := expr()
if peek("CLOSE")
{
getsym()
return tree
}
else
error("miss closing parentheses ")
}
else
error("no factor found")
}
peek(type, n=1) { global tokens
if (tokens[n, "type"] == type) return 1
}
getsym(n=1) { global tokens return token := tokens._Remove(n) }
error(msg) { global tokens msgbox % msg " at:`n" printToken(tokens[1]) }
printTree(ast)
{
if !ast
return
n := 0
loop
{
n += 1
if !node := ast[n]
break
if !isobject(node)
treeString .= node
else
treeString .= printTree(node)
}
return ("(" treeString ")" )
}
evalTree(ast) { if !ast return
n := 1
loop
{
n += 1
if !node := ast[n]
break
if !isobject(node)
treeString .= node
else
treeString .= evalTree(node)
}
if (n == 3) return treeString
return ("(" treeString ")" )
}
- include calclex.ahk</lang>
calclex.ahk<lang AutoHotkey>tokenize(string, lexer) {
stringo := string ; store original string locationInString := 1 size := strlen(string) tokens := object()
start:
Enum := Lexer._NewEnum()
While Enum[type, value] ; loop through regular expression lexing rules
{
if (1 == regexmatch(string, value, tokenValue))
{
token := object()
token.pos := locationInString
token.value := tokenValue
token.length := strlen(tokenValue)
token.type := type
tokens._Insert(token)
locationInString += token.length
string := substr(string, token.length + 1)
goto start
}
continue
}
if (locationInString < size)
msgbox % "unrecognized token at " substr(stringo, locationInstring)
return tokens
}
makeCalcLexer() {
calcLexer := object()
PLUS := "\+"
MINUS := "-"
MULT := "\*"
DIV := "/"
OPEN := "\("
CLOSE := "\)"
NUMBER := "\d+"
WS := "[ \t\n]+"
END := "\."
RULES := "PLUS,MINUS,MULT,DIV,OPEN,CLOSE,NUMBER,WS,END"
loop, parse, rules, `,
{
type := A_LoopField
value := %A_LoopField%
calcLexer._Insert(type, value)
}
return calcLexer
}
printTokens(tokens) {
loop % tokens._MaxIndex()
{
tokenString .= printToken(tokens[A_Index]) "`n`n"
}
return tokenString
}
printToken(token)
{
string := "pos= " token.pos "`nvalue= " token.value "`ntype= " token.type return string
}</lang>
C
C++
<lang cpp> #include <boost/spirit.hpp>
#include <boost/spirit/tree/ast.hpp>
#include <string>
#include <cassert>
#include <iostream>
#include <istream>
#include <ostream>
using boost::spirit::rule;
using boost::spirit::parser_tag;
using boost::spirit::ch_p;
using boost::spirit::real_p;
using boost::spirit::tree_node;
using boost::spirit::node_val_data;
// The grammar
struct parser: public boost::spirit::grammar<parser>
{
enum rule_ids { addsub_id, multdiv_id, value_id, real_id };
struct set_value
{
set_value(parser const& p): self(p) {}
void operator()(tree_node<node_val_data<std::string::iterator,
double> >& node,
std::string::iterator begin,
std::string::iterator end) const
{
node.value.value(self.tmp);
}
parser const& self;
};
mutable double tmp;
template<typename Scanner> struct definition
{
rule<Scanner, parser_tag<addsub_id> > addsub;
rule<Scanner, parser_tag<multdiv_id> > multdiv;
rule<Scanner, parser_tag<value_id> > value;
rule<Scanner, parser_tag<real_id> > real;
definition(parser const& self)
{
using namespace boost::spirit;
addsub = multdiv
>> *((root_node_d[ch_p('+')] | root_node_d[ch_p('-')]) >> multdiv);
multdiv = value
>> *((root_node_d[ch_p('*')] | root_node_d[ch_p('/')]) >> value);
value = real | inner_node_d[('(' >> addsub >> ')')];
real = leaf_node_d[access_node_d[real_p[assign_a(self.tmp)]][set_value(self)]];
}
rule<Scanner, parser_tag<addsub_id> > const& start() const
{
return addsub;
}
};
};
template<typename TreeIter>
double evaluate(TreeIter const& i)
{
double op1, op2;
switch (i->value.id().to_long())
{
case parser::real_id:
return i->value.value();
case parser::value_id:
case parser::addsub_id:
case parser::multdiv_id:
op1 = evaluate(i->children.begin());
op2 = evaluate(i->children.begin()+1);
switch(*i->value.begin())
{
case '+':
return op1 + op2;
case '-':
return op1 - op2;
case '*':
return op1 * op2;
case '/':
return op1 / op2;
default:
assert(!"Should not happen");
}
default:
assert(!"Should not happen");
}
return 0;
}
// the read/eval/write loop
int main()
{
parser eval;
std::string line;
while (std::cout << "Expression: "
&& std::getline(std::cin, line)
&& !line.empty())
{
typedef boost::spirit::node_val_data_factory<double> factory_t;
boost::spirit::tree_parse_info<std::string::iterator, factory_t> info =
boost::spirit::ast_parse<factory_t>(line.begin(), line.end(),
eval, boost::spirit::space_p);
if (info.full)
{
std::cout << "Result: " << evaluate(info.trees.begin()) << std::endl;
}
else
{
std::cout << "Error in expression." << std::endl;
}
}
};</lang>
Common Lisp
The following code parses a string into a sequence of tokens. The sequence of tokens includes :lparen and :rparen indicating left and right parenthesis, respectively. That sequence of tokens is then transformed by replacing subsequences of the form :lparen ... :rparen with a sublist containing the tokens between the :lparen and :rparen. The resulting tree is then simplified by replacing any subsequence of the form A x B y C … with either (A x B) y C … or A x (B y C) depending on the relative precedence of x and y. This produces a syntax tree each of whose elements is either a node representing an integer, (:integer . n), a list containing a single expression, (exp), or an operation, (e1 op e2). Evaluating such a syntax tree is then trivial. This implementation can read integers, and produce integral and rational values.
<lang lisp>(defun tokenize-stream (stream)
(labels ((whitespace-p (char)
(find char #(#\space #\newline #\return #\tab)))
(consume-whitespace ()
(loop while (whitespace-p (peek-char nil stream nil #\a))
do (read-char stream)))
(read-integer ()
(loop while (digit-char-p (peek-char nil stream nil #\space))
collect (read-char stream) into digits
finally (return (parse-integer (coerce digits 'string))))))
(consume-whitespace)
(let ((c (peek-char nil stream nil nil)))
(multiple-value-bind (token value)
(case c
((nil) :eof)
((#\() :lparen)
((#\)) :rparen)
((#\*) :multiply)
((#\/) :divide)
((#\+) :add)
((#\-) :subtract)
(otherwise
(unless (digit-char-p c)
(cerror "Skip it." "Unexpected character ~w." c)
(read-char stream)
(return-from tokenize-stream
(tokenize-stream stream)))
(values :integer (read-integer))))
(unless (find token #(:integer :eof))
(read-char stream))
(if (not (eql token :integer)) token
(cons token value))))))
(defun group-parentheses (tokens &optional (delimited nil))
(do ((new-tokens '()))
((endp tokens)
(when delimited
(cerror "Insert it." "Expected right parenthesis."))
(values (nreverse new-tokens) '()))
(let ((token (pop tokens)))
(case token
((:lparen)
(multiple-value-bind (group remaining-tokens)
(group-parentheses tokens t)
(setf new-tokens (cons group new-tokens)
tokens remaining-tokens)))
((:rparen)
(if (not delimited)
(cerror "Ignore it." "Unexpected right parenthesis.")
(return (values (nreverse new-tokens) tokens))))
(otherwise
(push token new-tokens))))))
(defun group-operations (expression)
(flet ((gop (exp) (group-operations exp)))
(if (eql (car expression) :integer) expression
(destructuring-bind (A &optional (x nil xp) B (y nil yp) C &rest others)
expression
(cond
((not xp) (gop A))
((not yp) (list (gop A) x (gop B)))
(t (let ((a (gop A)) (B (gop B)) (C (gop C)))
(if (and (find x #(:add :subtract))
(find y #(:multiply :divide)))
(gop (list* A x (list B y C) others))
(gop (list* (list A x B) y C others))))))))))
(defun evaluate-expression (expression)
(cond
((eql (car expression) :integer)
(cdr expression))
((endp (cdr expression))
(evaluate-expression (car expression)))
(t (destructuring-bind (e1 op e2) expression
(let ((v1 (evaluate-expression e1))
(v2 (evaluate-expression e2)))
(ecase op
(:add (+ v1 v2))
(:subtract (- v1 v2))
(:multiply (* v1 v2))
(:divide (/ v1 v2))))))))
(defun evaluate (string)
(with-input-from-string (in string)
(evaluate-expression
(group-operations
(group-parentheses
(loop for token = (tokenize-stream in)
until (eql :eof token)
collect token))))))</lang>
Examples
> (evaluate "1 - 5 * 2 / 20 + 1")
3/2
> (evaluate "(1 - 5) * 2 / (20 + 1)")
-8/21
> (evaluate "2 * (3 + ((5) / (7 - 11)))")
7/2
> (evaluate "(2 + 3) / (10 - 5)")
1
Examples of error handling
> (evaluate "(3 * 2) a - (1 + 2) / 4")
Error: Unexpected character a.
1 (continue) Skip it.
2 (abort) Return to level 0.
3 Return to top loop level 0.
Type :b for backtrace, :c <option number> to proceed, or :? for other options
: 1 > :c 1
21/4
> (evaluate "(3 * 2) - (1 + 2) / (4")
Error: Expected right parenthesis.
1 (continue) Insert it.
2 (abort) Return to level 0.
3 Return to top loop level 0.
Type :b for backtrace, :c <option number> to proceed, or :? for other options
: 1 > :c 1
21/4
D
Following the previous number-operator dual stacks approach, an AST is built while previous version is evaluating the expression value. After the AST tree is constructed, a visitor pattern is used to display the AST structure and calculate the value.
<lang d>//module evaluate ;
import std.stdio, std.string, std.ctype, std.conv ;
// simple stack template
void push(T)(inout T[] stk, T top) { stk ~= top ; }
T pop(T)(inout T[] stk, bool discard = true) {
T top ;
if (stk.length == 0) throw new Exception("Stack Empty") ;
top = stk[$-1] ;
if (discard) stk.length = stk.length - 1 ;
return top ;
}
alias int Type ;
enum { Num, OBkt, CBkt, Add, Sub, Mul, Div } ; // Type
string[] opChar = ["#","(",")","+","-","*","/"] ;
int[] opPrec = [0,-9,-9,1,1,2,2] ;
abstract class Visitor { void visit(XP e) ; }
class XP {
Type type ;
string str ;
int pos ; // optional, for dispalying AST struct.
XP LHS, RHS = null ;
this(string s = ")", int p = -1) {
str = s ; pos = p ;
type = Num ;
for(Type t = Div ; t > Num ; t--)
if(opChar[t] == s) type = t ;
}
int opCmp(XP rhs) { return opPrec[type] - opPrec[rhs.type] ; }
void accept(Visitor v) { v.visit(this) ; } ;
}
class AST {
XP root ;
XP[] num, opr ;
string xpr, token ;
int xpHead, xpTail ;
void joinXP(XP x) { x.RHS = num.pop() ; x.LHS = num.pop() ; num.push(x) ; }
string nextToken() {
while (xpHead < xpr.length && xpr[xpHead] == ' ')
xpHead++ ; // skip spc
xpTail = xpHead ;
if(xpHead < xpr.length) {
token = xpr[xpTail..xpTail+1] ;
switch(token) {
case "(",")","+","-","*","/": // valid non-number
xpTail++ ;
return token ;
default: // should be number
if(isdigit(token[0])) {
while(xpTail < xpr.length && isdigit(xpr[xpTail]))
xpTail++ ;
return xpr[xpHead..xpTail] ;
} // else may be error
} // end switch
}
if(xpTail < xpr.length)
throw new Exception("Invalid Char <" ~ xpr[xpTail] ~ ">") ;
return null ;
} // end nextToken
AST parse(string s) {
bool expectingOP ;
xpr = s ;
try {
xpHead = xpTail = 0 ;
num = opr = null ;
root = null ;
opr.push(new XP) ; // CBkt, prevent evaluate null OP precidence
while((token = nextToken) !is null) {
XP tokenXP = new XP(token, xpHead) ;
if(expectingOP) { // process OP-alike XP
switch(token) {
case ")":
while(opr.pop(false).type != OBkt)
joinXP(opr.pop()) ;
opr.pop() ;
expectingOP = true ; break ;
case "+","-","*","/":
while (tokenXP <= opr.pop(false))
joinXP(opr.pop()) ;
opr.push(tokenXP) ;
expectingOP = false ; break ;
default:
throw new Exception("Expecting Operator or ), not <" ~ token ~ ">") ;
}
} else { // process Num-alike XP
switch(token) {
case "+","-","*","/",")":
throw new Exception("Expecting Number or (, not <" ~ token ~ ">") ;
case "(":
opr.push(tokenXP) ;
expectingOP = false ; break ;
default: // number
num.push(tokenXP) ;
expectingOP = true ;
}
}
xpHead = xpTail ;
} // end while
while (opr.length > 1) // join pending Op
joinXP(opr.pop()) ;
}catch(Exception e) {
writefln("%s\n%s\n%s^", e.msg, xpr, repeat(" ", xpHead)) ;
root = null ;
return this ;
}
if(num.length != 1) { // should be one XP left
writefln("Parse Error...") ;
root = null ;
} else
root = num.pop() ;
return this ;
} // end Parse
} // end class AST
// for display AST fancy struct
void ins(inout char[][] s, string v, int p, int l) {
while(s.length < l + 1) s.length = s.length + 1 ;
while(s[l].length < p + v.length + 1) s[l] ~= " " ;
s[l][p..p +v.length] = v ;
}
class calcVis : Visitor {
int result, level = 0 ;
string Result = null ;
char[][] Tree = null ;
static void opCall(AST a) {
if (a && a.root) {
calcVis c = new calcVis ;
a.root.accept(c) ;
for(int i = 1; i < c.Tree.length ; i++) { // more fancy
bool flipflop = false ; char mk = '.' ;
for(int j = 0 ; j < c.Tree[i].length ; j++) {
while(j >= c.Tree[i-1].length) c.Tree[i-1] ~= " " ;
char c1 = c.Tree[i][j] ; char c2 = c.Tree[i-1][j] ;
if(flipflop && (c1 == ' ') && c2 == ' ')
c.Tree[i-1][j] = mk ;
if(c1 != mk && c1 != ' ' && (j == 0 || !isdigit(c.Tree[i][j-1])))
flipflop = !flipflop ;
}
}
foreach(t; c.Tree) writefln(t) ;
writefln("%s ==>\n%s = %s", a.xpr,c.Result,c.result) ;
} else
writefln("Evalute invalid or null Expression") ;
}
void visit(XP xp) {// calc. the value, display AST struct and eval order.
ins(Tree, xp.str, xp.pos, level) ;
level++ ;
if (xp.type == Num) {
Result ~= xp.str ;
result = toInt(xp.str) ;
} else {
Result ~= "(" ;
xp.LHS.accept(this) ;
int lhs = result ;
Result ~= opChar[xp.type] ;
xp.RHS.accept(this) ;
Result ~= ")" ;
switch(xp.type) {
case Add: result = lhs + result ; break ;
case Sub: result = lhs - result ; break ;
case Mul: result = lhs * result ; break ;
case Div: result = lhs / result ; break ;
default: throw new Exception("Invalid type") ;
}
} //
level-- ;
}
}
void main(string[] args) {
string expression = args.length > 1 ? join(args[1..$]," ") :
"1 + 2*(3 - 2*(3 - 2)*((2 - 4)*5 - 22/(7 + 2*(3 - 1)) - 1)) + 1" ; // should be 60
calcVis((new AST).parse(expression)) ;
}</lang>
E
While the task requirements specify not evaluating using the language's built-in eval, they don't say that you have to write your own parser...
<lang e>def eParser := <elang:syntax.makeEParser>
def LiteralExpr := <elang:evm.makeLiteralExpr>.asType()
def arithEvaluate(expr :String) {
def ast := eParser(expr)
def evalAST(ast) {
return switch (ast) {
match e`@a + @b` { evalAST(a) + evalAST(b) }
match e`@a - @b` { evalAST(a) - evalAST(b) }
match e`@a * @b` { evalAST(a) * evalAST(b) }
match e`@a / @b` { evalAST(a) / evalAST(b) }
match e`-@a` { -(evalAST(a)) }
match l :LiteralExpr { l.getValue() }
}
}
return evalAST(ast)
}</lang>
Parentheses are handled by the parser.
<lang e>? arithEvaluate("1 + 2")
- value: 3
? arithEvaluate("(1 + 2) * 10 / 100")
- value: 0.3
? arithEvaluate("(1 + 2 / 2) * (5 + 5)")
- value: 20.0</lang>
Factor
<lang factor>USING: accessors kernel locals math math.parser peg.ebnf ;
IN: rosetta.arith
TUPLE: operator left right ;
TUPLE: add < operator ; C: <add> add
TUPLE: sub < operator ; C: sub
TUPLE: mul < operator ; C: <mul> mul
TUPLE: div < operator ; C:
div
EBNF: expr-ast
spaces = [\n\t ]*
digit = [0-9]
number = (digit)+ => [[ string>number ]]
value = spaces number:n => n
| spaces "(" exp:e spaces ")" => e
fac = fac:a spaces "*" value:b => [[ a b <mul> ]]
| fac:a spaces "/" value:b => [[ a b ]]
| value
exp = exp:a spaces "+" fac:b => [[ a b <add> ]]
| exp:a spaces "-" fac:b => [[ a b ]]
| fac
main = exp:e spaces !(.) => e
- EBNF
GENERIC: eval-ast ( ast -- result )
M: number eval-ast ;
- recursive-eval ( ast -- left-result right-result )
[ left>> eval-ast ] [ right>> eval-ast ] bi ;
M: add eval-ast recursive-eval + ;
M: sub eval-ast recursive-eval - ;
M: mul eval-ast recursive-eval * ;
M: div eval-ast recursive-eval / ;
- evaluate ( string -- result )
expr-ast eval-ast ;</lang>
Go
Haskell
<lang haskell>import Text.ParserCombinators.Parsec
import Text.ParserCombinators.Parsec.Expr
data Exp = Num Int
| Add Exp Exp
| Sub Exp Exp
| Mul Exp Exp
| Div Exp Exp
expr = buildExpressionParser table factor
table = [[op "*" (Mul) AssocLeft, op "/" (Div) AssocLeft]
,[op "+" (Add) AssocLeft, op "-" (Sub) AssocLeft]]
where op s f assoc = Infix (do string s; return f) assoc
factor = do char '(' ; x <- expr ; char ')'
return x
<|> do ds <- many1 digit
return $ Num (read ds)
evaluate (Num x) = fromIntegral x
evaluate (Add a b) = (evaluate a) + (evaluate b)
evaluate (Sub a b) = (evaluate a) - (evaluate b)
evaluate (Mul a b) = (evaluate a) * (evaluate b)
evaluate (Div a b) = (evaluate a) `div` (evaluate b)
solution exp = case parse expr [] exp of
Right expr -> evaluate expr
Left _ -> error "Did not parse"</lang>
Icon and Unicon
A compact recursive descent parser using Hanson's device. This program
- handles left and right associativity and different precedences
- is ready to handle any number of infix operators without adding more functions to handle the precedences
- accepts integers, reals, and radix constants (e.g. 3r10 is 3 in base 3)
- currently accepts the Icon operators + - * / % (remainder) and ^ (exponentiation) and unary operators + and -
- string invocation is used to evaluate binary operators hence other Icon binary operators (including handle multiple character ones) can be easily added
- uses Icon style type coercion on operands
- represents the AST as a nested list eliminating unneeded parenthesis
- Notice that the code looks remarkably like a typical grammar, rather than being an opaque cryptic solution
- Does not rely on any library to silently solve 1/2 the problem; in fact, this code would probably suit being put into a library almost verbatim
<lang Icon>procedure main() #: simple arithmetical parser / evaluator
write("Usage: Input expression = Abstract Syntax Tree = Value, ^Z to end.")
repeat {
writes("Input expression : ")
if not writes(line := read()) then break
if map(line) ? { (x := E()) & pos(0) } then
write(" = ", showAST(x), " = ", evalAST(x))
else
write(" rejected")
}
end
procedure evalAST(X) #: return the evaluated AST
local x
if type(X) == "list" then {
x := evalAST(get(X))
while x := get(X)(x, evalAST(get(X) | stop("Malformed AST.")))
}
return \x | X
end
procedure showAST(X) #: return a string representing the AST
local x,s
s := ""
every x := !X do
s ||:= if type(x) == "list" then "(" || showAST(x) || ")" else x
return s
end
- When you're writing a big parser, a few utility recognisers are very useful
procedure ws() # skip optional whitespace
suspend tab(many(' \t')) | ""
end
procedure digits()
suspend tab(many(&digits))
end
procedure radixNum(r) # r sets the radix
static chars
initial chars := &digits || &lcase
suspend tab(many(chars[1 +: r]))
end
global token
record HansonsDevice(precedence,associativity)
procedure opinfo()
static O
initial {
O := HansonsDevice([], table(&null)) # parsing table
put(O.precedence, ["+", "-"], ["*", "/", "%"], ["^"]) # Lowest to Highest precedence
every O.associativity[!!O.precedence] := 1 # default to 1 for LEFT associativity
O.associativity["^"] := 0 # RIGHT associativity
}
return O
end
procedure E(k) #: Expression
local lex, pL
static opT
initial opT := opinfo()
/k := 1
lex := []
if not (pL := opT.precedence[k]) then # this op at this level?
put(lex, F())
else {
put(lex, E(k + 1))
while ws() & put(lex, token := =!pL) do
put(lex, E(k + opT.associativity[token]))
}
suspend if *lex = 1 then lex[1] else lex # strip useless []
end
procedure F() #: Factor
suspend ws() & ( # skip optional whitespace, and ...
(="+" & F()) | # unary + and a Factor, or ...
(="-" || V()) | # unary - and a Value, or ...
(="-" & [-1, "*", F()]) | # unary - and a Factor, or ...
2(="(", E(), ws(), =")") | # parenthesized subexpression, or ...
V() # just a value
)
end
procedure V() #: Value
local r
suspend ws() & numeric( # skip optional whitespace, and ...
=(r := 1 to 36) || ="r" || radixNum(r) | # N-based number, or ...
digits() || (="." || digits() | "") || exponent() # plain number with optional fraction
)
end
procedure exponent()
suspend tab(any('eE')) || =("+" | "-" | "") || digits() | ""
end</lang>
Sample Output:
#matheval.exe
Usage: Input expression = Abstract Syntax Tree = Value, ^Z to end.
Input expression : 1
1 = 1 = 1
Input expression : -1
-1 = -1 = -1
Input expression : (-15/2.0)
(-15/2.0) = -15/2.0 = -7.5
Input expression : -(15/2.0)
-(15/2.0) = -1*(15/2.0) = -7.5
Input expression : 2+(3-4)*6/5^2^3%3
2+(3-4)*6/5^2^3%3 = 2+((3-4)*6/(5^(2^3))%3) = 2
Input expression : 1+2+3+4
1+2+3+4 = 1+2+3+4 = 10
Input expression : ((((2))))+3*5
((((2))))+3*5 = 2+(3*5) = 17
Input expression : 3r10*3
3r10*3 = 3r10*3 = 9
Input expression : ^Z
J
Note that once you get beyond a few basic arithmetic operations, what we commonly call "mathematical precedence" stops making sense, and primary value for this kind of precedence has been that it allows polynomials to be expressed simply (but expressing polynomials as a sequence of coefficients, one for each exponent, is even simpler).
Nevertheless, this task deals only with simple arithmetic, so this kind of precedence is an arguably appropriate choice for this task.
The implementation here uses a shift/reduce parser to build a tree structure which J happens to support for evaluation:
<lang j>parse=:parse_parser_
eval=:monad define
'gerund structure'=:y
gerund@.structure
)
coclass 'parser'
classify=: '$()*/+-'&(((>:@#@[ # 2:) #: 2 ^ i.)&;:)
rules=:
patterns=: ,"0 assert 1
addrule=: dyad define
rules=: rules,;:x
patterns=: patterns,+./@classify"1 y
)
'Term' addrule '$()', '0', '+-',: '0'
'Factor' addrule '$()+-', '0', '*/',: '0'
'Parens' addrule '(', '*/+-0', ')',: ')*/+-0$'
rules=: rules,;:'Move'
buildTree=: monad define
words=: ;:'$',y
queue=: classify '$',y
stack=: classify '$$$$'
tokens=: ]&.>i.#words
tree=:
while.(#queue)+.6<#stack do.
rule=: rules {~ i.&1 patterns (*./"1)@:(+./"1) .(*."1)4{.stack
rule`:6
end.
'syntax' assert 1 0 1 1 1 1 -: {:"1 stack
gerund=: literal&.> (<,'%') (I. words=<,'/')} words
gerund;1{tree
)
literal=:monad define ::]
".'t=.',y
5!:1<'t'
)
Term=: Factor=: monad define
stack=: ({.stack),(classify '0'),4}.stack
tree=: ({.tree),(<1 2 3{tree),4}.tree
)
Parens=: monad define
stack=: (1{stack),3}.stack
tree=: (1{tree),3}.tree
)
Move=: monad define
'syntax' assert 0<#queue
stack=: ({:queue),stack
queue=: }:queue
tree=: ({:tokens),tree
tokens=: }:tokens
)
parse=:monad define
tmp=: conew 'parser'
r=: buildTree__tmp y
coerase tmp
r
)</lang>
example use:
<lang j> eval parse '1+2*3/(4-5+6)'
2.2</lang>
You can also display the syntax tree, for example:
<lang j> parse '2*3/(4-5)'
┌─────────────────────────────────────────────────────┬───────────────────┐
│┌───┬───────┬───┬───────┬───┬─┬───────┬───┬───────┬─┐│┌───────┬─┬───────┐│
││┌─┐│┌─────┐│┌─┐│┌─────┐│┌─┐│(│┌─────┐│┌─┐│┌─────┐│)│││┌─┬─┬─┐│4│┌─┬─┬─┐││
│││$│││┌─┬─┐│││*│││┌─┬─┐│││%││ ││┌─┬─┐│││-│││┌─┬─┐││ ││││1│2│3││ ││6│7│8│││
││└─┘│││0│2│││└─┘│││0│3│││└─┘│ │││0│4│││└─┘│││0│5│││ │││└─┴─┴─┘│ │└─┴─┴─┘││
││ ││└─┴─┘││ ││└─┴─┘││ │ ││└─┴─┘││ ││└─┴─┘││ ││└───────┴─┴───────┘│
││ │└─────┘│ │└─────┘│ │ │└─────┘│ │└─────┘│ ││ │
│└───┴───────┴───┴───────┴───┴─┴───────┴───┴───────┴─┘│ │
└─────────────────────────────────────────────────────┴───────────────────┘</lang>
At the top level, the first box is a list of terminals, and the second box represents their parsed structure within the source sentence, with numbers indexing the respective terminals.
Java
Uses the BigRational class to handle arbitrary-precision numbers (rational numbers since basic arithmetic will result in rational values).
<lang java>import java.util.Stack;
public class ArithmeticEvaluation
{
public static enum Parentheses { LEFT, RIGHT }
public static enum BinaryOperator
{
ADD('+', 1) {
public BigRational eval(BigRational leftValue, BigRational rightValue) { return leftValue.add(rightValue); }
},
SUB('-', 1) {
public BigRational eval(BigRational leftValue, BigRational rightValue) { return leftValue.subtract(rightValue); }
},
MUL('*', 2) {
public BigRational eval(BigRational leftValue, BigRational rightValue) { return leftValue.multiply(rightValue); }
},
DIV('/', 2) {
public BigRational eval(BigRational leftValue, BigRational rightValue) { return leftValue.divide(rightValue); }
};
public final char symbol;
public final int precedence;
BinaryOperator(char symbol, int precedence)
{
this.symbol = symbol;
this.precedence = precedence;
}
public abstract BigRational eval(BigRational leftValue, BigRational rightValue);
}
public static class BinaryExpression
{
public Object leftOperand = null;
public BinaryOperator operator = null;
public Object rightOperand = null;
public BinaryExpression(Object leftOperand, BinaryOperator operator, Object rightOperand)
{
this.leftOperand = leftOperand;
this.operator = operator;
this.rightOperand = rightOperand;
}
public BigRational eval()
{
BigRational leftValue = (leftOperand instanceof BinaryExpression) ? ((BinaryExpression)leftOperand).eval() : (BigRational)leftOperand;
BigRational rightValue = (rightOperand instanceof BinaryExpression) ? ((BinaryExpression)rightOperand).eval() : (BigRational)rightOperand;
return operator.eval(leftValue, rightValue);
}
public String toString()
{ return "(" + leftOperand + " " + operator.symbol + " " + rightOperand + ")"; }
}
public static void createNewOperand(BinaryOperator operator, Stack<Object> operands)
{
Object rightOperand = operands.pop();
operands.push(new BinaryExpression(operands.pop(), operator, rightOperand));
return;
}
public static Object createExpression(String inputString)
{
int curIndex = 0;
boolean afterOperand = false;
Stack<Object> operands = new Stack<Object>();
Stack<Object> operators = new Stack<Object>();
inputStringLoop:
while (curIndex < inputString.length())
{
int startIndex = curIndex;
char c = inputString.charAt(curIndex++);
if (Character.isWhitespace(c))
continue;
if (afterOperand)
{
if (c == ')')
{
Object operator = null;
while (!operators.isEmpty() && ((operator = operators.pop()) != Parentheses.LEFT))
createNewOperand((BinaryOperator)operator, operands);
continue;
}
afterOperand = false;
for (BinaryOperator operator : BinaryOperator.values())
{
if (c == operator.symbol)
{
while (!operators.isEmpty() && (operators.peek() != Parentheses.LEFT) && (((BinaryOperator)operators.peek()).precedence >= operator.precedence))
createNewOperand((BinaryOperator)operators.pop(), operands);
operators.push(operator);
continue inputStringLoop;
}
}
throw new IllegalArgumentException();
}
if (c == '(')
{
operators.push(Parentheses.LEFT);
continue;
}
afterOperand = true;
while (curIndex < inputString.length())
{
c = inputString.charAt(curIndex);
if (((c < '0') || (c > '9')) && (c != '.'))
break;
curIndex++;
}
operands.push(BigRational.valueOf(inputString.substring(startIndex, curIndex)));
}
while (!operators.isEmpty())
{
Object operator = operators.pop();
if (operator == Parentheses.LEFT)
throw new IllegalArgumentException();
createNewOperand((BinaryOperator)operator, operands);
}
Object expression = operands.pop();
if (!operands.isEmpty())
throw new IllegalArgumentException();
return expression;
}
public static void main(String[] args)
{
String[] testExpressions = { "2+3", "2+3/4", "2*3-4", "2*(3+4)+5/6", "2 * (3 + (4 * 5 + (6 * 7) * 8) - 9) * 10", "2*-3--4+-.25" };
for (String testExpression : testExpressions)
{
Object expression = createExpression(testExpression);
System.out.println("Input: \"" + testExpression + "\", AST: \"" + expression + "\", eval=" + (expression instanceof BinaryExpression ? ((BinaryExpression)expression).eval() : expression));
}
}
}</lang>
Output:
Input: "2+3", AST: "(2 + 3)", eval=5
Input: "2+3/4", AST: "(2 + (3 / 4))", eval=11/4
Input: "2*3-4", AST: "((2 * 3) - 4)", eval=2
Input: "2*(3+4)+5/6", AST: "((2 * (3 + 4)) + (5 / 6))", eval=89/6
Input: "2 * (3 + (4 * 5 + (6 * 7) * 8) - 9) * 10", AST: "((2 * ((3 + ((4 * 5) + ((6 * 7) * 8))) - 9)) * 10)", eval=7000
Input: "2*-3--4+-.25", AST: "(((2 * -3) - -4) + -1/4)", eval=-9/4
Lua
<lang lua>require"lpeg"
P, R, C, S, V = lpeg.P, lpeg.R, lpeg.C, lpeg.S, lpeg.V
--matches arithmetic expressions and returns a syntax tree
expression = P{"expr";
ws = P" "^0,
number = C(R"09"^1) * V"ws",
lp = "(" * V"ws",
rp = ")" * V"ws",
sym = C(S"+-*/") * V"ws",
more = (V"sym" * V"expr")^0,
expr = V"number" * V"more" + V"lp" * lpeg.Ct(V"expr" * V"more") * V"rp" * V"more"}
--evaluates a tree
function eval(expr)
--empty
if type(expr) == "string" or type(expr) == "number" then return expr + 0 end
--arithmetic functions
tb = {["+"] = function(a,b) return eval(a) + eval(b) end,
["-"] = function(a,b) return eval(a) - eval(b) end,
["*"] = function(a,b) return eval(a) * eval(b) end,
["/"] = function(a,b) return eval(a) / eval(b) end}
--you could add ^ or other operators to this pretty easily
for i, v in ipairs{"*/", "+-"} do
for s, u in ipairs(expr) do
local k = type(u) == "string" and C(S(v)):match(u)
if k then
expr[s-1] = tb[k](expr[s-1],expr[s+1])
table.remove(expr, s)
table.remove(expr, s)
end
end
end
return expr[1]
end
print(eval{expression:match(io.read())})</lang>
OCaml
<lang ocaml>type expression =
| Const of float
| Sum of expression * expression (* e1 + e2 *)
| Diff of expression * expression (* e1 - e2 *)
| Prod of expression * expression (* e1 * e2 *)
| Quot of expression * expression (* e1 / e2 *)
let rec eval expr =
match expr with
| Const c -> c
| Sum (f, g) -> eval f +. eval g
| Diff(f, g) -> eval f -. eval g
| Prod(f, g) -> eval f *. eval g
| Quot(f, g) -> eval f /. eval g
open Genlex
let lexer = make_lexer ["("; ")"; "+"; "-"; "*"; "/"]
let rec parse_expr = parser
[< e1 = parse_mult; e = parse_more_adds e1 >] -> e
and parse_more_adds e1 = parser
[< 'Kwd "+"; e2 = parse_mult; e = parse_more_adds (Sum(e1, e2)) >] -> e
| [< 'Kwd "-"; e2 = parse_mult; e = parse_more_adds (Diff(e1, e2)) >] -> e
| [< >] -> e1
and parse_mult = parser
[< e1 = parse_simple; e = parse_more_mults e1 >] -> e
and parse_more_mults e1 = parser
[< 'Kwd "*"; e2 = parse_simple; e = parse_more_mults (Prod(e1, e2)) >] -> e
| [< 'Kwd "/"; e2 = parse_simple; e = parse_more_mults (Quot(e1, e2)) >] -> e
| [< >] -> e1
and parse_simple = parser
| [< 'Int i >] -> Const(float i)
| [< 'Float f >] -> Const f
| [< 'Kwd "("; e = parse_expr; 'Kwd ")" >] -> e
let parse_expression = parser [< e = parse_expr; _ = Stream.empty >] -> e
let read_expression s = parse_expression(lexer(Stream.of_string s))</lang>
Using the function read_expression in an interactive loop:
<lang ocaml>let () =
while true do
print_string "Expression: ";
let str = read_line() in
if str = "q" then exit 0;
let expr = read_expression str in
let res = eval expr in
Printf.printf " = %g\n%!" res;
done</lang>
Compile with:
ocamlopt -pp camlp4o arith_eval.ml -o arith_eval.opt
Oz
We can create a simple, but slow parser using logic programming.
Every procedure reads the input characters from X0 and returns the remaining characters in X. The AST is returned as the regular return value.
The Do procedure automatically threads the input state through a sequence of procedure calls.
<lang oz>declare
fun {Expr X0 ?X}
choice
[L _ R] = {Do [Term &+ Expr] X0 ?X} in add(L R)
[] [L _ R] = {Do [Term &- Expr] X0 ?X} in sub(L R)
[] {Term X0 X}
end
end
fun {Term X0 ?X}
choice
[L _ R] = {Do [Factor &* Term] X0 ?X} in mul(L R)
[] [L _ R] = {Do [Factor &/ Term] X0 ?X} in 'div'(L R)
[] {Factor X0 X}
end
end
fun {Factor X0 ?X}
choice {Parens Expr X0 X}
[] {Number X0 X}
end
end
fun {Number X0 X}
Ds = {Many1 Digit X0 X}
in
num(Ds)
end
fun {Digit X0 ?X}
D|!X = X0
in
D = choice &0 [] &1 [] &2 [] &3 [] &4 [] &5 [] &6 [] &7 [] &8 [] &9 end
end
fun {Many1 Rule X0 ?X}
choice [{Rule X0 X}]
[] X1 in {Rule X0 X1}|{Many1 Rule X1 X}
end
end
fun {Parens Rule X0 ?X}
[_ R _] = {Do [&( Rule &)] X0 X}
in
R
end
fun {Do Rules X0 ?X}
Res#Xn = {FoldL Rules
fun {$ Res#Xi Rule}
if {Char.is Rule} then
!Rule|X2 = Xi
in
(Rule|Res) # X2
elseif {Procedure.is Rule} then
X2 in
({Rule Xi X2}|Res) # X2
end
end
nil#X0}
in
X = Xn
{Reverse Res}
end
%% Returns a singleton list if an AST was found or nil otherwise.
fun {Parse S}
{SearchOne fun {$} {Expr S nil} end}
end
fun {Eval X}
case X of
num(Ds) then {String.toInt Ds}
[] add(L R) then {Eval L} + {Eval R}
[] sub(L R) then {Eval L} - {Eval R}
[] mul(L R) then {Eval L} * {Eval R}
[] 'div'(L R) then {Eval L} div {Eval R}
end
end
[AST] = {Parse "((11+15)*15)*2-(3)*4*1"}
in
{Inspector.configure widgetShowStrings true}
{Inspect AST}
{Inspect {Eval AST}}</lang>
To improve performance, the number of choice points should be limited, for example by reading numbers deterministically instead.
For real parsing with possible large input, it is however recommended to use Gump, Mozart's parser generator.
Pascal
See Arithmetic Evaluator/Pascal.
Perl
<lang perl>sub ev
- Evaluates an arithmetic expression like "(1+3)*7" and returns
- its value.
{my $exp = shift;
# Delete all meaningless characters. (Scientific notation,
# infinity, and not-a-number aren't supported.)
$exp =~ tr {0-9.+-/*()} {}cd;
return ev_ast(astize($exp));}
{my $balanced_paren_regex;
$balanced_paren_regex = qr
{\( ( [^()]+ | (??{$balanced_paren_regex}) )+ \)}x;
# ??{ ... } interpolates lazily (only when necessary),
# permitting recursion to arbitrary depths.
sub astize
# Constructs an abstract syntax tree by recursively
# transforming textual arithmetic expressions into array
# references of the form [operator, left oprand, right oprand].
{my $exp = shift;
# If $exp is just a number, return it as-is.
$exp =~ /[^0-9.]/ or return $exp;
# If parentheses surround the entire expression, get rid of
# them.
$exp = substr($exp, 1, -1)
while $exp =~ /\A($balanced_paren_regex)\z/;
# Replace stuff in parentheses with placeholders.
my @paren_contents;
$exp =~ s {($balanced_paren_regex)}
{push(@paren_contents, $1);
"[p$#paren_contents]"}eg;
# Scan for operators in order of increasing precedence,
# preferring the rightmost.
$exp =~ m{(.+) ([+-]) (.+)}x or
$exp =~ m{(.+) ([*/]) (.+)}x or
# The expression must've been malformed somehow.
# (Note that unary minus isn't supported.)
die "Eh?: [$exp]\n";
my ($op, $lo, $ro) = ($2, $1, $3);
# Restore the parenthetical expressions.
s {\[p(\d+)\]} {($paren_contents[$1])}eg
foreach $lo, $ro;
# And recurse.
return [$op, astize($lo), astize($ro)];}}
{my %ops =
('+' => sub {$_[0] + $_[1]},
'-' => sub {$_[0] - $_[1]},
'*' => sub {$_[0] * $_[1]},
'/' => sub {$_[0] / $_[1]});
sub ev_ast
# Evaluates an abstract syntax tree of the form returned by
# &astize.
{my $ast = shift;
# If $ast is just a number, return it as-is.
ref $ast or return $ast;
# Otherwise, recurse.
my ($op, @operands) = @$ast;
$_ = ev_ast($_) foreach @operands;
return $ops{$op}->(@operands);}}</lang>
Perl 6
<lang perl6>sub ev (Str $s --> Num) {
grammar expr {
token TOP { ^ <sum> $ }
token sum { <product> (('+' || '-') <product>)* }
token product { <factor> (('*' || '/') <factor>)* }
token factor { <unary_minus>? [ <parens> || <literal> ] }
token unary_minus { '-' }
token parens { '(' <sum> ')' }
token literal { \d+ ['.' \d+]? || '.' \d+ }
}
my sub minus ($b) { $b ?? -1 !! +1 }
my sub sum ($x) {
[+] product($x<product>), map
{ minus($^y[0] eq '-') * product $^y<product> },
|($x[0] or [])
}
my sub product ($x) {
[*] factor($x<factor>), map
{ factor($^y<factor>) ** minus($^y[0] eq '/') },
|($x[0] or [])
}
my sub factor ($x) {
minus($x<unary_minus>) * ($x<parens>
?? sum $x<parens><sum>
!! $x<literal>)
}
expr.parse([~] split /\s+/, $s);
$/ or fail 'No parse.';
sum $/<sum>;
}</lang>
Testing:
<lang perl6>say ev '5'; # 5
say ev '1 + 2 - 3 * 4 / 5'; # 0.6
say ev '1 + 5*3.4 - .5 -4 / -2 * (3+4) -6'; # 25.5
say ev '((11+15)*15)* 2 + (3) * -4 *1'; # 768</lang>
PicoLisp
The built-in function 'str' splits a string into a list of lexical tokens
(numbers and transient symbols). From that, a recursive descendent parser can
build an expression tree, resulting in directly executable Lisp code.
<lang PicoLisp>(de ast (Str)
(let *L (str Str "")
(aggregate) ) )
(de aggregate ()
(let X (product)
(while (member (car *L) '("+" "-"))
(setq X (list (intern (pop '*L)) X (product))) )
X ) )
(de product ()
(let X (term)
(while (member (car *L) '("*" "/"))
(setq X (list (intern (pop '*L)) X (term))) )
X ) )
(de term ()
(let X (pop '*L)
(cond
((num? X) X)
((= "+" X) (term))
((= "-" X) (list '- (term)))
((= "(" X) (prog1 (aggregate) (pop '*L)))) ) ) )</lang>
Output:
<lang PicoLisp>: (ast "1+2+3*-4/(1+2)")
-> (+ (+ 1 2) (/ (* 3 (- 4)) (+ 1 2)))
- (ast "(1+2+3)*-4/(1+2)")
-> (/ (* (+ (+ 1 2) 3) (- 4)) (+ 1 2))</lang>
Pop11
<lang pop11>/* Scanner routines */
/* Uncomment the following to parse data from standard input
vars itemrep;
incharitem(charin) -> itemrep;
- /
- Current symbol
vars sym;
define get_sym();
itemrep() -> sym;
enddefine;
define expect(x);
lvars x;
if x /= sym then
printf(x, 'Error, expected %p\n');
mishap(sym, 1, 'Example parser error');
endif;
get_sym();
enddefine;
lconstant res_list = [( ) + * ];
lconstant reserved = newproperty(
maplist(res_list, procedure(x); [^x ^(true)]; endprocedure),
20, false, "perm");
/*
Parser for arithmetic expressions
- /
/*
expr: term
| expr "+" term
| expr "-" term
;
- /
define do_expr() -> result;
lvars result = do_term(), op;
while sym = "+" or sym = "-" do
sym -> op;
get_sym();
[^op ^result ^(do_term())] -> result;
endwhile;
enddefine;
/*
term: factor
| term "*" factor
| term "/" factor
;
- /
define do_term() -> result;
lvars result = do_factor(), op;
while sym = "*" or sym = "/" do
sym -> op;
get_sym();
[^op ^result ^(do_factor())] -> result;
endwhile;
enddefine;
/*
factor: word
| constant
| "(" expr ")"
;
- /
define do_factor() -> result;
if sym = "(" then
get_sym();
do_expr() -> result;
expect(")");
elseif isinteger(sym) or isbiginteger(sym) then
sym -> result;
get_sym();
else
if reserved(sym) then
printf(sym, 'unexpected symbol %p\n');
mishap(sym, 1, 'Example parser syntax error');
endif;
sym -> result;
get_sym();
endif;
enddefine;
/* Expression evaluator, returns false on error (currently only
division by 0 */
define arith_eval(expr);
lvars op, arg1, arg2;
if not(expr) then
return(expr);
endif;
if isinteger(expr) or isbiginteger(expr) then
return(expr);
endif;
expr(1) -> op;
arith_eval(expr(2)) -> arg1;
arith_eval(expr(3)) -> arg2;
if not(arg1) or not(arg2) then
return(false);
endif;
if op = "+" then
return(arg1 + arg2);
elseif op = "-" then
return(arg1 - arg2);
elseif op = "*" then
return(arg1 * arg2);
elseif op = "/" then
if arg2 = 0 then
return(false);
else
return(arg1 div arg2);
endif;
else
printf('Internal error\n');
return(false);
endif;
enddefine;
/* Given list, create item repeater. Input list is stored in a
closure are traversed when new item is requested. */
define listitemrep(lst);
procedure();
lvars item;
if lst = [] then
termin;
else
front(lst) -> item;
back(lst) -> lst;
item;
endif;
endprocedure;
enddefine;
/* Initialise scanner */
listitemrep([(3 + 50) * 7 - 100 / 10]) -> itemrep;
get_sym();
- Test it
arith_eval(do_expr()) =></lang>
Prolog
<lang prolog>% Lexer
numeric(X) :- 48 =< X, X =< 57.
not_numeric(X) :- 48 > X ; X > 57.
lex1([], []).
lex1([40|Xs], ['('|Ys]) :- lex1(Xs, Ys).
lex1([41|Xs], [')'|Ys]) :- lex1(Xs, Ys).
lex1([43|Xs], ['+'|Ys]) :- lex1(Xs, Ys).
lex1([45|Xs], ['-'|Ys]) :- lex1(Xs, Ys).
lex1([42|Xs], ['*'|Ys]) :- lex1(Xs, Ys).
lex1([47|Xs], ['/'|Ys]) :- lex1(Xs, Ys).
lex1([X|Xs], [N|Ys]) :- numeric(X), N is X - 48, lex1(Xs, Ys).
lex2([], []).
lex2([X], [X]).
lex2([Xa,Xb|Xs], [Xa|Ys]) :- atom(Xa), lex2([Xb|Xs], Ys).
lex2([Xa,Xb|Xs], [Xa|Ys]) :- number(Xa), atom(Xb), lex2([Xb|Xs], Ys).
lex2([Xa,Xb|Xs], [Y|Ys]) :- number(Xa), number(Xb), N is Xa * 10 + Xb, lex2([N|Xs], [Y|Ys]).
% Parser
oper(1, *, X, Y, X * Y). oper(1, /, X, Y, X / Y).
oper(2, +, X, Y, X + Y). oper(2, -, X, Y, X - Y).
num(D) --> [D], {number(D)}.
expr(0, Z) --> num(Z).
expr(0, Z) --> {Z = (X)}, ['('], expr(2, X), [')'].
expr(N, Z) --> {succ(N0, N)}, {oper(N, Op, X, Y, Z)}, expr(N0, X), [Op], expr(N, Y).
expr(N, Z) --> {succ(N0, N)}, expr(N0, Z).
parse(Tokens, Expr) :- expr(2, Expr, Tokens, []).
% Evaluator
evaluate(E, E) :- number(E).
evaluate(A + B, E) :- evaluate(A, Ae), evaluate(B, Be), E is Ae + Be.
evaluate(A - B, E) :- evaluate(A, Ae), evaluate(B, Be), E is Ae - Be.
evaluate(A * B, E) :- evaluate(A, Ae), evaluate(B, Be), E is Ae * Be.
evaluate(A / B, E) :- evaluate(A, Ae), evaluate(B, Be), E is Ae / Be.
% Solution
calculator(String, Value) :-
lex1(String, Tokens1),
lex2(Tokens1, Tokens2),
parse(Tokens2, Expression),
evaluate(Expression, Value).
% Example use
% calculator("(3+50)*7-9", X).</lang>
Python
There are python modules, such as Ply, which facilitate the implementation of parsers. This example, however, uses only standard Python with the parser having two stacks, one for operators, one for operands.
A subsequent example uses Pythons' ast module to generate the abstract syntax tree.
<lang python>import operator
class AstNode(object):
def __init__( self, opr, left, right ):
self.opr = opr
self.l = left
self.r = right
def eval(self):
return self.opr(self.l.eval(), self.r.eval())
class LeafNode(object):
def __init__( self, valStrg ):
self.v = int(valStrg)
def eval(self):
return self.v
class Yaccer(object):
def __init__(self):
self.operstak = []
self.nodestak =[]
self.__dict__.update(self.state1)
def v1( self, valStrg ):
# Value String
self.nodestak.append( LeafNode(valStrg))
self.__dict__.update(self.state2)
#print 'push', valStrg
def o2( self, operchar ):
# Operator character or open paren in state1
def openParen(a,b):
return 0 # function should not be called
opDict= { '+': ( operator.add, 2, 2 ),
'-': (operator.sub, 2, 2 ),
'*': (operator.mul, 3, 3 ),
'/': (operator.div, 3, 3 ),
'^': ( pow, 4, 5 ), # right associative exponentiation for grins
'(': ( openParen, 0, 8 )
}
operPrecidence = opDict[operchar][2]
self.redeuce(operPrecidence)
self.operstak.append(opDict[operchar])
self.__dict__.update(self.state1)
# print 'pushop', operchar
def syntaxErr(self, char ):
# Open Parenthesis
print 'parse error - near operator "%s"' %char
def pc2( self,operchar ):
# Close Parenthesis
# reduce node until matching open paren found
self.redeuce( 1 )
if len(self.operstak)>0:
self.operstak.pop() # pop off open parenthesis
else:
print 'Error - no open parenthesis matches close parens.'
self.__dict__.update(self.state2)
def end(self):
self.redeuce(0)
return self.nodestak.pop()
def redeuce(self, precidence):
while len(self.operstak)>0:
tailOper = self.operstak[-1]
if tailOper[1] < precidence: break
tailOper = self.operstak.pop()
vrgt = self.nodestak.pop()
vlft= self.nodestak.pop()
self.nodestak.append( AstNode(tailOper[0], vlft, vrgt))
# print 'reduce'
state1 = { 'v': v1, 'o':syntaxErr, 'po':o2, 'pc':syntaxErr }
state2 = { 'v': syntaxErr, 'o':o2, 'po':syntaxErr, 'pc':pc2 }
def Lex( exprssn, p ):
bgn = None
cp = -1
for c in exprssn:
cp += 1
if c in '+-/*^()': # throw in exponentiation (^)for grins
if bgn is not None:
p.v(p, exprssn[bgn:cp])
bgn = None
if c=='(': p.po(p, c)
elif c==')':p.pc(p, c)
else: p.o(p, c)
elif c in ' \t':
if bgn is not None:
p.v(p, exprssn[bgn:cp])
bgn = None
elif c in '0123456789':
if bgn is None:
bgn = cp
else:
print 'Invalid character in expression'
if bgn is not None:
p.v(p, exprssn[bgn:cp])
bgn = None
if bgn is not None:
p.v(p, exprssn[bgn:cp+1])
bgn = None
return p.end()
expr = raw_input("Expression:")
astTree = Lex( expr, Yaccer())
print expr, '=',astTree.eval()</lang>
ast standard library module
Python comes with its own ast module as part of its standard libraries. The module compiles Python source into an AST tree that can in turn be compiled to bytecode then executed.
<lang python>>>> import ast
>>>
>>> expr="2 * (3 -1) + 2 * 5"
>>> node = ast.parse(expr, mode='eval')
>>> print(ast.dump(node).replace(',', ',\n'))
Expression(body=BinOp(left=BinOp(left=Num(n=2),
op=Mult(),
right=BinOp(left=Num(n=3),
op=Sub(),
right=Num(n=1))),
op=Add(),
right=BinOp(left=Num(n=2),
op=Mult(),
right=Num(n=5))))
>>> code_object = compile(node, filename='<string>', mode='eval')
>>> eval(code_object)
14
>>> # lets modify the AST by changing the 5 to a 6
>>> node.body.right.right.n
5
>>> node.body.right.right.n = 6
>>> code_object = compile(node, filename='<string>', mode='eval')
>>> eval(code_object)
16</lang>
Ruby
Function to convert infix arithmetic expression to binary tree. The resulting tree knows how to print and evaluate itself. Assumes expression is well-formed (matched parens, all operators have 2 operands). Algorithm: http://www.seas.gwu.edu/~csci131/fall96/exp_to_tree.html
<lang ruby>$op_priority = {"+" => 0, "-" => 0, "*" => 1, "/" => 1}
$op_function = {
"+" => lambda {|x, y| x + y},
"-" => lambda {|x, y| x - y},
"*" => lambda {|x, y| x * y},
"/" => lambda {|x, y| x / y}}
class TreeNode
attr_accessor :info, :left, :right
def initialize(info)
@info = info
end
def leaf?
@left.nil? and @right.nil?
end
def to_s(order)
if leaf?
@info
else
left_s, right_s = @left.to_s(order), @right.to_s(order)
strs = case order
when :prefix then [@info, left_s, right_s]
when :infix then [left_s, @info, right_s]
when :postfix then [left_s, right_s, @info]
else []
end
"(" + strs.join(" ") + ")"
end
end
def eval
if !leaf? and operator?(@info)
$op_function[@info].call(@left.eval, @right.eval)
else
@info.to_f
end
end
end
def tokenize(exp)
exp
.gsub('(', ' ( ')
.gsub(')', ' ) ')
.split(' ')
end
def operator?(token)
$op_priority.keys.include?(token)
end
def pop_connect_push(op_stack, node_stack)
temp = op_stack.pop
temp.right = node_stack.pop
temp.left = node_stack.pop
node_stack.push(temp)
end
def infix_exp_to_tree(exp)
tokens = tokenize(exp)
op_stack, node_stack = [], []
tokens.each do |token|
if operator?(token)
# clear stack of higher priority operators
while not (op_stack.empty? or
op_stack.last.info == "(" or
$op_priority[op_stack.last.info] < $op_priority[token])
pop_connect_push(op_stack, node_stack)
end
op_stack.push(TreeNode.new(token))
elsif token == "("
op_stack.push(TreeNode.new(token))
elsif token == ")"
while op_stack.last.info != "("
pop_connect_push(op_stack, node_stack)
end
# throw away the '('
op_stack.pop
else
node_stack.push(TreeNode.new(token))
end
end
while not op_stack.empty?
pop_connect_push(op_stack, node_stack)
end
node_stack.last
end</lang>
Testing:
<lang ruby>exp = "1 + 2 - 3 * (4 / 6)"
puts("Original: " + exp)
tree = infix_exp_to_tree(exp)
puts("Prefix: " + tree.to_s(:prefix))
puts("Infix: " + tree.to_s(:infix))
puts("Postfix: " + tree.to_s(:postfix))
puts("Result: " + tree.eval.to_s)</lang>
Output:
Original: 1 + 2 - 3 * (4 / 6)
Prefix: (- (+ 1 2) (* 3 (/ 4 6)))
Infix: ((1 + 2) - (3 * (4 / 6)))
Postfix: ((1 2 +) (3 (4 6 /) *) -)
Result: 1.0
Scala
This code shows a bit of Scala's parser classes. The error handling of parser errors
is practically non-existent, to avoid obscuring the code.
<lang scala>
package org.rosetta.arithmetic_evaluator.scala
object ArithmeticParser extends scala.util.parsing.combinator.RegexParsers {
def readExpression(input: String) : Option[()=>Int] = {
parseAll(expr, input) match {
case Success(result, _) =>
Some(result)
case other =>
println(other)
None
}
}
private def expr : Parser[()=>Int] = {
(term<~"+")~expr ^^ { case l~r => () => l() + r() } |
(term<~"-")~expr ^^ { case l~r => () => l() - r() } |
term
}
private def term : Parser[()=>Int] = {
(factor<~"*")~term ^^ { case l~r => () => l() * r() } |
(factor<~"/")~term ^^ { case l~r => () => l() / r() } |
factor
}
private def factor : Parser[()=>Int] = {
"("~>expr<~")" |
"\\d+".r ^^ { x => () => x.toInt } |
failure("Expected a value")
}
}
object Main {
def main(args: Array[String]) {
println("""Please input the expressions. Type "q" to quit.""")
var input: String = ""
do {
input = readLine("> ")
if (input != "q") {
ArithmeticParser.readExpression(input).foreach(f => println(f()))
}
} while (input != "q")
}
}
</lang>
Example:
C:\Workset>scala org.rosetta.arithmetic_evaluator.scala.ArithmeticEvaluator
Please input the expressions. Type "q" to quit.
> 2+3*2
8
> (1+3)*7
28
> 1+a
[1.3] failure: Expected a number
1+a
^
> 2 + 2
4
> q
This example was made rather more complex by the requirement of generating an AST tree. With a Scala distribution there are many examples of arithmetic parsers, as small as half a dozen lines.
Tcl
The code below delivers the AST for an expression in a form that it can be immediately eval-led, using Tcl's prefix operators.
<lang Tcl>namespace import tcl::mathop::*
proc ast str {
# produce abstract syntax tree for an expression
regsub -all {[-+*/()]} $str { & } str ;# "tokenizer"
s $str
}
proc s {args} {
# parse "(a + b) * c + d" to "+ [* [+ a b] c] d"
if {[llength $args] == 1} {set args [lindex $args 0]}
if [regexp {[()]} $args] {
eval s [string map {( "\[s " ) \]} $args]
} elseif {"*" in $args} {
s [s_group $args *]
} elseif {"/" in $args} {
s [s_group $args /]
} elseif {"+" in $args} {
s [s_group $args +]
} elseif {"-" in $args} {
s [s_group $args -]
} else {
string map {\{ \[ \} \]} [join $args]
}
}
proc s_group {list op} {
# turn ".. a op b .." to ".. {op a b} .."
set pos [lsearch -exact $list $op]
set p_1 [- $pos 1]
set p1 [+ $pos 1]
lreplace $list $p_1 $p1 \
[list $op [lindex $list $p_1] [lindex $list $p1]]
}
- -- Test suite
foreach test [split {
ast 2-2
ast 1-2-3
ast (1-2)-3
ast 1-(2-3)
ast (1+2)*3
ast (1+2)/3-4*5
ast ((1+2)/3-4)*5
} \n] {
puts "$test ..... [eval $test] ..... [eval [eval $test]]"
}</lang>
Output: ast 2-2 ..... - 2 2 ..... 0
ast 1-2-3 ..... - [- 1 2] 3 ..... -4
ast (1-2)-3 ..... - [- 1 2] 3 ..... -4
ast 1-(2-3) ..... - 1 [- 2 3] ..... 2
ast (1+2)*3 ..... * [+ 1 2] 3 ..... 9
ast (1+2)/3-4*5 ..... - [/ [+ 1 2] 3] [* 4 5] ..... -19
ast ((1+2)/3-4)*5 ..... * [- [/ [+ 1 2] 3] 4] 5 ..... -15
Ursala
with no error checking other than removal of spaces
<lang Ursala>#import std
- import nat
- import flo
lex = ~=' '*~F+ rlc both -=digits # separate into tokens
parse = # build a tree
--<';'>; @iNX ~&l->rh ^/~< cases~&lhh\~&lhPNVrC {
'*/': ^|C/~&hNV associate '*/',
'+-': ^|C/~&hNV associate '*/+-',
');': @r ~&htitBPC+ associate '*/+-'}
associate "ops" = ~&tihdh2B-="ops"-> ~&thd2tth2hNCCVttt2C
traverse = *^ ~&v?\%ep ^H\~&vhthPX '+-*/'-$<plus,minus,times,div>@dh
evaluate = traverse+ parse+ lex</lang>
test program:
<lang Ursala>#cast %eL
test = evaluate*t
-[
1+1
4/5
2-1
3*7
3+4+5
9-2-4
7/3/2
4+2*3
5*2-1
5-3*2
(1+1)*(2+3)
(2-4)/(3+5*(8-1))]-</lang>
output:
<
2.000000e+00,
8.000000e-01,
1.000000e+00,
2.100000e+01,
1.200000e+01,
3.000000e+00,
1.166667e+00,
1.000000e+01,
9.000000e+00,
-1.000000e+00,
1.000000e+01,
-5.263158e-02>