### 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:

- "P
**lease 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".

## 0 Comments:

## Post a Comment

Subscribe to Post Comments [Atom]

## Links to this post:

Create a Link

<< Home