Using a Stack in Java

You can compare a Stack with a worker in a restaurant that puts his clean plates on an elastic spring. He can only see the plate that is on top. He can put a plate on top (in stack terminology: push), he can take away the top plate (in stack terminology: pop) or he can just look at the plate that’s on top though that can get pretty boring after a while (in stack terminology: peek). This principle of entities leaving a queue in reverse order of the sequence in which they arrive is also called LIFO (Last In First Out).

Stacks are very useful in programming. For example, programs maintain a stack of local variables that are pushed on the stack when they get in scope and popped back off when they go out of scope (this is where those variables are stored).

The following program shows how to use a stack in another way. Maybe you remember those weird HP calculators from a couple years back. They used the Reverse Polish Notation (RPN). If you wanted to make the calculation 3 + 4, you had to enter 3, enter 4 and press + (RPN: 3 4 + ). The operands of the expression are pushed on the stack as they are typed in and the operators pop them, make the computation and push the result back on the stack.

Steps in computing a RPN:

   1.   loop: scan RPN expression from left to right 
      1.1   if operand ==> push on stack
      1.2   if operator ==> pop top two operands off stack and push result back on
   2.   the result is the top (and only) element on the stack

Main.java:

import java.util.*;
import java.io.*;
  
public class Main {   
   public static void main(String[] args) {
      System.out.println(RPN.evaluate("3 2 + 7 * 35 /"));
      System.out.println(RPN.evaluate("1 23 + 45 6 + *"));
   }
}
 
class RPN 
{
   public static int evaluate(String expression) {
      Stack stack = new Stack();
 
      StringTokenizer st = new StringTokenizer(expression);
      while (st.hasMoreTokens()) {
         String var = (String) st.nextElement();
 
         // it's an integer
         if (Character.isDigit(var.charAt(0))) {   
            stack.push(new Integer(var));
         }
         // it's an operator
         else { 
            // get top two elements
            int op1 = ((Integer) stack.pop()).intValue();
            int op2 = ((Integer) stack.pop()).intValue();
  
            // perform calculation and push result back on stack
            if (var.equals("+")) stack.push(new Integer(op1 + op2));
            if (var.equals("-")) stack.push(new Integer(op1 - op2));
            if (var.equals("*")) stack.push(new Integer(op1 * op2));
            if (var.equals("/")) stack.push(new Integer(op1 / op2));
         }
      }
 
      return ((Integer) stack.pop()).intValue();
   }
}

outputs:

1
1224