Lab 07 Handout: Infix/Prefix/Postfix
Definitions
Infix: The operator is placed between the two operands: 3 + 5
Prefix: The operator is placed before the two operands: + 3 5
Postfix: The operator is placed after the two operands: 3 5 +
Calculator algorithm
- Convert infix to postfix
- Use stack to evaluate postfix
- Output top of stack (should be the only element)
Convert infix to postfix algorithm
- Given a sequence of tokens s and a result r
- While s is not empty:
- Let t = next token.
- If t is an operand, r = r + t;
- If t is an open parenthesis, push it.
- If t is a close parenthesis:
- while top <> open parenthesis
- r = r + top
- pop
- pop // removes the open parenthesis
- while top <> open parenthesis
- If t is an operator
- while not (top is of lower precedence than t OR t is right associative and top is of equal precedence)
- r = r + top
- pop
- push t
- while not (top is of lower precedence than t OR t is right associative and top is of equal precedence)
- while stack not empty
- r = r + top
- pop
Evaluate postfix algorithm
- Given a sequence of tokens s
- While s is not empty:
- Let t = next token.
- If t is an operand, push it;
- If t is an operator:
- put the top into rhs, pop it;
- put the top into lhs, pop it;
- calculate lhs t rhs;
- push the result
- The top of the stack is the result.