Reverse Polish ‘Notation is postfix notation which in terms of mathematical notion signifies operators following operands. Let’s take a problem statement to implement RPN
Problem Statement: The task is to find the value of the arithmetic expression present in the array using valid operators like +, -, *, /. Each operand may be an integer or another expression.
Note:
- The division between two integers should truncate toward zero.
- The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation.
Layman Working of RPN as shown
Input: ["2", "1", "+", "3", "*"] Output: 9 Explanation: ((2 + 1) * 3) = 9 Input: ["4", "13", "5", "/", "+"] Output: 6 Explanation: (4 + (13 / 5)) = 6 Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"] Output: 22 Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = ((10 * (6 / (12 * -11))) + 17) + 5 = ((10 * (6 / -132)) + 17) + 5 = ((10 * 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22
Approach:
The basic approach for the problem is using the stack.
- Accessing all elements in the array, if the element is not matching with the special character (‘+’, ‘-‘,’*’, ‘/’) then push the element to the stack.
- Then whenever the special character is found then pop the first two-element from the stack and perform the action and then push the element to stack again.
- Repeat the above two process to all elements in the array
- At last pop the element from the stack and print the Result
Implementation:
Python3
# Python 3 code to evaluate reverse polish notation # function to evaluate reverse polish notation def evaluate(expression): # splitting expression at whitespaces expression = expression.split() # stack stack = [] # iterating expression for ele in expression: # ele is a number if ele not in '/*+-': stack.append(int(ele)) # ele is an operator else: # getting operands right = stack.pop() left = stack.pop() # performing operation according to operator if ele == '+': stack.append(left + right) elif ele == '-': stack.append(left - right) elif ele == '*': stack.append(left * right) elif ele == '/': stack.append(int(left / right)) # return final answer. return stack.pop() # input expression arr = "10 6 9 3 + -11 * / * 17 + 5 +" # calling evaluate() answer = evaluate(arr) # printing final value of the expression print(f"Value of given expression'{arr}' = {answer}") |
Output
Value of given expression'10 6 9 3 + -11 * / * 17 + 5 +' = 22
Time complexity: O(n)
Auxiliary Space: O(n)
Please refer complete article on Evaluate the Value of an Arithmetic Expression in Reverse Polish Notation in Java for more details!
