Core Java coding interview question and answer on Reverse Polish Notation (RPN)

Q.  Can you explain Reverse Polish Notation (RPN)?
A.  You have already heard about the following from your elementary schooling:

• "Please Excuse My Dear Aunt Sally" (meaning Parentheses, Exponentiation (roots and powers), Multiplication, Division, Addition, and Subtraction
• BODMAS, tells us to attend to Brackets, Of, Division, Multiplication, Addition, and Subtraction

This means:

(1+2)*3 = 9 using BODMAS or  "Please Excuse My Dear Aunt Sally" 

Polish Notation was invented in the 1920's by Polish mathematician Jan Lukasiewicz, who showed that by writing operators in front of their operands, instead of between them, brackets were made unnecessary. 

3 2 1 + x = 9  using Reverse Polish Notion (RPN).

In programming, the RPN is evaluated using a stack, which is a LIFO (Last In First Out) data structure.

The algorithm for RPN is: 

Keep pushing the numbers into a stack, and when it is an operator, pop two numbers from the stack, do the calculation, and push back the result.

Q. Can you write code that demonstrates RPN?
A. It can be coded in Java 7, as shown below. Java 7 supports string in switch statements.

package com.java8.examples;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

public class ReversePolishNotationTest {

 public static void main(String[] args) {
  
  String[] tokens = new String[] { "3", "2", "1", "+", "*" };
        System.out.println(evalRPN(tokens));
 }
 
 
 
 public static int evalRPN(String[] tokens){
  int result = 0;
  String operators = "+-*/";
  
  //Double ended queue can be used as a stack LIFO(push/pop) or queue FIFO (offer/poll).
  Deque<String> stack = new ArrayDeque<String>();
  
  for (String string : tokens) {
   //keep pushing the numbers
   if (!operators.contains(string)) {
    stack.push(string);
   } else { //for operators
    int a = Integer.valueOf(stack.pop());
    int b = Integer.valueOf(stack.pop());
    switch (string) {
    case "+":
     stack.push(String.valueOf(a + b));
     break;
    case "-":
     stack.push(String.valueOf(b - a));
     break;
    case "*":
     stack.push(String.valueOf(a * b));
     break;
    case "/":
     stack.push(String.valueOf(b / a));
     break;
    }
   }
  }
  
  //get the value left in th stack
  result = Integer.valueOf(stack.pop());
  
  return result;
 }

}

Things to remember:

1. Algorithm: Keep pushing the numbers into a stack, and when it is an operator, pop two numbers from the stack, do the calculation, and push back the result.

2. Use a stack, which is a LIFO data structure.

3. In Java, Deque is a linear collection that supports element insertion and removal at both ends. The name deque is short for "double ended queue" and is usually pronounced "deck".