A couple of days ago my small son came home with math homework from school. The problem: add parenthesis to the following arithmetic expression so it makes sense.
14 * 3 - 8 / 2 = 17
When I saw that, I thought it was a nice little programming exercise. Also Prolog seems like an appropriate language to write the a solution for this problem.
To solve this problem we need at least to:
- Choose a representation for the input formula and the results
- A way to generate all possible combinations of arithmetic expressions
- Something to evaluate the arithmetic expression so we can get the result
- Let Prolog find the answer we need!
First, we need to generate all possible expressions from given the problem .
We're going to represent the input formula as a list of the parts of the expression.
For example, given the following expression:
14 * 3 - 8 / 2
The input representation for this formula is the following:
[ 14, '*', 3, '-', 8, '/', 2 ]
To represent the output formula I'm going to use a term with the form
op(operator, left, right).
For example, to represent the following possible groupings:
It will be represented as:
op(*, 9, op(+, 6, op(/, 6, op(-, 6, 9))))
Generating expression groupings
Given the representation of the problem we can write a predicate to generate all possible groupings of these operations.
After some unsuccessful attempts I came with the following predicate:
arith_op([X], X) :- number(X),!. arith_op(Arr, op(Op, X, Y)) :- append(First, [Op | Second], Arr), arith_op(First, X), arith_op(Second, Y).
What I really like about Prolog is that with relative few words we can find a solution for problems like this.
Now I can take advantage from Prolog's backtracking mechanism and find all possible solutions for the following input.
?- arith_op([ 1, '*', 2, '+', 3, '/', 4] ,X). X = op(*, 1, op(+, 2, op(/, 3, 4))) ; X = op(*, 1, op(/, op(+, 2, 3), 4)) ; X = op(+, op(*, 1, 2), op(/, 3, 4)) ; X = op(/, op(*, 1, op(+, 2, 3)), 4) ; X = op(/, op(+, op(*, 1, 2), 3), 4) ; false.
Evaluating the arithmetic expressions
Having a way to evaluate the expression is useful so we can verify the result of the operation. A simple way to implement it looks like this:
eval(op(Op,X,Y),Result) :- eval(X,R1),eval(Y,R2), ( (Op = '+', Result is (R1 + R2)) ; (Op = '-', Result is (R1 - R2)) ; (Op = '*', Result is (R1 * R2)) ; (Op = '/', Result is (R1 / R2))), !. eval(X, X).
With this predicate we can get the result of an operation. For example:
?- eval(op('+', op('*', 34, 23), 34), R). R = 816.
Solving the problem
With these two predicates we can solve the problem like this:
?- arith_op([ 14, '*', 3,'-', 8, '/', 2 ] ,Operation), eval(Operation, 17). Operation = op(/, op(-, op(*, 14, 3), 8), 2) ; false.
Now it is useful to present the results using infix notation with parenthesis. To do this we can write the following predicate:
forprint(op(Op,X,Y)) :- writef("("), forprint(X), writef(Op), forprint(Y), writef(")"),!. forprint(X) :- write(X),!.
Now we can write:
arith_op([ 14, '*', 3,'-', 8, '/', 2 ] ,Operation), eval(Operation, 17), forprint(Operation). (((14*3)-8)/2) Operation = op(/, op(-, op(*, 14, 3), 8), 2) ; false.
I can also use this predicate to generate samples of results for other groupings. For example:
?- arith_op([ 14, '*', 3,'-', 8, '/', 2 ] ,Operation), eval(Operation, Result), Result > 0, forprint(Operation). ((14*3)-(8/2)) Operation = op(-, op(*, 14, 3), op(/, 8, 2)), Result = 38 ; (((14*3)-8)/2) Operation = op(/, op(-, op(*, 14, 3), 8), 2), Result = 17 ; false.