Data structures and algorithms in Java

This post explains what is a reverse polish notation, how to evaluate a reverse polish notation and an algorithm for the same. It also provides a program which evaluates such a notation.

Prerequisites :

Knowledge of Java, data structures, stack data structure and the operations that can be performed on it. Understanding about time and space complexity is required.

Explanation :

Stack data structure is a very effective data structure in evaluating arithmetic expressions. Arithmetic expressions are usually represented using infix notations. Infix notations are the notations in which the operator lies in between the operands. For example, A + B where A and B are the operands and + is the operator.

Polish notation (Prefix notation) :

It is a mathematical notation in which the operators e.g +, -, *, / precede their operands. For example, + A B.

Reverse polish notation (Postfix notation) :

Reverse polish notation is a mathematical notation in which the operators e.g. +, -, *, / follow their operands e.g. A B + in contrast to the polish notation in which the operators precede their operands. The reverse polish notation is obtained by reversing the polish notation.

Examples :

+ 3 4 is the prefix/polish notation in which the operator (+) sign precedes the operands 3 and 4.

3 4 + is the postfix /reverse polish notation in which the operator (+) sign follows the operands 3 and 4.

3 + 4 is the infix notation in which the operator (+) lies in between the operands.

How to evaluate a reverse polish notation?

Let us understand this by considering a simple example, 3 4 *.

Start reading the notation from left to right. Consider 3 as the first operand and 4 as the second operand. Now, apply the operator * on these two operands i.e. 3 * 4 and we get the result as 12.

Algorithm to evaluate a reverse polish notation using a stack :

1. Create a stack of type Stack<Integer> to store the operands.
2. Scan the string s from left to right and perform below for every element that is scanned.
   • If the element scanned is an operand, push the element to the stack.
   • If the element scanned is an operator, pop two elements from the stack and evaluate the expression using the operator and popped elements and push the result back to the stack.
3. When the scanning of entire string is complete, the element left in the stack is the result.

Diagrammatic representation :

Implementation of above algorithm :

class EvalReversePolishNotation {
	public static int evalRPN(String s) {

		// stack to store operands
		java.util.Stack stack = new java.util.Stack<Integer>();
		String tokens[] = s.split(" ");
		int expLength = tokens.length;

		// parse the entire expression
		for (int i = 0; i < expLength; i++) {
			int result, element1, element2;
			switch (tokens[i]) {
			case "+":
				element1 = (Integer) stack.pop();
				element2 = (Integer) stack.pop();
				result = element2 + element1;
				stack.push(result);
				break;
			case "-":
				element1 = (Integer) stack.pop();
				element2 = (Integer) stack.pop();
				result = element2 - element1;
				stack.push(result);
				break;
			case "*":
				element1 = (Integer) stack.pop();
				element2 = (Integer) stack.pop();
				result = element2 * element1;
				stack.push(result);
				break;
			case "/":
				element1 = (Integer) stack.pop();
				element2 = (Integer) stack.pop();
				result = element2 / element1;
				stack.push(result);
				break;
			default:
				result = Integer.parseInt(tokens[i]);
				stack.push(result);

			}
		}
		return (Integer) stack.pop();
	}

	public static void main(String[] args) {
		int result = evalRPN("4 13 5 / +");
		System.out.println("Result of evaluation = " + result);
		int result1 = evalRPN("10 6 9 3 + -11 * / * 17 + 5 +");
		System.out.println("Result of evaluation = " + result1);
	}
}

Output of above code :

Result of evaluation = 6
Result of evaluation = 22

Time and space complexity :

Considering n = length of input Reverse Polish Expression, d = number of operands/digits, o = number of operators, the time complexity of the above implementation is O(n), since we are scanning the entire string. Time taken by push and pop operations is constant i.e. O(1) constant time complexity.

Space complexity = O(d), since we store only operands/digits in the stack and this is the worst case for space complexity in which we push all the operands to the stack, e.g. 2 3 4 * +.

Here is the link to the above code on my github profile, Evaluating reverse polish notation.

If you enjoyed this post and it helped you to learn something new please support by sharing it. Your feedback is highly appreciated.