Evaluate Reverse Polish Notation

Hi Geeks! Welcome to 100 Days of Leetcode Challenge.

Day 4

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +-*/. Each operand may be an integer or another expression.

Note:

  • 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

How to approach this problem

When you observe this problem, immediately one thing comes to your mind.

Yea, you are correct. That is Stack. By using Stack, we can easily solve this problem.

Basic knowledge

  1. Stack – push() and pop() operations
  2. Switch statements

Solution

C# Program

      public class Solution {
      public int EvalRPN(string[] tokens) {
        
        Stack<int> stack = new Stack<int>();
        foreach(string s in tokens)
        {
            switch(s)
            {
                case "+":
                    stack.Push(stack.Pop() + stack.Pop());
                    break;
                
                case "-":
                    stack.Push(-stack.Pop() + stack.Pop());
                    break;
                    
                case "*":
                    stack.Push(stack.Pop() * stack.Pop());
                    break;
                    
                case "/":
                    int n2 = stack.Pop();
                    int n1 = stack.Pop();
                    stack.Push(n1/n2);
                    break;
                    
                default:
                    stack.Push(Convert.ToInt32(s));
                    break;
            }
        }
        
        return stack.Pop();
    }
}

Solution Explanation

Consider this example,

Input: ["2", "1", "+", "3", "*"]
Output: 9

Whenever number appears, insert it into the stack.

  • When “+” appears, pop() two values from the stack.
  • Add these two values and insert it into the stack

Here, we popped 2 and 1 from the stack, we added that, it becomes 3.

Now we inserted back into the stack.

Continue the process. Now we got another integer 3. Insert into the stack. Now the stack looks like.

  • When “*” appears, pop() two values from the stack.
  • Multiply these two values and insert it into the stack

Here, we popped 3 and 3 from the stack, we multiplied that, it becomes 9. We inserted back into the stack.

Now pop() the stack, to get our desired output.

Time Complexity: O(n)

Space complexity: O(n)

That’s all about Evaluate Reverse Polish Notation.

0 thoughts on “Evaluate Reverse Polish Notation”

  1. Pingback: 100 Days Leetcode Challenge – Passion of Programming

Leave a Comment

Your email address will not be published. Required fields are marked *