Stacks, Infix, Prefix, Postfix

Infix

• Most common style of representing mathematical expressions
• Operators are smashed between operands
• Parenthesis are required for order of operations
• Can easily be represented by a binary tree

A) 1 + 2
B) (1 + 2) * 13 
C) 1 + 2 * 13
D) 1 + 2 * ((13 - 1) + 5)

Prefix

• Also refered to as Polish Notation
• Operators come before its operands
• Parenthesis are not required for order of operations

A) + 1 2
B) * + 1 2 13 
C) + 1 * 2 13
D) + 1 * 2 + - 13 1 5

Postfix

• Also refered to as Reverse Polish Notation
• Operators come after its operands
• Parenthesis are not required for order of operations

A) 1 2 +
B) 1 2 + 13 * 
C) 1 2 13 * +
D) 1 2 13 1 - 5 + * +

See: http://www.cs.man.ac.uk/~pjj/cs2121/fix.html for more information.

In-lab activity

Convert the following infix expressions into prefix and postfix notation

• 1 + 2 + 3
• 1 * 2 + 3
• 1 + 2 * 3
• (1 + 2) * 3

Evaluate the following prefix expressions

• • / 4 2 19
• • • 1 3 - 4 2

Evaluate the following postfix expressions

• 15 3 2 + 2 * -
• 10 4 - 1 1 + /

Evaluating postfix expressions

• Can use a single stack

create an empty stack of integers
while there are more tokens
  get the next token
  if the first character of the token is a digit
    push the token on the stack
  else if the token is an operator
    pop the right operand off the stack
    pop the left operand off the stack
    evaluate the operation
    push the result onto the stack
pop the stack and return the result

Evaluating prefix expressions

• Need to use two stacks

create two empty stacks, operatorStack and operandStack
while there are more tokens
  push token to operatorStack

while operatorStack is not empty:
  pop operatorStack
  if popped item is operand
    push to operand stack
  else if item is operator
    pop two operands from operand stack
    evaluate with operator
    push result back to operand stack
pop the stack and return the result

In-lab activity

Complete the methods evaluatePrefix and evaluatePostfix in https://github.com/anthonyjchriste/ics211f13/blob/master/src/fixes/ExpressionEvaluator.java.