arithmetic computer

Question

I need some help in prolog, which is pretty new to me. I have to design a small arithmetic computer. The expression to be evaluated will be represented as a list for example:

?-evaluate([2,+,4,*,5,+,1,*,2,*,3],R).

I am trying to do this by designing two predicates one called parse to transform my list for example:

?-parse([1,+,2,*,3],PF).
PF=[+,1,[*,2,3]]

and another one to evaluate the new expression.

?-evpf([+,1,[*,2,3]],R).
R=7

I have problems with the first part, can anyone help my with the code?

Tattle

The central challenge here, at least after applying DCG techniques as mat outlined, is converting from "infix operator" notation to "prefix operator" form of an expression. To do so correctly you need to specify the rules for operator precedence. Does * have higher precedence than +? Are operations performed in right-to-left order? Either possibility is consistent with your single example (see PF above) of transforming a list. What rule did you have in mind? – Fluoro

Answer 1

Parsing (= converting a list to an abstract syntax tree) is easy with DCGs:

list_ast(Ls, AST) :- phrase(expression(AST), Ls).

expression(E)       --> term(T), expression_r(T, E).

expression_r(E0, E) --> [+], term(T), expression_r(E0+T, E).
expression_r(E0, E) --> [-], term(T), expression_r(E0-T, E).
expression_r(E, E)  --> [].

term(T)       --> power(P), term_r(P, T).
term_r(T0, T) --> [*], power(P), term_r(T0*P, T).
term_r(T0, T) --> [/], power(P), term_r(T0/P, T).
term_r(T, T)  --> [].

power(P)          --> factor(F), power_r(F, P).
power_r(P0, P0^P) --> [^], factor(P1), power_r(P1, P).
power_r(P, P)     --> [].

factor(N) --> [N], { number(N) }.
factor(E) --> ['('], expression(E), [')'].

To actually evaluate the expression, you can then use the built-in predicate is/2. Sample query:

?- list_ast([2,+,4,+,5,+,1,+,2,*,3], Ast), V is Ast.
Ast = 2+4+5+1+2*3,
V = 18 ;
false.

Artel

Thank you, it is not exactly what i wanted, but i can use the predicate provided by you to create the desired list – Tattle

Yes, I forgot to add: This is very easy, for example with an additional DCG that translates the AST to a different representation, or by modifying the above DCG. – Artel