Queue Applications

Infix Expression Evaluation

In-fix Expressions
- Order: left-operand, operator, right-operand.
- Parentheses are often needed to indicate order of operation.
- Example: (3 + 4) * (5 + 6).
Evaluation
- Begin with an empty stack and an empty queue.
- Process the tokens from left to right according to the following rules.
  - If the token is a number,
    - Enqueue the token.
  - If the token is a left parenthesis,
    - Push the token onto the stack.
  - If the token is a right parenthesis,
    - Pop tokens off the stack and enqueue them until
      - A left parenthesis is popped.
    - Discard the token and the left parenthesis.
  - If the token is an operator,
    - Pop tokens off the stack and enqueue them until
      - An operator of lower precedence is on top of the stack, or
      - A left parenthesis is on top of the stack, or
      - The stack is empty.
    - Push the token onto the stack.
- After processing the last token
- The queue now contains the expression in post-fix notation.
- Process the queue as a post-fix expression.
Sample program - InfixEvaluator.exe

This page was last modified on Mar 28, 2001

URL: http://people.hsc.edu/faculty-staff/robbk/Coms262/Lectures/QueueAppsInfix.html