# prolog - Predicate that turns an expression into right bracketed form?

I am trying to write a predicate `rightBrack(E1, E2)` where `E2` is the expression `E1` but in right bracketed form. An expression is defined as:

`` Expr ::= lit(i)|add(Expr, Expr)|sub(Expr, Expr)``

So for example if `E1 = add(add(add(lit(2), lit(3)), lit(4)),lit(5))` then `E2` should be `add(lit(2), add(lit(3), add(lit(4), lit(5))))`

I am not comfortable with Prolog at all, and I do not have much experience with it. With that said, I tried writing the following which does not work and I don't know how to make it work. Any help is appreciated.

``rightBrack(add(add(E1, E2), E3), add(E4, add(E5, E6))) :-rightBrack(E1, E4),rightBrack(E2, E5),rightBrack(E3, E6).rightBrack(add(E1, E2), add(E3, E4)) :-rightBrack(E1, E3),rightBrack(E2, E4).rightBrack(sub(E1, E2), sub(E3, E4)) :-rightBrack(E1, E3),rightBrack(E2, E4).rightBrack(lit(N), lit(N)).``

``````noadd(lit(_)).

rightBrack(E1, E3),
rightBrack(E2, E4).
rightBrack(sub(E1, E2), sub(E3, E4)) :-
rightBrack(E1, E3),
rightBrack(E2, E4).
rightBrack(lit(N), lit(N)).
``````

Nice problem, the transformation need to change the tree from

``````?- draw(add(add(add(lit('2'), lit('3')), lit('4')),lit('5'))).

|
+-------+
|       |
+------+    |
|      |    |
+----+    |    |
lit  lit   |    |
|    |    |    |
|    |    |    |
2    3    4    5
``````

to

``````?- draw(add(lit('2'), add(lit('3'), add(lit('4'), lit('5'))))).

|
+---------+
|         |
|    +-------+
|    |       |
|    |    +----+
|    |   lit  lit
|    |    |    |
|    |    |    |
2    3    4    5
``````

I've renamed some constant (just easier to read, to me)

``````l2r(+(A,B),+(C,D)) :-
l2r(A,B, C,D), !.
l2r(A, A).

l2r(+(A1,A2),B1, A3,+(A4,B2)) :-
l2r(A1,B1, A3,B2),
l2r(A2,A4).
l2r(A1,+(B1,B2), A2,+(B3,B4)) :- % as noted by @false
l2r(B1,B2, B3,B4),
l2r(A1,A2).
l2r(A,B, A,B).
``````

mini test:

``````?- l2r(+(+(+(1,2),3),4),R),display(R).
+(1,+(3,+(2,4)))
R = 1+ (3+ (2+4)).

?- l2r(+(1,+(+(2,3),4)),R),display(R).
+(1,+(2,+(3,4)))
R = 1+ (2+ (3+4)).
``````