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 .

## Input representation

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:

`(9*(6+(6/(6-9))))`

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.
```

## No comments:

Post a Comment