Expressions

Two main kinds of expressions that you see:

• postfix expressions (a.k.a. reverse polish notation)
• infix expressions (a.k.a. what we use all the time)

A postfix expression looks like:

5 4 + 8 3 - * 15 /

which, when analyzed left to right, means take 5 and 4 and add them, to get 9, then take 8 and 3 and subtract them, to get 5, and then take the 9 and the 5 and multiply them, to get 45, and then take the 45 and the 15, and divide them to get 3.

This same expression would be written with infix notation, with parentheses, like so:

((5+4)*(8-3))/15

Algorithms

To analyze and evaluate thees kinds of expressions, we often want to build an expression tree. Here is some pseudocode for two algorithms for building postfix and infix expression trees, plus a link to Java code that does this:

git.charlesreid1.com link:

Postfix expression tree builder:

create tree node stack
/* the last pop of this stack will be our root node */
while next char in expression:
    take next char
    if numeric:
        make new node
        add node to stack
    if operator:
        make new node
        left = pop
        right = pop
        add node to stack

new tree( pop stack )

and the corresponding infix expression builder pseudocode follows.

Infix expression tree builder: