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
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>
BBC BASIC
<lang bbcbasic> Expr$ = "1 + 2 * (3 + (4 * 5 + 6 * 7 * 8) - 9) / 10"
PRINT "Input = " Expr$ AST$ = FNast(Expr$) PRINT "AST = " AST$ PRINT "Value = " ;EVAL(AST$) END DEF FNast(RETURN in$) LOCAL ast$, oper$ REPEAT ast$ += FNast1(in$) WHILE ASC(in$)=32 in$ = MID$(in$,2) : ENDWHILE oper$ = LEFT$(in$,1) IF oper$="+" OR oper$="-" THEN ast$ += oper$ in$ = MID$(in$,2) ELSE EXIT REPEAT ENDIF UNTIL FALSE = "(" + ast$ + ")" DEF FNast1(RETURN in$) LOCAL ast$, oper$ REPEAT ast$ += FNast2(in$) WHILE ASC(in$)=32 in$ = MID$(in$,2) : ENDWHILE oper$ = LEFT$(in$,1) IF oper$="*" OR oper$="/" THEN ast$ += oper$ in$ = MID$(in$,2) ELSE EXIT REPEAT ENDIF UNTIL FALSE = "(" + ast$ + ")" DEF FNast2(RETURN in$) LOCAL ast$ WHILE ASC(in$)=32 in$ = MID$(in$,2) : ENDWHILE IF ASC(in$)<>40 THEN = FNnumber(in$) in$ = MID$(in$,2) ast$ = FNast(in$) in$ = MID$(in$,2) = ast$ DEF FNnumber(RETURN in$) LOCAL ch$, num$ REPEAT ch$ = LEFT$(in$,1) IF INSTR("0123456789.", ch$) THEN num$ += ch$ in$ = MID$(in$,2) ELSE EXIT REPEAT ENDIF UNTIL FALSE = num$</lang>
Output:
Input = 1 + 2 * (3 + (4 * 5 + 6 * 7 * 8) - 9) / 10 AST = ((1)+(2*((3)+(((4*5)+(6*7*8)))-(9))/10)) Value = 71
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>
Clojure
<lang Clojure>(def precedence '{* 0, / 0 + 1, - 1})
(defn order-ops
"((A x B) y C) or (A x (B y C)) depending on precedence of x and y" A x B y C & more (let [ret (if (<= (precedence x)
(precedence y)) (list (list A x B) y C) (list A x (list B y C)))]
(if more (recur (concat ret more)) ret)))
(defn add-parens
"Tree walk to add parens. All lists are length 3 afterwards." [s] (clojure.walk/postwalk #(if (seq? %) (let [c (count %)]
(cond (even? c) (throw (Exception. "Must be an odd number of forms")) (= c 1) (first %) (= c 3) % (>= c 5) (order-ops %)))
%) s))
(defn make-ast
"Parse a string into a list of numbers, ops, and lists" [s] (-> (format "'(%s)" s) (.replaceAll , "([*+-/])" " $1 ") load-string add-parens))
(def ops {'* * '+ + '- - '/ /})
(def eval-ast
(partial clojure.walk/postwalk
#(if (seq? %) (let [[a o b] %] ((ops o) a b)) %)))
(defn evaluate [s]
"Parse and evaluate an infix arithmetic expression" (eval-ast (make-ast s)))
user> (evaluate "1 + 2*(3 - 2*(3 - 2)*((2 - 4)*5 - 22/(7 + 2*(3 - 1)) - 1)) + 1") 60</lang>
Common Lisp
The following code processes the data in a pipeline of steps which are combined in the evaluate
function.
First, the string is converted into a sequence of tokens, represented as a list. Operator tokens are represented directly by the corresponding Lisp symbols, and the integer terms are represented by Lisp integer objects. The symbols :lparen
and :rparen
represent the the parentheses. So for instance the input
"1*(3+2)"
tokenizes as (1 * :lparen 3 + 2 :rparen)
.
Next, that sequence of tokens is then transformed by eliminating the parentheses. Subsequences of the form :lparen ... :rparen
with a sublist containing the tokens between the :lparen
and :rparen
. The sequence now has an intermediate tree structure, in which parenthesized fragments like 1 + 2 * 3 + 4 / 9
still remain flat.
At this point, another processing stage parses the operator precedence, and fully parenthesizes fragments, turning (1 + 2 / 3 + 5)
into (1 + (2 / 3) + 5)
. The result is a Lisp-ified infix representation.
Finally, this infix representation can be easily converted to prefix, forming the final AST which is a Lisp expression.
(Lisp expressions are abstract syntax trees!) This representation evaluates directly with eval
.
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))) (token (case c (nil nil) (#\( :lparen) (#\) :rparen) (#\* '*) (#\/ '/) (#\+ '+) (#\- '-) (otherwise (unless (digit-char-p c) (cerror "Skip it." "Unexpected character ~w." c) (read-char stream) (return-from tokenize-stream (tokenize-stream stream))) (read-integer))))) (unless (or (null token) (integerp token)) (read-char stream)) token)))
(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 (integerp expression) expression (destructuring-bind (a &optional op1 b op2 c &rest others) expression (unless (member op1 '(+ - * / nil)) (error "syntax error: in expr ~a expecting operator, not ~a" expression op1)) (unless (member op2 '(+ - * / nil)) (error "syntax error: in expr ~a expecting operator, not ~a" expression op2)) (cond ((not op1) (gop a)) ((not op2) `(,(gop a) ,op1 ,(gop b))) (t (let ((a (gop a)) (b (gop b)) (c (gop c))) (if (and (member op1 '(+ -)) (member op2 '(* /))) (gop `(,a ,op1 (,b ,op2 ,c) ,@others)) (gop `((,a ,op1 ,b) ,op2 ,c ,@others))))))))))
(defun infix-to-prefix (expression)
(if (integerp expression) expression (destructuring-bind (a op b) expression `(,op ,(infix-to-prefix a) ,(infix-to-prefix b)))))
(defun evaluate (string)
(with-input-from-string (in string) (eval (infix-to-prefix (group-operations (group-parentheses (loop for token = (tokenize-stream in) until (null 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
After the AST tree is constructed, a visitor pattern is used to display the AST structure and calculate the expression value. <lang d>import std.stdio, std.string, std.ascii, std.conv, std.array,
std.exception, std.traits;
struct Stack(T) {
T[] data; alias data this; void push(T top) pure nothrow @safe { data ~= top; }
T pop(bool discard = true)() pure @nogc @safe { immutable static exc = new immutable(Exception)("Stack Empty"); if (data.empty) throw exc; auto top = data[$ - 1]; static if (discard) data.popBack; return top; }
}
enum Type { Num, OBkt, CBkt, Add, Sub, Mul, Div } immutable opChar = ["#", "(", ")", "+", "-", "*", "/"]; immutable opPrec = [ 0, -9, -9, 1, 1, 2, 2];
abstract class Visitor { void visit(XP e) pure @safe; }
final class XP {
immutable Type type; immutable string str; immutable int pos; // Optional, to dispaly AST struct. XP LHS, RHS;
this(string s=")", int p = -1) pure nothrow @safe { str = s; pos = p; auto localType = Type.Num; foreach_reverse (immutable t; [EnumMembers!Type[1 .. $]]) if (opChar[t] == s) localType = t; this.type = localType; }
override int opCmp(Object other) pure @safe { auto rhs = cast(XP)other; enforce(rhs !is null); return opPrec[type] - opPrec[rhs.type]; }
void accept(Visitor v) pure @safe { v.visit(this); }
}
final class AST {
XP root; Stack!XP opr, num; string xpr, token; int xpHead, xpTail;
void joinXP(XP x) pure @safe { x.RHS = num.pop; x.LHS = num.pop; num.push(x); }
string nextToken() pure @safe { 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 (token[0].isDigit) { while (xpTail < xpr.length && xpr[xpTail].isDigit()) 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(in string s) /*@safe*/ { bool expectingOP; xpr = s; try { xpHead = xpTail = 0; num = opr = null; root = null; opr.push(new XP); // CBkt, prevent evaluate null OP precedence. 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 != 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, " ".replicate(xpHead)); root = null; return this; }
if (num.length != 1) { // Should be one XP left. "Parse Error...".writefln; root = null; } else { root = num.pop; } return this; } // End Parse.
} // End class AST.
// To display AST fancy struct. void ins(ref char[][] s, in string v, in int p, in int l) pure nothrow @safe {
if (l + 1 > s.length) s.length++; while (s[l].length < p + v.length + 1) s[l] ~= " "; s[l][p .. p + v.length] = v[];
}
final class CalcVis : Visitor {
int result, level; string resultStr; char[][] Tree;
static void opCall(AST a) @safe { if (a && a.root) { auto c = new CalcVis; a.root.accept(c); foreach (immutable i; 1 .. c.Tree.length) { // More fancy. bool flipflop = false; enum char mk = '.'; foreach (immutable j; 0 .. c.Tree[i].length) { while (j >= c.Tree[i - 1].length) c.Tree[i - 1] ~= " "; immutable c1 = c.Tree[i][j]; immutable 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 (const t; c.Tree) t.writefln; writefln("\n%s ==>\n%s = %s", a.xpr, c.resultStr, c.result); } else "Evalute invalid or null Expression.".writefln; }
// Calc. the value, display AST struct and eval order. override void visit(XP xp) @safe { ins(Tree, xp.str, xp.pos, level); level++; if (xp.type == Type.Num) { resultStr ~= xp.str; result = xp.str.to!int; } else { resultStr ~= "("; xp.LHS.accept(this); immutable int lhs = result; resultStr ~= opChar[xp.type]; xp.RHS.accept(this); resultStr ~= ")"; switch (xp.type) { case Type.Add: result = lhs + result; break; case Type.Sub: result = lhs - result; break; case Type.Mul: result = lhs * result; break; case Type.Div: result = lhs / result; break; default: throw new Exception("Invalid type"); } } level--; }
}
void main(string[] args) /*@safe*/ {
immutable exp0 = "1 + 2*(3 - 2*(3 - 2)*((2 - 4)*5" ~ " - 22/(7 + 2*(3 - 1)) - 1)) + 1"; immutable exp = (args.length > 1) ? args[1 .. $].join(' ') : exp0; new AST().parse(exp).CalcVis; // Should be 60.
}</lang>
- Output:
........................................................+. .+.. 1 1 *... 2 .-.......... 3 .......*................................ *... ....................-. 2 .-. ..-... 1 3 2 ...* /... .-. 5 22 .+.. 2 4 7 *... 2 .-. 3 1 1 + 2*(3 - 2*(3 - 2)*((2 - 4)*5 - 22/(7 + 2*(3 - 1)) - 1)) + 1 ==> ((1+(2*(3-((2*(3-2))*((((2-4)*5)-(22/(7+(2*(3-1)))))-1)))))+1) = 60
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>
Elena
<lang elena>#define system.
- define extensions.
// --- Token ---
- class Token
{
#field theValue. #constructor new [ theValue := String new. ] #constructor new : aValue [ theValue := String new:aValue. ] #method ParseOrder = 0. #method append : aChar [ theValue += aChar. ] #method add : aNode [ ^ aNode += self. ]
#method Number = convertor toReal:(theValue value).
}
// --- Node ---
- class Node
{
#field theLeft. #field theRight. #field theState. #method setRight : aNode [ theRight := aNode. theState := %appendRight. ] #method setLeft : aNode [ theLeft := aNode. theState := %setRight. ] #constructor new [ theState := %setLeft. ]
#method add : aNode = (self ParseOrder > aNode ParseOrder) ? [ self += aNode. ^ self. ] ! [ aNode += self. ^ aNode. ]. #method appendRight : aNode [ (theRight ParseOrder > aNode ParseOrder) ? [ theRight += aNode. ] ! [ theRight := aNode += theRight. ]. ] #method append : anObject = $self~theState eval:anObject. #method => theState.
}
// --- SummaryNode
- class SummaryNode : Node
{
#method ParseOrder = 2. #method Number = theLeft Number + theRight Number.
}
// --- DifferenceNode ---
- class DifferenceNode : Node
{
#method ParseOrder = 2. #method Number = theLeft Number - theRight Number.
}
// --- ProductNode ---
- class ProductNode : Node
{
#method ParseOrder = 1. #method Number = theLeft Number * theRight Number.
}
// --- FractionNode ---
- class FractionNode : Node
{
#method ParseOrder = 1. #method Number = theLeft Number / theRight Number.
}
// --- SubExpression ---
- class SubExpression
{
#field theParser. #field theCounter. #constructor new [ theParser := arithmeval'Parser new. theCounter := Integer new:1. ]
#method ParseOrder = 0. #method add : aNode [ ^ aNode += self. ] #method validate [ (theCounter < 0) ? [ #throw Exception new:"Invalid expression". ]. ^ (0 == theCounter). ] #method append : aChar [ aChar => 41 ? [ theCounter -= 1. ] 40 ? [ theCounter += 1 ] ! [ theParser evaluate:aChar ]. ]
#method Number = $self validate ? [ theParser Number ] ! [ #throw Exception new:"Invalid expression". ].
}
// ---- Parser ----
- class Parser : system'routines'BasePattern
{
#field theToken. #field theTopNode. #field theState. #method onBrackets : aChar [ theToken += aChar. (theToken validate) ? [ theState := %onDigit. ]. ]
#method onStart : aChar [ aChar => 40 ? [ // ( theToken := SubExpression new. theTopNode := theToken. theState := %onBrackets. ] 45 ? [ // - theToken := DifferenceNode new add:(Token new:"0"). theTopNode := theToken. theState := %onOperator. ] ! [ theToken := Token new. theTopNode := theToken. theState := %onDigit. $self appendDigit:aChar. ]. ]
#method onOperator : aChar [ aChar => 40 ? [ theToken := SubExpression new. theTopNode += theToken. theState := %onBrackets. ] ! [ theToken := Token new. theTopNode += theToken. theState := %onDigit.
$self appendDigit:aChar. ]. ]
#constructor new [ theState := %onStart. ]
#method Number = theTopNode Number.
#method appendDigit : aChar [ (aChar >= 48) and:(aChar < 58) ? [ theToken += aChar. ] ! [ #throw Exception new:"Invalid expression". ] ]
#method onDigit : aChar [ aChar => 40 ? [ // ( theToken := SubExpression new. theTopNode := theToken. theState := %onBrackets. ] 42 ? [ // * theTopNode := theTopNode + ProductNode new.
theState := %onOperator. ] 43 ? [ // + theTopNode := theTopNode + SummaryNode new.
theState := %onOperator. ] 45 ? [ // - theTopNode := theTopNode + DifferenceNode new.
theState := %onOperator. ] 47 ? // / [ theTopNode := theTopNode + FractionNode new.
theState := %onOperator. ] ! [ $self appendDigit:aChar. ]. ]
#method eval : aChar = $self~theState eval:aChar.
}
- symbol program =
[
#var aText := String new.
control while:(consoleEx readLine:aText length > 0) &do: [ #var aParser := Parser new.
consoleEx writeLine:"=" :(aParser foreach:aText Number) | if &e: [ consoleEx writeLine:"Invalid Expression". ]. ].
].</lang>
ELENA VM script
<lang elena>number ::= $numeric; numeric ::= "(" sub_expr; numeric ::= number; factor ::= number factor_r; factor ::= "(" sub_expr; sum ::= "+" factor ; difference ::= "-" factor ; multiply ::= "*" numeric; divide ::= "/" numeric; factor_r ::= multiply factor_r; factor_r ::= divide factor_r; factor_r ::= $eps; expr_r ::= sum expr_r; expr_r ::= difference expr_r; expr_r ::= $eps; neg_r ::= factor_r expr_r; sub_expr ::= expression sub_expr_r; sub_expr_r ::= ")" factor_r; neg_expression ::= $numeric neg_r; expression ::= factor expr_r; expression ::= "-" neg_expression; print ::= "?" expression; start ::= print; print => &nil 'program'output $body ^write; multiply => $body ^multiply; divide => $body ^divide; sum => $body ^add; difference => $body ^subtract; neg_expression => 0 $terminal ^subtract $body; number => $terminal $body;</lang>
ERRE
<lang ERRE> PROGRAM EVAL
! ! arithmetic expression evaluator !
!$KEY
LABEL 98,100,110
DIM STACK$[50]
PROCEDURE DISEGNA_STACK
!$RCODE="LOCATE 3,1" !$RCODE="COLOR 0,7" PRINT(TAB(35);"S T A C K";TAB(79);) !$RCODE="COLOR 7,0" FOR TT=1 TO 38 DO IF TT>=20 THEN !$RCODE="LOCATE 3+TT-19,40" ELSE !$RCODE="LOCATE 3+TT,1" END IF IF TT=NS THEN PRINT(">";) ELSE PRINT(" ";) END IF PRINT(RIGHT$(STR$(TT),2);"³ ";STACK$[TT];" ") END FOR REPEAT GET(Z$) UNTIL LEN(Z$)<>0
END PROCEDURE
PROCEDURE COMPATTA_STACK
IF NS>1 THEN R=1 WHILE R<NS DO IF INSTR(OP_LIST$,STACK$[R])=0 AND INSTR(OP_LIST$,STACK$[R+1])=0 THEN FOR R1=R TO NS-1 DO STACK$[R1]=STACK$[R1+1] END FOR NS=NS-1 END IF R=R+1 END WHILE END IF DISEGNA_STACK
END PROCEDURE
PROCEDURE CALC_ARITM
L=NS1 WHILE L<=NS2 DO IF STACK$[L]="^" THEN IF L>=NS2 THEN GOTO 100 END IF N1#=VAL(STACK$[L-1]) N2#=VAL(STACK$[L+1]) NOP=NOP-1 IF STACK$[L]="^" THEN RI#=N1#^N2# END IF STACK$[L-1]=STR$(RI#) N=L WHILE N<=NS2-2 DO STACK$[N]=STACK$[N+2] N=N+1 END WHILE NS2=NS2-2 L=NS1-1 END IF L=L+1 END WHILE
L=NS1 WHILE L<=NS2 DO IF STACK$[L]="*" OR STACK$[L]="/" THEN IF L>=NS2 THEN GOTO 100 END IF N1#=VAL(STACK$[L-1]) N2#=VAL(STACK$[L+1]) NOP=NOP-1 IF STACK$[L]="*" THEN RI#=N1#*N2# ELSE RI#=N1#/N2# END IF STACK$[L-1]=STR$(RI#) N=L WHILE N<=NS2-2 DO STACK$[N]=STACK$[N+2] N=N+1 END WHILE NS2=NS2-2 L=NS1-1 END IF L=L+1 END WHILE
L=NS1 WHILE L<=NS2 DO IF STACK$[L]="+" OR STACK$[L]="-" THEN EXIT IF L>=NS2 N1#=VAL(STACK$[L-1]) N2#=VAL(STACK$[L+1]) NOP=NOP-1 IF STACK$[L]="+" THEN RI#=N1#+N2# ELSE RI#=N1#-N2# END IF STACK$[L-1]=STR$(RI#) N=L WHILE N<=NS2-2 DO STACK$[N]=STACK$[N+2] N=N+1 END WHILE NS2=NS2-2 L=NS1-1 END IF L=L+1 END WHILE
100:
IF NOP<2 THEN ! operator priority DB#=VAL(STACK$[NS1]) ELSE IF NOP<3 THEN DB#=VAL(STACK$[NS1+2]) ELSE DB#=VAL(STACK$[NS1+4]) END IF END IF
END PROCEDURE
PROCEDURE SVOLGI_PAR
NPA=NPA-1 FOR J=NS TO 1 STEP -1 DO EXIT IF STACK$[J]="(" END FOR IF J=0 THEN NS1=1 NS2=NS CALC_ARITM NERR=7 ELSE FOR R=J TO NS-1 DO STACK$[R]=STACK$[R+1] END FOR NS1=J NS2=NS-1 CALC_ARITM IF NS1=2 THEN NS1=1 STACK$[1]=STACK$[2] END IF NS=NS1 COMPATTA_STACK END IF
END PROCEDURE
BEGIN
OP_LIST$="+-*/^(" NOP=0 NPA=0 NS=1 K$="" STACK$[1]="@" ! init stack
PRINT(CHR$(12);) INPUT(LINE,EXPRESSION$)
FOR W=1 TO LEN(EXPRESSION$) DO LOOP CODE=ASC(MID$(EXPRESSION$,W,1)) IF (CODE>=48 AND CODE<=57) OR CODE=46 THEN K$=K$+CHR$(CODE) W=W+1 IF W>LEN(EXPRESSION$) THEN GOTO 98 END IF ELSE EXIT IF K$="" IF NS>1 OR (NS=1 AND STACK$[1]<>"@") THEN NS=NS+1 END IF IF FLAG=0 THEN STACK$[NS]=K$ ELSE STACK$[NS]=STR$(VAL(K$)*FLAG) END IF K$="" FLAG=0 EXIT END IF END LOOP IF CODE=43 THEN K$="+" END IF IF CODE=45 THEN K$="-" END IF IF CODE=42 THEN K$="*" END IF IF CODE=47 THEN K$="/" END IF IF CODE=94 THEN K$="^" END IF
CASE CODE OF 43,45,42,47,94-> IF MID$(EXPRESSION$,W+1,1)="-" THEN FLAG=-1 W=W+1 END IF IF INSTR(OP_LIST$,STACK$[NS])<>0 THEN NERR=5 ELSE NS=NS+1 STACK$[NS]=K$ NOP=NOP+1 IF NOP>=2 THEN FOR J=NS TO 1 STEP -1 DO IF STACK$[J]<>"(" THEN CONTINUE FOR END IF IF J<NS-2 THEN EXIT ELSE GOTO 110 END IF END FOR NS1=J+1 NS2=NS CALC_ARITM NS=NS2 STACK$[NS]=K$ REGISTRO_X#=VAL(STACK$[NS-1]) END IF END IF
110:
END ->
40-> IF NS>1 OR (NS=1 AND STACK$[1]<>"@") THEN NS=NS+1 END IF STACK$[NS]="(" NPA=NPA+1 IF MID$(EXPRESSION$,W+1,1)="-" THEN FLAG=-1 W=W+1 END IF END ->
41-> SVOLGI_PAR IF NERR=7 THEN NERR=0 NOP=0 NPA=0 NS=1 ELSE IF NERR=0 OR NERR=1 THEN DB#=VAL(STACK$[NS]) REGISTRO_X#=DB# ELSE NOP=0 NPA=0 NS=1 END IF END IF END ->
OTHERWISE NERR=8 END CASE K$="" DISEGNA_STACK
END FOR
98:
IF K$<>"" THEN IF NS>1 OR (NS=1 AND STACK$[1]<>"@") THEN NS=NS+1 END IF IF FLAG=0 THEN STACK$[NS]=K$ ELSE STACK$[NS]=STR$(VAL(K$)*FLAG) END IF END IF DISEGNA_STACK IF INSTR(OP_LIST$,STACK$[NS])<>0 THEN NERR=6 ELSE WHILE NPA<>0 DO SVOLGI_PAR END WHILE IF NERR<>7 THEN NS1=1 NS2=NS CALC_ARITM END IF END IF NS=1 NOP=0 NPA=0 !$RCODE="LOCATE 23,1" IF NERR>0 THEN PRINT("Internal Error #";NERR) ELSE PRINT("Value is ";DB#) END IF
END PROGRAM </lang> This solution is based on a stack: as a plus there is a power (^) operator. Unary operator "-" is accepted. Program shows the stack after every operation and you must press a key to go on (this feature can be avoided by removing the final REPEAT..UNTIL loop at the end of "DISEGNA_STACK" procedure).
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:
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>
F#
Using FsLex and FsYacc from the F# PowerPack, we implement this with multiple source files:
AbstractSyntaxTree.fs
:
<lang fsharp>module AbstractSyntaxTree
type Expression =
| Int of int | Plus of Expression * Expression | Minus of Expression * Expression | Times of Expression * Expression | Divide of Expression * Expression</lang>
Lexer.fsl
:
<lang fsharp>{
module Lexer
open Parser // we need the terminal tokens from the Parser
let lexeme = Lexing.LexBuffer<_>.LexemeString }
let intNum = '-'? ['0'-'9']+ let whitespace = ' ' | '\t' let newline = '\n' | '\r' '\n'
rule token = parse
| intNum { INT (lexeme lexbuf |> int) } | '+' { PLUS } | '-' { MINUS } | '*' { TIMES } | '/' { DIVIDE } | '(' { LPAREN } | ')' { RPAREN } | whitespace { token lexbuf } | newline { lexbuf.EndPos <- lexbuf.EndPos.NextLine; token lexbuf } | eof { EOF } | _ { failwithf "unrecognized input: '%s'" <| lexeme lexbuf }</lang>
Parser.fsy
:
<lang fsharp>%{
open AbstractSyntaxTree
%}
%start Expr
// terminal tokens %token <int> INT %token PLUS MINUS TIMES DIVIDE LPAREN RPAREN %token EOF
// associativity and precedences %left PLUS MINUS %left TIMES DIVIDE
// return type of Expr %type <Expression> Expr
%%
Expr: INT { Int $1 }
| Expr PLUS Expr { Plus ($1, $3) } | Expr MINUS Expr { Minus ($1, $3) } | Expr TIMES Expr { Times ($1, $3) } | Expr DIVIDE Expr { Divide ($1, $3) } | LPAREN Expr RPAREN { $2 } </lang>
Program.fs
:
<lang fsharp>open AbstractSyntaxTree
open Lexer
open Parser
let parse txt =
txt |> Lexing.LexBuffer<_>.FromString |> Parser.Expr Lexer.token
let rec eval = function
| Int i -> i | Plus (a,b) -> eval a + eval b | Minus (a,b) -> eval a - eval b | Times (a,b) -> eval a * eval b | Divide (a,b) -> eval a / eval b
do
"((11+15)*15)*2-(3)*4*1" |> parse |> eval |> printfn "%d"</lang>
Go
Groovy
Solution: <lang groovy>enum Op {
ADD('+', 2), SUBTRACT('-', 2), MULTIPLY('*', 1), DIVIDE('/', 1); static { ADD.operation = { a, b -> a + b } SUBTRACT.operation = { a, b -> a - b } MULTIPLY.operation = { a, b -> a * b } DIVIDE.operation = { a, b -> a / b } } final String symbol final int precedence Closure operation
private Op(String symbol, int precedence) { this.symbol = symbol this.precedence = precedence }
String toString() { symbol }
static Op fromSymbol(String symbol) { Op.values().find { it.symbol == symbol } }
}
interface Expression {
Number evaluate();
}
class Constant implements Expression {
Number value
Constant (Number value) { this.value = value }
Constant (String str) { try { this.value = str as BigInteger } catch (e) { this.value = str as BigDecimal } }
Number evaluate() { value }
String toString() { "${value}" }
}
class Term implements Expression {
Op op Expression left, right
Number evaluate() { op.operation(left.evaluate(), right.evaluate()) }
String toString() { "(${op} ${left} ${right})" }
}
void fail(String msg, Closure cond = {true}) {
if (cond()) throw new IllegalArgumentException("Cannot parse expression: ${msg}")
}
Expression parse(String expr) {
def tokens = tokenize(expr) def elements = groupByParens(tokens, 0) parse(elements)
}
List tokenize(String expr) {
def tokens = [] def constStr = "" def captureConstant = { i -> if (constStr) { try { tokens << new Constant(constStr) } catch (NumberFormatException e) { fail "Invalid constant '${constStr}' near position ${i}" } constStr = } } for(def i = 0; i<expr.size(); i++) { def c = expr[i] def constSign = c in ['+','-'] && constStr.empty && (tokens.empty || tokens[-1] != ')') def isConstChar = { it in ['.'] + ('0'..'9') || constSign } if (c in ([')'] + Op.values()*.symbol) && !constSign) { captureConstant(i) } switch (c) { case ~/\s/: break case isConstChar: constStr += c; break case Op.values()*.symbol: tokens << Op.fromSymbol(c); break case ['(',')']: tokens << c; break default: fail "Invalid character '${c}' at position ${i+1}" } } captureConstant(expr.size()) tokens
}
List groupByParens(List tokens, int depth) {
def deepness = depth def tokenGroups = [] for (def i = 0; i < tokens.size(); i++) { def token = tokens[i] switch (token) { case '(': fail("'(' too close to end of expression") { i+2 > tokens.size() } def subGroup = groupByParens(tokens[i+1..-1], depth+1) tokenGroups << subGroup[0..-2] i += subGroup[-1] + 1 break case ')': fail("Unbalanced parens, found extra ')'") { deepness == 0 } tokenGroups << i return tokenGroups default: tokenGroups << token } } fail("Unbalanced parens, unclosed groupings at end of expression") { deepness != 0 } def n = tokenGroups.size() fail("The operand/operator sequence is wrong") { n%2 == 0 } (0..<n).each { def i = it fail("The operand/operator sequence is wrong") { (i%2 == 0) == (tokenGroups[i] instanceof Op) } } tokenGroups
}
Expression parse(List elements) {
while (elements.size() > 1) { def n = elements.size() fail ("The operand/operator sequence is wrong") { n%2 == 0 } def groupLoc = (0..<n).find { i -> elements[i] instanceof List } if (groupLoc != null) { elements[groupLoc] = parse(elements[groupLoc]) continue } def opLoc = (0..<n).find { i -> elements[i] instanceof Op && elements[i].precedence == 1 } \ ?: (0..<n).find { i -> elements[i] instanceof Op && elements[i].precedence == 2 } if (opLoc != null) { fail ("Operator out of sequence") { opLoc%2 == 0 } def term = new Term(left:elements[opLoc-1], op:elements[opLoc], right:elements[opLoc+1]) elements[(opLoc-1)..(opLoc+1)] = [term] continue } } return elements[0] instanceof List ? parse(elements[0]) : elements[0]
}</lang>
Test: <lang groovy>def testParse = {
def ex = parse(it) print """
Input: ${it} AST: ${ex} value: ${ex.evaluate()} """ }
testParse('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')
assert (parse('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')
.evaluate() - Math.E).abs() < 0.0000000000001
testParse('1 + 2*(3 - 2*(3 - 2)*((2 - 4)*5 - 22/(7 + 2*(3 - 1)) - 1)) + 1') testParse('1 - 5 * 2 / 20 + 1') testParse('(1 - 5) * 2 / (20 + 1)') testParse('2 * (3 + ((5) / (7 - 11)))') testParse('(2 + 3) / (10 - 5)') testParse('(1 + 2) * 10 / 100') testParse('(1 + 2 / 2) * (5 + 5)') testParse('2*-3--4+-.25') testParse('2*(-3)-(-4)+(-.25)') testParse('((11+15)*15)*2-(3)*4*1') testParse('((11+15)*15)* 2 + (3) * -4 *1') testParse('(((((1)))))') testParse('-35') println()
try { testParse('((11+15)*1') } catch (e) { println e } try { testParse('((11+15)*1)))') } catch (e) { println e } try { testParse('((11+15)*x)') } catch (e) { println e } try { testParse('+++++') } catch (e) { println e } try { testParse('1 /') } catch (e) { println e } try { testParse('1++') } catch (e) { println e } try { testParse('*1') } catch (e) { println e } try { testParse('/ 1 /') } catch (e) { println e }</lang>
Output:
Input: 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 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)) value: 2.7182818284589946 Input: 1 + 2*(3 - 2*(3 - 2)*((2 - 4)*5 - 22/(7 + 2*(3 - 1)) - 1)) + 1 AST: (+ (+ 1 (* 2 (- 3 (* (* 2 (- 3 2)) (- (- (* (- 2 4) 5) (/ 22 (+ 7 (* 2 (- 3 1))))) 1))))) 1) value: 60 Input: 1 - 5 * 2 / 20 + 1 AST: (+ (- 1 (/ (* 5 2) 20)) 1) value: 1.5 Input: (1 - 5) * 2 / (20 + 1) AST: (/ (* (- 1 5) 2) (+ 20 1)) value: -0.3809523810 Input: 2 * (3 + ((5) / (7 - 11))) AST: (* 2 (+ 3 (/ 5 (- 7 11)))) value: 3.50 Input: (2 + 3) / (10 - 5) AST: (/ (+ 2 3) (- 10 5)) value: 1 Input: (1 + 2) * 10 / 100 AST: (/ (* (+ 1 2) 10) 100) value: 0.3 Input: (1 + 2 / 2) * (5 + 5) AST: (* (+ 1 (/ 2 2)) (+ 5 5)) value: 20 Input: 2*-3--4+-.25 AST: (+ (- (* 2 -3) -4) -0.25) value: -2.25 Input: 2*(-3)-(-4)+(-.25) AST: (+ (- (* 2 -3) -4) -0.25) value: -2.25 Input: ((11+15)*15)*2-(3)*4*1 AST: (- (* (* (+ 11 15) 15) 2) (* (* 3 4) 1)) value: 768 Input: ((11+15)*15)* 2 + (3) * -4 *1 AST: (+ (* (* (+ 11 15) 15) 2) (* (* 3 -4) 1)) value: 768 Input: (((((1))))) AST: 1 value: 1 Input: -35 AST: -35 value: -35 java.lang.IllegalArgumentException: Cannot parse expression: Unbalanced parens, unclosed groupings at end of expression java.lang.IllegalArgumentException: Cannot parse expression: Unbalanced parens, found extra ')' java.lang.IllegalArgumentException: Cannot parse expression: Invalid character 'x' at position 10 java.lang.IllegalArgumentException: Cannot parse expression: Invalid constant '+' near position 1 java.lang.IllegalArgumentException: Cannot parse expression: The operand/operator sequence is wrong java.lang.IllegalArgumentException: Cannot parse expression: Invalid constant '+' near position 3 java.lang.IllegalArgumentException: Cannot parse expression: The operand/operator sequence is wrong java.lang.IllegalArgumentException: Cannot parse expression: The operand/operator sequence is wrong
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
JavaScript
Numbers must have a digit before the decimal point, so 0.1 not .1.
Spaces are removed, expressions like 5--1
are treated as 5 - -1
<lang javascript>function evalArithmeticExp(s) {
s = s.replace(/\s/g,).replace(/^\+/,); var rePara = /\([^\(\)]*\)/; var exp = s.match(rePara);
while (exp = s.match(rePara)) { s = s.replace(exp[0], evalExp(exp[0])); } return evalExp(s); function evalExp(s) { s = s.replace(/[\(\)]/g,); var reMD = /\d+\.?\d*\s*[\*\/]\s*[+-]?\d+\.?\d*/; var reM = /\*/; var reAS = /-?\d+\.?\d*\s*[\+-]\s*[+-]?\d+\.?\d*/; var reA = /\d\+/; var exp;
while (exp = s.match(reMD)) { s = exp[0].match(reM)? s.replace(exp[0], multiply(exp[0])) : s.replace(exp[0], divide(exp[0])); } while (exp = s.match(reAS)) { s = exp[0].match(reA)? s.replace(exp[0], add(exp[0])) : s.replace(exp[0], subtract(exp[0])); } return + s;
function multiply(s, b) { b = s.split('*'); return b[0] * b[1]; } function divide(s, b) { b = s.split('/'); return b[0] / b[1]; } function add(s, b) { s = s.replace(/^\+/,).replace(/\++/,'+'); b = s.split('+'); return Number(b[0]) + Number(b[1]); } function subtract(s, b) { s = s.replace(/\+-|-\+/g,'-');
if (s.match(/--/)) { return add(s.replace(/--/,'+')); } b = s.split('-'); return b.length == 3? -1 * b[1] - b[2] : b[0] - b[1]; } }
}</lang>
Sample output:
evalArithmeticExp('2+3') // 5 evalArithmeticExp('2+3/4') // 2.75 evalArithmeticExp('2*3-4') // 2 evalArithmeticExp('2*(3+4)+5/6') // 14.833333333333334 evalArithmeticExp('2 * (3 + (4 * 5 + (6 * 7) * 8) - 9) * 10') // 7000 evalArithmeticExp('2*-3--4+-0.25' // -2.25
Julia
Julia's homoiconic nature and strong metaprogramming facilities make AST/Expression parsing and creation as accessible and programmatic as other language features <lang julia>julia> expr="2 * (3 -1) + 2 * 5" "2 * (3 -1) + 2 * 5"
julia> parsed = parse(expr) #Julia provides low-level access to language parser for AST/Expr creation
- (+(*(2,-(3,1)),*(2,5)))
julia> t = typeof(parsed) Expr
julia> names(t) #shows type fields (:head,:args,:typ)
julia> parsed.args #Inspect our 'Expr' type innards 3-element Any Array:
:+ :(*(2,-(3,1))) :(*(2,5))
julia> typeof(parsed.args[2]) #'Expr' types can nest Expr
julia> parsed.args[2].args 3-element Any Array:
:* 2 :(-(3,1))
julia> parsed.args[2].args[3].args #Will nest until lowest level of AST 3-element Any Array:
:- 3 1
julia> eval(parsed) 14
julia> eval(parse("1 - 5 * 2 / 20 + 1")) 1.5
julia> eval(parse("2 * (3 + ((5) / (7 - 11)))")) 3.5</lang>
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>
Liberty BASIC
<lang lb> '[RC] Arithmetic evaluation.bas 'Buld the tree (with linked nodes, in array 'cause LB has no pointers) 'applying shunting yard algorythm. 'Then evaluate tree
global stack$ 'operator/brakets stack stack$=""
maxStack = 100 dim stack(maxStack) 'nodes stack global SP 'stack pointer SP = 0
'------------------- global maxNode,curFree global FirstOp,SecondOp,isNumber,NodeCont global opList$ opList$ = "+-*/^"
maxNode=100 FirstOp=1 'pointers to other nodes; 0 means no pointer SecondOp=2 isNumber=3 'like, 1 is number, 0 is operator NodeCont=4 'number if isNumber; or mid$("+-*/^", i, 1) for 1..5 operator
dim node(NodeCont, maxNode) 'will be used from 1, 0 plays null pointer (no link)
curFree=1 'first free node '-------------------
in$ = " 1 + 2 ^ 3 * 4 - 12 / 6 " print "Input: " print in$
'read tokens token$ = "#" while 1
i=i+1 token$ = word$(in$, i) if token$ = "" then i=i-1: exit while
select case case token$ = "(" 'If the token is a left parenthesis, then push it onto the stack. call stack.push token$
case token$ = ")" 'If the token is a right parenthesis: 'Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue. 'Pop the left parenthesis from the stack, but not onto the output queue. 'If the stack runs out without finding a left parenthesis, then there are mismatched parentheses. while stack.peek$() <> "(" 'if stack is empty if stack$="" then print "Error: no matching '(' for token ";i: end 'add operator node to tree child2=node.pop() child1=node.pop() call node.push addOpNode(child1,child2,stack.pop$()) wend discard$=stack.pop$() 'discard "("
case isOperator(token$) 'If the token is an operator, o1, then: 'while there is an operator token, o2, at the top of the stack, and 'either o1 is left-associative and its precedence is equal to that of o2, 'or o1 has precedence less than that of o2, ' pop o2 off the stack, onto the output queue; 'push o1 onto the stack op1$=token$ while(isOperator(stack.peek$())) op2$=stack.peek$() if (op2$<>"^" and precedence(op1$) = precedence(op2$)) _ OR (precedence(op1$) < precedence(op2$)) then '"^" is the only right-associative operator 'add operator node to tree child2=node.pop() child1=node.pop() call node.push addOpNode(child1,child2,stack.pop$()) else exit while end if wend call stack.push op1$
case else 'number 'actually, wrohg operator could end up here, like say % 'If the token is a number, then 'add leaf node to tree (number) call node.push addNumNode(val(token$)) end select
wend
'When there are no more tokens to read: 'While there are still operator tokens in the stack: ' If the operator token on the top of the stack is a parenthesis, then there are mismatched parentheses. ' Pop the operator onto the output queue. while stack$<>""
if stack.peek$() = "(" then print "no matching ')'": end 'add operator node to tree child2=node.pop() child1=node.pop() call node.push addOpNode(child1,child2,stack.pop$())
wend
root = node.pop() 'call dumpNodes print "Tree:" call drawTree root, 1, 0, 3 locate 1, 10 print "Result: ";evaluate(root)
end
'------------------------------------------ function isOperator(op$)
isOperator = instr(opList$, op$)<>0 AND len(op$)=1
end function
function precedence(op$)
if isOperator(op$) then precedence = 1 _ + (instr("+-*/^", op$)<>0) _ + (instr("*/^", op$)<>0) _ + (instr("^", op$)<>0) end if
end function
'------------------------------------------ sub stack.push s$
stack$=s$+"|"+stack$
end sub
function stack.pop$()
'it does return empty on empty stack or queue stack.pop$=word$(stack$,1,"|") stack$=mid$(stack$,instr(stack$,"|")+1)
end function
function stack.peek$()
'it does return empty on empty stack or queue stack.peek$=word$(stack$,1,"|")
end function
'--------------------------------------- sub node.push s
stack(SP)=s SP=SP+1
end sub
function node.pop()
'it does return -999999 on empty stack if SP<1 then pop=-999999: exit function SP=SP-1 node.pop=stack(SP)
end function
'======================================= sub dumpNodes
for i = 1 to curFree-1 print i, for j = 1 to 4 print node(j, i), next print next print
end sub
function evaluate(node)
if node=0 then exit function if node(isNumber, node) then evaluate = node(NodeCont, node) exit function end if 'else operator op1 = evaluate(node(FirstOp, node)) op2 = evaluate(node(SecondOp, node)) select case node(NodeCont, node) 'opList$, "+-*/^" case 1 evaluate = op1+op2 case 2 evaluate = op1-op2 case 3 evaluate = op1*op2 case 4 evaluate = op1/op2 case 5 evaluate = op1^op2 end select
end function
sub drawTree node, level, leftRight, offsetY
if node=0 then exit sub call drawTree node(FirstOp, node), level+1, leftRight-1/2^level, offsetY
'print node 'count on 80 char maiwin x = 40*(1+leftRight) y = level+offsetY locate x, y 'print x, y,">"; if node(isNumber, node) then print node(NodeCont, node) else print mid$(opList$, node(NodeCont, node),1) end if
call drawTree node(SecondOp, node), level+1, leftRight+1/2^level, offsetY
end sub
function addNumNode(num) 'returns new node
newNode=curFree curFree=curFree+1 node(isNumber,newNode)=1 node(NodeCont,newNode)=num
addNumNode = newNode
end function
function addOpNode(firstChild, secondChild, op$) 'returns new node 'FirstOrSecond ignored if parent is 0
newNode=curFree curFree=curFree+1 node(isNumber,newNode)=0 node(NodeCont,newNode)=instr(opList$, op$)
node(FirstOp,newNode)=firstChild node(SecondOp,newNode)=secondChild
addOpNode = newNode
end function </lang>
- Output:
Input: 1 + 2 ^ 3 * 4 - 12 / 6 Tree: - + / 1 * 12 6 ^ 4 2 3 Result: 31
Mathematica
<lang Mathematica>(*parsing:*) parse[string_] :=
Module[{e}, StringCases[string, "+" | "-" | "*" | "/" | "(" | ")" | DigitCharacter ..] //. {a_String?DigitQ :> e[ToExpression@a], {x___, PatternSequence["(", a_e, ")"], y___} :> {x, a, y}, {x : PatternSequence[] | PatternSequence[___, "(" | "+" | "-" | "*" | "/"], PatternSequence[op : "+" | "-", a_e], y___} :> {x, e[op, a], y}, {x : PatternSequence[] | PatternSequence[___, "(" | "+" | "-"], PatternSequence[a_e, op : "*" | "/", b_e], y___} :> {x, e[op, a, b], y}, {x : PatternSequence[] | PatternSequence[___, "(" | "+" | "-"], PatternSequence[a_e, b_e], y___} :> {x, e["*", a, b], y}, {x : PatternSequence[] | PatternSequence[___, "("], PatternSequence[a_e, op : "+" | "-", b_e], y : PatternSequence[] | PatternSequence[")" | "+" | "-", ___]} :> {x, e[op, a, b], y}} //. {e -> List, {a_Integer} :> a, {a_List} :> a}]
(*evaluation*) evaluate[a_Integer] := a; evaluate[{"+", a_}] := evaluate[a]; evaluate[{"-", a_}] := -evaluate[a]; evaluate[{"+", a_, b_}] := evaluate[a] + evaluate[b]; evaluate[{"-", a_, b_}] := evaluate[a] - evaluate[b]; evaluate[{"*", a_, b_}] := evaluate[a]*evaluate[b]; evaluate[{"/", a_, b_}] := evaluate[a]/evaluate[b]; evaluate[string_String] := evaluate[parse[string]]</lang>
Example use: <lang Mathematica>parse["-1+2(3+4*-5/6)"] evaluate["-1+2(3+4*-5/6)"]</lang>
Output:
{"+", {"-", 1}, {"*", 2, {"-", 3, {"/", {"*", 4, {"-", 5}}, 6}}}} 35/3
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 = function
| 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
ooRexx
<lang ooRexx> expressions = .array~of("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") loop input over expressions
expression = createExpression(input) if expression \= .nil then say 'Expression "'input'" parses to "'expression~string'" and evaluates to "'expression~evaluate'"'
end
-- create an executable expression from the input, printing out any
-- errors if they are raised.
- routine createExpression
use arg inputString
-- signal on syntax
return .ExpressionParser~parseExpression(inputString)
syntax:
condition = condition('o') say condition~errorText say condition~message return .nil
-- a base class for tree nodes in the tree
-- all nodes return some sort of value. This can be constant,
-- or the result of additional evaluations
- class evaluatornode
-- all evaluation is done here
- method evaluate abstract
-- node for numeric values in the tree
- class constant
- method init
expose value use arg value
- method evaluate
expose value return value
- method string
expose value return value
-- node for a parenthetical group on the tree
- class parens
- method init
expose subexpression use arg subexpression
- method evaluate
expose subexpression return subexpression~evaluate
- method string
expose subexpression return "("subexpression~string")"
-- base class for binary operators
- class binaryoperator
- method init
expose left right -- the left and right sides are set after the left and right sides have -- been resolved. left = .nil right = .nil
-- base operation
- method evaluate
expose left right return self~operation(left~evaluate, right~evaluate)
-- the actual operation of the node
- method operation abstract
- method symbol abstract
- method precedence abstract
-- display an operator as a string value
- method string
expose left right return '('left~string self~symbol right~string')'
- attribute left
- attribute right
- class addoperator subclass binaryoperator
- method operation
use arg left, right return left + right
- method symbol
return "+"
- method precedence
return 1
- class subtractoperator subclass binaryoperator
- method operation
use arg left, right return left - right
- method symbol
return "-"
- method precedence
return 1
- class multiplyoperator subclass binaryoperator
- method operation
use arg left, right return left * right
- method symbol
return "*"
- method precedence
return 2
- class divideoperator subclass binaryoperator
- method operation
use arg left, right return left / right
- method symbol
return "/"
- method precedence
return 2
-- a class to parse the expression and build an evaluation tree
- class expressionParser
-- create a resolved operand from an operator instance and the top -- two entries on the operand stack.
- method createNewOperand class
use strict arg operator, operands -- the operands are a stack, so they are in inverse order current operator~right = operands~pull operator~left = operands~pull -- this goes on the top of the stack now operands~push(operator)
- method parseExpression class
use strict arg inputString -- stacks for managing the operands and pending operators operands = .queue~new operators = .queue~new -- this flags what sort of item we expect to find at the current -- location afterOperand = .false
loop currentIndex = 1 to inputString~length char = inputString~subChar(currentIndex) -- skip over whitespace if char == ' ' then iterate currentIndex -- If the last thing we parsed was an operand, then -- we expect to see either a closing paren or an -- operator to appear here if afterOperand then do if char == ')' then do loop while \operators~isempty operator = operators~pull -- if we find the opening paren, replace the -- top operand with a paren group wrapper -- and stop popping items if operator == '(' then do operands~push(.parens~new(operands~pull)) leave end -- collapse the operator stack a bit self~createNewOperand(operator, operands) end -- done with this character iterate currentIndex end afterOperand = .false operator = .nil if char == "+" then operator = .addoperator~new else if char == "-" then operator = .subtractoperator~new else if char == "*" then operator = .multiplyoperator~new else if char == "/" then operator = .divideoperator~new if operator \= .nil then do loop while \operators~isEmpty top = operators~peek -- start of a paren group stops the popping if top == '(' then leave -- or the top operator has a lower precedence if top~precedence < operator~precedence then leave -- process this pending one self~createNewOperand(operators~pull, operands) end -- this new operator is now top of the stack operators~push(operator) -- and back to the top iterate currentIndex end raise syntax 98.900 array("Invalid expression character" char) end -- if we've hit an open paren, add this to the operator stack -- as a phony operator if char == '(' then do operators~push('(') iterate currentIndex end -- not an operator, so we have an operand of some type afterOperand = .true startindex = currentIndex -- allow a leading minus sign on this if inputString~subchar(currentIndex) == '-' then currentIndex += 1 -- now scan for the end of numbers loop while currentIndex <= inputString~length -- exit for any non-numeric value if \inputString~matchChar(currentIndex, "0123456789.") then leave currentIndex += 1 end -- extract the string value operand = inputString~substr(startIndex, currentIndex - startIndex) if \operand~datatype('Number') then raise syntax 98.900 array("Invalid numeric operand '"operand"'") -- back this up to the last valid character currentIndex -= 1 -- add this to the operand stack as a tree element that returns a constant operands~push(.constant~new(operand)) end
loop while \operators~isEmpty operator = operators~pull if operator == '(' then raise syntax 98.900 array("Missing closing ')' in expression") self~createNewOperand(operator, operands) end -- our entire expression should be the top of the expression tree expression = operands~pull if \operands~isEmpty then raise syntax 98.900 array("Invalid expression") return expression
</lang> Output:
Expression "2+3" parses to "(2 + 3)" and evaluates to "5" Expression "2+3/4" parses to "(2 + (3 / 4))" and evaluates to "2.75" Expression "2*3-4" parses to "((2 * 3) - 4)" and evaluates to "2" Expression "2*(3+4)+5/6" parses to "((2 * ((3 + 4))) + (5 / 6))" and evaluates to "14.8333333" Expression "2 * (3 + (4 * 5 + (6 * 7) * 8) - 9) * 10" parses to "((2 * (((3 + (((4 * 5) + (((6 * 7)) * 8)))) - 9))) * 10)" and evaluates to 7000" Expression "2*-3--4+-.25" parses to "(((2 * -3) - -4) + -.25)" and evaluates to "-2.25"
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>
Racket
<lang racket>
- lang racket
(require parser-tools/yacc parser-tools/lex
(prefix-in ~ parser-tools/lex-sre))
(define-tokens value-tokens (NUM)) (define-empty-tokens op-tokens (OPEN CLOSE + - * / EOF NEG))
(define lex
(lexer [(eof) 'EOF] [whitespace (lex input-port)] [(~or "+" "-" "*" "/") (string->symbol lexeme)] ["(" 'OPEN] [")" 'CLOSE] [(~: (~+ numeric) (~? #\. (~* numeric))) (token-NUM (string->number lexeme))]))
(define parse
(parser [start E] [end EOF] [tokens value-tokens op-tokens] [error void] [precs (left - +) (left * /) (left NEG)] [grammar (E [(NUM) $1] [(E + E) (+ $1 $3)] [(E - E) (- $1 $3)] [(E * E) (* $1 $3)] [(E / E) (/ $1 $3)] [(- E) (prec NEG) (- $2)] [(OPEN E CLOSE) $2])]))
(define (calc str)
(define i (open-input-string str)) (displayln (parse (λ() (lex i)))))
(calc "(1 + 2 * 3) - (1+2)*-3") </lang>
REXX
Several additional operators are supported as well as several forms of exponentiated numbers:
- ^ exponentiation, as well as **
- // remainder division
- % integer division
- ÷ in addition to /
- & for logical AND
- | for logical OR
- && for logical XOR
- || for concatenation
- [ ] { } as grouping symbols, as well as ( )
- 12.3e+44 ("single" precision)
- 12.3E+44 ("single" precision)
- 12.3D+44 ("double" precision)
- 12.3Q+44 ("extended" or "quad" precision)
<lang rexx>/*REXX pgm evaluates an infix-type arithmetic expression & shows result.*/ nchars = '0123456789.eEdDqQ' /*possible parts of a #, sans ± */ e='***error!***'; $=' '; doubleOps='&|*/'; z= parse arg x 1 ox1; if x= then call serr 'no input was specified.' x=space(x); L=length(x); x=translate(x,'()()',"[]{}")
j=0; do forever; j=j+1; if j>L then leave; _=substr(x,j,1); _2=getX()
newT=pos(_,' ()[]{}^÷')\==0; if newT then do; z=z _ $; iterate; end possDouble=pos(_,doubleOps)\==0 /*is _ a possible double operator*/ if possDouble then do /*is this a possible double oper?*/ if _2==_ then do /*yup, it's one of 'em.*/ _=_||_ /*use a double operator*/ x=overlay($,x,Nj) /*blank out the*/ end /* 2nd symbol.*/ z=z _ $; iterate end if _=='+' | _=="-" then do; p_=word(z,words(z)) /*last Z token*/ if p_=='(' then z=z 0 /*handle unary ±*/ z=z _ $; iterate end lets=0; sigs=0; #=_
do j=j+1 to L; _=substr(x,j,1) /*build a valid number.*/ if lets==1 & sigs==0 then if _=='+' | _=='-' then do; sigs=1 #=# || _ iterate end if pos(_,nchars)==0 then leave lets=lets+datatype(_,'M') /*keep track of # of exponents. */ #=# || translate(_,'EEEEE','eDdQq') /*keep buildingthe num.*/ end /*j*/ j=j-1 if \datatype(#,'N') then call serr 'invalid number: ' # z=z # $ end /*forever*/
_=word(z,1); if _=='+' | _=='-' then z=0 z /*handle unary cases.*/ x='(' space(z) ') '; tokens=words(x) /*force stacking for expression. */
do i=1 for tokens; @.i=word(x,i); end /*i*/ /*assign input tokens*/
L=max(20,length(x)) /*use 20 for the min show width. */ op=')(-+/*^'; rOp=substr(op,3); p.=; s.=; n=length(op); epr=; stack=
do i=1 for n; _=substr(op,i,1); s._=(i+1)%2; p._=s._+(i==n); end /*i*/ /*[↑] assign operator priorities.*/ do #=1 for tokens; ?=@.# /*process each token from @. list*/ if ?=='**' then ?="^" /*convert REXX-type exponentation*/ select /*@.# is: (, operator, ), operand*/ when ?=='(' then stack='(' stack when isOp(?) then do /*is token an operator?*/ !=word(stack,1) /*get token from stack.*/ do while !\==')' & s.!>=p.?; epr=epr ! /*add*/ stack=subword(stack,2); /*del token from stack.*/ !=word(stack,1) /*get token from stack.*/ end /*while ···)*/ stack=? stack /*add token to stack.*/ end when ?==')' then do; !=word(stack,1) /*get token from stack.*/ do while !\=='('; epr=epr ! /*add to epr.*/ stack=subword(stack,2) /*del token from stack.*/ !=word(stack,1) /*get token from stack.*/ end /*while ···( */ stack=subword(stack,2) /*del token from stack.*/ end otherwise epr=epr ? /*add operand to epr. */ end /*select*/ end /*#*/
epr=space(epr stack); tokens=words(epr); x=epr; z=; stack=
do i=1 for tokens; @.i=word(epr,i); end /*i*/ /*assign input tokens*/
dop='/ // % ÷'; bop='& | &&' /*division ops; binary operands*/ aop='- + * ^ **' dop bop; lop=aop '||' /*arithmetic ops; legal operands*/
do #=1 for tokens; ?=@.#; ??=? /*process each token from @. list*/ w=words(stack); b=word(stack,max(1,w)) /*stack count; last entry.*/ a=word(stack,max(1,w-1)) /*stack's "first" operand.*/ division =wordpos(?,dop)\==0 /*flag: doing a division.*/ arith =wordpos(?,aop)\==0 /*flag: doing arithmetic.*/ bitOp =wordpos(?,bop)\==0 /*flag: doing binary math*/ if datatype(?,'N') then do; stack=stack ?; iterate; end if wordpos(?,lop)==0 then do; z=e 'illegal operator:' ?; leave; end if w<2 then do; z=e 'illegal epr expression.'; leave; end if ?=='^' then ??="**" /*REXXify ^ ──► ** (make legal)*/ if ?=='÷' then ??="/" /*REXXify ÷ ──► / (make legal)*/ if division & b=0 then do; z=e 'division by zero: ' b; leave; end if bitOp & \isBit(a) then do; z=e "token isn't logical: " a; leave; end if bitOp & \isBit(b) then do; z=e "token isn't logical: " b; leave; end select /*perform arith. operation*/ when ??=='+' then y = a + b when ??=='-' then y = a - b when ??=='*' then y = a * b when ??=='/' | ??=="÷" then y = a / b when ??=='//' then y = a // b when ??=='%' then y = a % b when ??=='^' | ??=="**" then y = a ** b when ??=='||' then y = a || b otherwise z=e 'invalid operator:' ?; leave end /*select*/ if datatype(y,'W') then y=y/1 /*normalize number with ÷ by 1.*/ _=subword(stack,1,w-2); stack=_ y /*rebuild the stack with answer. */ end /*#*/
if word(z,1)==e then stack= /*handle special case of errors. */ z=space(z stack) /*append any residual entries. */ say 'answer──►' z /*display the answer (result). */ parse source upper . how . /*invoked via C.L. or REXX pgm?*/ if how=='COMMAND' | ,
\datatype(z,'W') then exit /*stick a fork in it, we're done.*/
return z /*return Z ──► invoker (RESULT).*/ /*──────────────────────────────────subroutines─────────────────────────*/ isBit: return arg(1)==0 | arg(1)==1 /*returns 1 if arg1 is bin bit.*/ isOp: return pos(arg(1),rOp)\==0 /*is argument1 a "real" operator?*/ serr: say; say e arg(1); say; exit 13 /*issue an error message with txt*/ /*──────────────────────────────────GETX subroutine─────────────────────*/ getX: do Nj=j+1 to length(x); _n=substr(x,Nj,1); if _n==$ then iterate
if _n==$ then iterate; return substr(x,Nj,1) /*ignore blanks*/ end /*Nj*/
return $ /*reached end-of-tokens, return $*/</lang> output when using the input of: + 1+2.0-003e-00*[4/6]
answer──► 1
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}
class TreeNode
OP_FUNCTION = { "+" => lambda {|x, y| x + y}, "-" => lambda {|x, y| x - y}, "*" => lambda {|x, y| x * y}, "/" => lambda {|x, y| x / y}} 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(')', ' ) ') .gsub('+', ' + ') .gsub('-', ' - ') .gsub('*', ' * ') .gsub('/', ' / ') .split(' ')
end
def operator?(token)
$op_priority.has_key?(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 until (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 until 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.
Sidef
Translation of JavaScript.
<lang ruby>func evalArithmeticExp(s) {
func evalExp(s) {
func operate(s, op) { s.split(op).map{|c|c.toNum}.reduce(op); }
func add(s) { operate(s.replace(/^\+/,).replace(/\++/,'+'), '+'); }
func subtract(s) { s.gReplace!(/(\+-|-\+)/,'-');
if (s.match(/--/)) { return(add(s.replace(/--/,'+'))); }
var b = s.split('-') -> len == 3 ? (-1 * b[1].toNum - b[2].toNum) : (operate(s, '-')); }
s.gReplace!(/[()]/,).gReplace!(/-\+/, '-');
var reM = /\*/; var reMD = %r"(\d+\.?\d*\s*[*/]\s*[+-]?\d+\.?\d*)";
var reA = /\d\+/; var reAS = /(-?\d+\.?\d*\s*[+-]\s*[+-]?\d+\.?\d*)/;
var match; while (match = s.match(reMD)) { var cap = match.captures.first -> =~ reM ?? ? (s.replace!(reMD, operate(cap, '*').to_s)) : (s.replace!(reMD, operate(cap, '/').to_s)); }
while (match = s.match(reAS)) { var cap = match.captures.first -> =~ reA ?? ? (s.replace!(reAS, add(cap).to_s)) : (s.replace!(reAS, subtract(cap).to_s)); }
return(s); }
var rePara = /(\([^\(\)]*\))/; s = (s.split.join().replace(/^\+/,));
while (var match = s.match(rePara)) { s.replace!(rePara, evalExp(match.captures.first)); }
return(evalExp(s).toNum);
}</lang>
Testing the function: <lang ruby>for [
['2+3' => 5], ['-4-3' => -7], ['-+2+3/4' => -1.25], ['2*3-4' => 2], ['2*(3+4)+2/4' => 2/4 + 14], ['2*-3--4+-0.25' => -2.25], ['2 * (3 + (4 * 5 + (6 * 7) * 8) - 9) * 10' => 7000], ] { |expr, res|
var num = (evalArithmeticExp(expr)) == res || ( "Error occurred on expression '#{expr}': got '#{num}' instead of '#{res}'\n".die; );
"%-45s == %10g\n".printf(expr, num);
}</lang>
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
TXR
Use TXR text pattern matching to parse expression to a Lisp AST, then evaluate with eval
:
<lang txr>@(next :args) @(define space)@/ */@(end) @(define mulop (nod))@\
@(local op)@\ @(space)@\ @(cases)@\ @{op /[*]/}@(bind nod @(intern op *user-package*))@\ @(or)@\ @{op /\//}@(bind (nod) @(list 'trunc))@\ @(end)@\ @(space)@\
@(end) @(define addop (nod))@\
@(local op)@(space)@{op /[+\-]/}@(space)@\ @(bind nod @(intern op *user-package*))@\
@(end) @(define number (nod))@\
@(local n)@(space)@{n /[0-9]+/}@(space)@\ @(bind nod @(int-str n 10))@\
@(end) @(define factor (nod))@(cases)(@(expr nod))@(or)@(number nod)@(end)@(end) @(define term (nod))@\
@(local op nod1 nod2)@\ @(cases)@\ @(factor nod1)@\ @(cases)@(mulop op)@(term nod2)@(bind nod (op nod1 nod2))@\ @(or)@(bind nod nod1)@\ @(end)@\ @(or)@\ @(addop op)@(factor nod1)@\ @(bind nod (op nod1))@\ @(end)@\
@(end) @(define expr (nod))@\
@(local op nod1 nod2)@\ @(term nod1)@\ @(cases)@(addop op)@(expr nod2)@(bind nod (op nod1 nod2))@\ @(or)@(bind nod nod1)@\ @(end)@\
@(end) @(cases) @ {source (expr e)} @ (output) source: @source AST: @(format nil "~s" e) value: @(eval e nil) @ (end) @(or) @ (maybe)@(expr e)@(end)@bad @ (output) erroneous suffix "@bad" @ (end) @(end)</lang>
Run:
$ txr expr-ast.txr '3 + 3/4 * (2 + 2) + (4*4)' source: 3 + 3/4 * (2 + 2) + (4*4) AST: (+ 3 (+ (trunc 3 (* 4 (+ 2 2))) (* 4 4))) value: 19
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>
zkl
In zkl, the compiler stack is part of the language and is written in zkl so ... <lang zkl>Compiler.Parser.parseText("(1+3)*7").dump(); Compiler.Parser.parseText("1+3*7").dump();</lang> The ASTs look like
- Output:
class RootClass# Input source: "<text>" Attributes: static createReturnsSelf ... { Block(Class) <Line 1> Exp( (,1,+,3,),*,7 ) } class RootClass# Input source: "<text>" ... { Block(Class) <Line 1> Exp( 1,+,3,*,7 ) }
Evaluating them is just moving up the stack: <lang zkl>Compiler.Compiler.compileText("(1+3)*7").__constructor(); vm.regX; Compiler.Compiler.compileText("1+3*7").__constructor(); vm.regX;</lang>
- Output:
28 22
- Programming Tasks
- Solutions by Programming Task
- Recursion
- Ada
- ALGOL 68
- AutoHotkey
- BBC BASIC
- C
- C++
- Boost.Spirit
- Clojure
- Common Lisp
- D
- E
- Elena
- ERRE
- Factor
- F Sharp
- Go
- Groovy
- Haskell
- Icon
- Unicon
- J
- Java
- JavaScript
- Julia
- Lua
- Liberty BASIC
- Mathematica
- OCaml
- OoRexx
- Oz
- Pascal
- Perl
- Perl 6
- PicoLisp
- Pop11
- Prolog
- Python
- Racket
- REXX
- Ruby
- Scala
- Sidef
- Tcl
- TXR
- Gnuplot/Omit
- Ursala
- Zkl