Using Stacks to Evaluate Prefix and Postfix Expressions

Using Stacks to Evaluate Postfix (and Prefix) Expressions

Watch this video: https://www.youtube.com/watch?v=MeRb_1bddWg

Using Stacks to Convert Between Infix and Postfix Expressions

Watch this video: https://www.youtube.com/watch?v=vq-nUF0G4fI


Arithmetic Expression Evaluation

Taken from West Chester University web site:

This section illustrates two common stack-based algorithms for arithmetic expression manipulation:
  1. evaluating an arithmetic expression written in postfix form.
  2. converting an infix expression to postfix form.
Converting an infix expression (the usual form) to postfix means to write the expression so that the operators come after the operands. There are no parentheses in such expressions. For simplicity we'll look at only the standard binary operators:
+, –, *, /

Postfix expression evaluation

In the postfix expression evaluation algorithm, the stack contains only numbers. Here is a sketch of the algorithm:
for each expression token:
  if the token is a number:
    push it
  else (the token is an operator, OP):
    second = pop();
    first = pop();
    compute: result = first OP second
    push the result on the stack

when there are no more tokens, pop the answer off the stack
The arithmetic expressions 4 - ( 2 - 3 ) and 4 - 2 - 3 have these respective postfix expressions and evaluations:
4 2 3 - -

token    stack
-----    -----
         []
  4      [4]
  2      [2, 4]
  3      [3, 2, 4]
  -      [-1, 4]
  -      [5]
 END     []    ⇒ answer = 5
4 2 - 3 -

token    stack
-----    -----
         []
  4      [4]
  2      [2, 4]
  -      [2]
  3      [3, 2]
  -      [-1]
 END     []    ⇒ answer = -1
The arithmetic expression ( 7 + 3 ) * ( 11 - 4 * 2 ) has the following postfix form and evaluation:
7 3 + 11 4 2 * - *

token    stack
-----    -----
         []
  7      [7]
  3      [3, 7]
  +      [10]
  11     [11, 10]
  4      [4, 11, 10]
  2      [2, 4, 11, 10]
  *      [8, 11, 10]
  -      [3, 10]
  *      [30]
 END     []    ⇒ answer = 30

Infix to Postfix conversion

The infix-to-postfix conversion algorithm is more complicated. It is extremely simple if all operators have the same precedence (such as "+" and "") and there are no parentheses. Adding parentheses and operators of differing precedence introduces complications.

The goal of the algorithm is to construct an output string which is the equivalent postfix form of a given infix expression. The stack will hold operators and left parentheses. One key observation is that the numbers stay in the same order as in the infix expression.

Here is a sketch of the algorithm:
for each expression token:
  if the token is a number:
    add it to output
  else if the token is a left paren:
    push it
  else if the token is a right paren:
    pop and add to output all tokens on stack up to left paren
    pop the left paren, but don't add to output
  else if the token is an operator:
    if stack is empty or the top is a left paren:
       push it
    else if the stack top is a lower precedence operator:
       push it
    else
       pop and add to output all operators of higher or equal precedence 
       push it

when there are no more tokens,
  pop and add to output all remaining operators on stack
Observe in the way numbers are handled that the numbers appear in the same order as in the infix expression. Here are some examples:
7 - 3 + 5 - 2

token   stack     output
-----   -----     ------
        []
  7               7
  -     [-]
  3               7 3
  +     [+]       7 3 -
  5               7 3 - 5
  -     [-]       7 3 - 5 +
  2               7 3 - 5 + 2
 END    []        7 3 - 5 + 2 -
7 + ( 3 + 5 - 4 ) - 2

token    stack        output
-----    -----        ------
         []
  7                   7
  +      [+]
  (      [ (, +]
  3                   7 3
  +      [+, (, +]
  5                   7 3 5
  -      [-, (, +]    7 3 5 +
  4                   7 3 5 + 4
  )      [+]          7 3 5 + 4 -
  -      [-]          7 3 5 + 4 - +
  2                   7 3 5 + 4 - + 2
 END     []           7 3 5 + 4 - + 2 -
7 + 10 * 6 / 4

token   stack         output
-----   -----         ------
        []        
  7                   7
  +     [+]
  10                  7 10
  *     [*, +]
  6                   7 10 6
  /     [/, +]        7 10 6 *
  4                   7 10 6 * 4
 END    []            7 10 6 * 4 / +

Java Programs

These two programs are intended to be in the demo package.

The Infix2Postfix program enters and processes an arithmetic expression (in standard infix form), generating an output of the arithmetic expression in postfix form. Operands are assumed to be unsigned non-negative integers.
demo.Infix2Postfix   
The PostfixEvaluation program evaluates a postfix expression. Again, operands are assumed to be unsigned non-negative integers.
demo.PostfixEvaluate   

Practice Problem 11 Solutions

  1. Convert:   19 - ( 7 - 4 * 3 + 2 ) * ( 7 - 5 )
    token   stack           output
    -----   -----           ------
    19                      19
    -       [-]
    (       [(,-]
    7                       19 7
    -       [-,(,-]        
    4                       19 7 4
    *       [*,-,(,-]       
    3                       19 7 4 3
    +       [+,(,-]         19 7 4 3 * -
    2                       19 7 4 3 * - 2
    )       [-]             19 7 4 3 * - 2 +
    *       [*,-]
    (       [(,*,-] 
    7                       19 7 4 3 * - 2 + 7
    -       [-,(,*,-]
    5                       19 7 4 3 * - 2 + 7 5
    )       [*,-]           19 7 4 3 * - 2 + 7 5 -
    END     []              19 7 4 3 * - 2 + 7 5 - * -
    
    Evaluate:   19 7 4 3 * - 2 + 7 5 - * -
    token           stack
    -----           -----
    19, 7, 4, 3     [3, 4, 7, 19]
    *               [12, 7, 19]
    -               [-5, 19]
    2               [2, -5, 19]
    +               [-3, 19]
    7, 5            [5, 7, -3, 19]
    -               [2, -3, 19]
    *               [-6, 19]
    -               [25]
    END             []           => 25
    
    
  2. Convert:   3 - 7 * 15 / ( 2 + 3 )
    token   stack           output
    -----   -----           ------
    3 	[]		3 
    - 	[-]		 
    7 	[-]		3 7 
    * 	[*, -]
    15 	[*, -]		3 7 15 
    / 	[/, -]		3 7 15 * 
    ( 	[(, /, -]
    2 	[(, /, -]	3 7 15 * 2 
    + 	[+, (, /, -]
    3 	[+, (, /, -]
    ) 	[/, -]		3 7 15 * 2 3 + 
    END     []		3 7 15 * 2 3 + / - 
    
    
    
  3. Convert:   17 - ( 22 - ( 11 - 8 + 2 ) )
    token   stack              output
    -----   -----              ------
            []
    17                         17
    -       [-]
    (       [(, -]       
    22                         17 22
    -       [-, (, -]
    (       [(, -, (, -]
    11                         17 22 11
    -       [-, (, -, (, -]
    8                          17 22 11 8
    +       [+, (, -, (, -]    17 22 11 8 -
    2                          17 22 11 8 - 2
    )       [-, (, -]          17 22 11 8 - 2 +
    )       [-]                17 22 11 8 - 2 + -
    END     []                 17 22 11 8 - 2 + - -