How to Evaluate Reverse Polish Notation - The Coding Shala

Home >> Interview Questions >> Evaluate Reverse Polish Notation

How to Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation. The Valid operators are +, -, *, /. 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.

Example 1:
Input: ["2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:
Input: ["4", "13", "5", "/", "+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:
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

Reverse Polish Notation Java Program

Method 1:
Using Stack.
If a valid operator comes then pop two-element from the stack, evaluate them and push the result back. Return top element at the end.

Java Code: 
class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> st = new Stack<Integer>();
        for(String ch : tokens){
            if(ch.equals("+")){
                int num1 = st.pop();
                int num2 = st.pop();
                st.push(num1+num2);
            }else if(ch.equals("-")){
                int num1 = st.pop();
                int num2 = st.pop();
                st.push(num2-num1);
            }else if(ch.equals("*")){
                int num1 = st.pop();
                int num2 = st.pop();
                st.push(num1*num2);
            }else if(ch.equals("/")){
                int num1 = st.pop();
                int num2 = st.pop();
                st.push(num2/num1);
            }else{
                st.push(Integer.parseInt(ch));
            }
        }
        return st.pop();
    }
}



Other Posts You May Like
Prev<< Rotate Linked List                                                                              NEXT >>Valid Parentheses
Please leave a comment below if you like this post or found some error, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Add two numbers in Scala - The Coding Shala

LeetCode - Number of Good Pairs Solution - The Coding Shala

Richest Customer Wealth LeetCode Solution - The Coding Shala