Exercise from SICP:

Exercise 1.2.

Translate the following expression into prefix form

\[ \frac{5 + 4 + (2 - (3 - (6 + \frac{1}{5})))}{3(6-2)(2-7)} \]

Solution

One way to do this is to read it from the outside in and translate it into a tree (for example the first thing we extract is the division).

graph BT; DIV[`/`] --> ANS TOP[.] --> ANS[.] BOTTOM[.] --> ANS TOPSUM[+] --> TOP S1[5] --> TOP S2[4] --> TOP S3[.] --> TOP S3A[-] --> S3 S3B[2] --> S3 S3C[.] --> S3 S3C1[+] --> S3C S3C2[.] --> S3C S3C3[.] --> S3C S3C2A[-] --> S3C2 S3C2B[3] --> S3C2 S3C2C[6] --> S3C2 RATIODIV[`/`] --> S3C3 RATIONUM[4] --> S3C3 RATIODEN[5] --> S3C3 PROD[*] --> BOTTOM P1[3] --> BOTTOM P2[.] --> BOTTOM P3[.] --> BOTTOM P2a[-] --> P2 P2b[6] --> P2 P2c[2] --> P2 P3a[-] --> P3 P3b[2] --> P3 P3c[7] --> P3

We can then read this diagram from the top down to get prefix notation:

(/ (+ 5 4 (- 2 (+ (- 3 6) (/ 4 5))))
   (* 3 (- 6 2) (- 2 7)))