Expressions

Expression Trees

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:

Expression trees git.charlesreid1.com link: https://git.charlesreid1.com/cs/java/src/master/trees/expressions

Postfix expression tree builder code: https://git.charlesreid1.com/cs/java/src/master/trees/expressions/PostfixExpressionTree.java

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 )

The corresponding infix expression builder pseudocode follows.

Infix expression builder code: https://git.charlesreid1.com/cs/java/src/master/trees/expressions/InfixExpressionTree.java

Infix expression tree builder:

create new node stack
set start new expression to true
while next char in expression:
	take next char
	if numeric:
		make new node
		if start new expression:
			push node onto stack
			set start new expression to false
		else if expression on stack:
			peek at top of stack
			if top of stack is operator:
				if top of stack has 1 child:
					add right child
				else:
					error
			else:
				error
	if operator:
		new node
		pop stack
		set node left to popped item
		push node onto stack
	if (:
		set start new expression to true
	if ):
		if stack size > 1:
			pop top of stack
			peek top of stack
			set popped item to peek's right

while stack size > 1:
pop top
peek top of stack
set popped item to peek's right