Arithmetic evaluation: Difference between revisions
Content added Content deleted
m (Stupid wiki...) |
(Added Haskell version) |
||
Line 7: | Line 7: | ||
* Multiplication/Division (left to right) |
* Multiplication/Division (left to right) |
||
* Addition/Subtraction (left to right) |
* Addition/Subtraction (left to right) |
||
=={{header|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" |
|||
=={{header|Prolog}}== |
=={{header|Prolog}}== |
Revision as of 21:24, 11 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).