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.

3 thoughts on “Evaluate Reverse Polish Notation

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s