Arithmetic evaluation: Difference between revisions
Content added Content deleted
(clarification) |
m (Fixed typos and added precedence list.) |
||
Line 1: | Line 1: | ||
{{task}} |
{{task}} |
||
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. |
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. |
||
The expression will be a string of list of symbols like "(1+3)*7". |
|||
For those who don't remember, mathematical precedence is as follows: |
|||
+ - * / as binary operators must be supported including precedence levels, as well as paranthesis. |
|||
Parentheses |
|||
Exponents (not in this program) |
|||
Multiplication/Division (left to right) |
|||
Addition/Subtraction (left to right) |
|||
=={{header|Prolog}}== |
=={{header|Prolog}}== |
Revision as of 21:21, 11 December 2007
![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 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)
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).