4.Evaluate Reverse Polish Notation

Postfix Expression

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

Solution : (Using Stack)

Algorithm:

1) Create a stack to store the value / numbers. 2) Scan the given expression and do following for every scanned element. a) If the element is a number, push it into the stack. b) If the element is a operator, pop first two numbers from stack. c) The 1st no is right operand and 2nd no is left. c) Evaluate the operator and push the result back to the stack. 3) When the expression is ended, the number in the stack is the final answer.

class Solution
{
public:
    int evalRPN(vector<string> &tokens)
    {

        stack<int> s;
        for (int i = 0; i < tokens.size(); i++)
        {
          
            if(tokens[i]=="+" || tokens[i]=="-" || tokens[i]=="*" || tokens[i]=="/")
            {
                int res;
                int r = s.top();
                s.pop();
                int l = s.top();
                s.pop();

                if (tokens[i] == "+")
                {
                    res = l + r;
                }
                else if (tokens[i] == "-")
                {
                    res = l - r;
                }
                else if (tokens[i] == "/")
                {
                    res = l / r;
                }
                else if (tokens[i] == "*")
                {
                    res = l * r;
                }
                s.push(res);
            }
            
            else
            {
                int n = stoi(tokens[i]); //convert a string to interger
                s.push(n);
            }
        }
        
        return s.top();
    }
};