Arithmetic evaluation
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
A program which parses and evaluates arithmetic expressions. Requirements: an AST for the expression must be created from parsing the input, the AST must be used in evaluation also, so no calling eval or similar if the language has such a thing. The expression will be a string or list of symbols like "(1+3)*7". + - * / as binary operators must be supported including precedence levels, as well as parentheses.
For those who don't remember, mathematical precedence is as follows:
- Parentheses
- Exponents (not in this program)
- Multiplication/Division (left to right)
- Addition/Subtraction (left to right)
D
module test; import std.stdio; int calculate(string expr) { string take(int count) { auto res = expr[0 .. count]; expr = expr[count .. $]; return res; } string peek(int count) { if (expr.length < count) count = expr.length; return expr [0 .. count]; } int delegate(int level) descent; // grab the next number from the input expression int getNumber() { int res; // if our "number" is a parantheses-wrapped expression, evaluate it if (peek(1) == "(") { take(1); return descent(0); } while (expr.length) { auto next = peek(1)[0]; // if the next character is a digit ... if (next >= '0' && next <= '9') { res = res * 10 + (next-'0'); take(1); } else return res; } return res; } // descent evaluates a level-l expression (1: multiplication and division, 0: also addition and subtraction) descent = (int l) { auto num = getNumber; // get the first number of our expression while (expr.length) { auto op = take(1)[0]; if (op == ')') return num; // expression end if (op == '*') num *= getNumber; if (op == '/') num /= getNumber; if (l == 1) return num; if (op == '+') num += descent(1); if (op == '-') num -= descent(1); } return num; }; return descent(0); } void main() { writefln(calculate("(3+50)*7-9"), ", ", (3+50)*7-9); }
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"
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).