Arithmetic evaluation: Difference between revisions
Content added Content deleted
(Added Haskell version) |
|||
Line 21: | Line 21: | ||
table = [[op "*" (Mul) AssocLeft, op "/" (Div) AssocLeft] |
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 |
where op s f assoc = Infix (do string s; return f) assoc |
||
factor = do char '(' ; x <- expr ; char ')' |
factor = do char '(' ; x <- expr ; char ')' |
||
return x |
return x |
||
<|> do ds <- many1 digit |
<|> do ds <- many1 digit |
||
return $ Num (read ds) |
return $ Num (read ds) |
||
Line 38: | Line 38: | ||
Right expr -> evaluate expr |
Right expr -> evaluate expr |
||
Left _ -> error "Did not parse" |
Left _ -> error "Did not parse" |
||
=={{header|Prolog}}== |
=={{header|Prolog}}== |
Revision as of 14:52, 25 December 2007
Arithmetic evaluation
You are encouraged to solve this task according to the task description, using any language you may know.
You are encouraged to solve this task according to the task description, using any language you may know.
A program which parsers 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)
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).