<p>You are given an array of strings <code>tokens</code> that represents an arithmetic expression in a <a href="http://en.wikipedia.org/wiki/Reverse_Polish_notation" target="_blank">Reverse Polish Notation</a>.</p>

<p>Evaluate the expression. Return <em>an integer that represents the value of the expression</em>.</p>

<p><strong>Note</strong> that:</p>

<ul>
	<li>The valid operators are <code>&#39;+&#39;</code>, <code>&#39;-&#39;</code>, <code>&#39;*&#39;</code>, and <code>&#39;/&#39;</code>.</li>
	<li>Each operand may be an integer or another expression.</li>
	<li>The division between two integers always <strong>truncates toward zero</strong>.</li>
	<li>There will not be any division by zero.</li>
	<li>The input represents a valid arithmetic expression in a reverse polish notation.</li>
	<li>The answer and all the intermediate calculations can be represented in a <strong>32-bit</strong> integer.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> tokens = [&quot;2&quot;,&quot;1&quot;,&quot;+&quot;,&quot;3&quot;,&quot;*&quot;]
<strong>Output:</strong> 9
<strong>Explanation:</strong> ((2 + 1) * 3) = 9
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> tokens = [&quot;4&quot;,&quot;13&quot;,&quot;5&quot;,&quot;/&quot;,&quot;+&quot;]
<strong>Output:</strong> 6
<strong>Explanation:</strong> (4 + (13 / 5)) = 6
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> tokens = [&quot;10&quot;,&quot;6&quot;,&quot;9&quot;,&quot;3&quot;,&quot;+&quot;,&quot;-11&quot;,&quot;*&quot;,&quot;/&quot;,&quot;*&quot;,&quot;17&quot;,&quot;+&quot;,&quot;5&quot;,&quot;+&quot;]
<strong>Output:</strong> 22
<strong>Explanation:</strong> ((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
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= tokens.length &lt;= 10<sup>4</sup></code></li>
	<li><code>tokens[i]</code> is either an operator: <code>&quot;+&quot;</code>, <code>&quot;-&quot;</code>, <code>&quot;*&quot;</code>, or <code>&quot;/&quot;</code>, or an integer in the range <code>[-200, 200]</code>.</li>
</ul>

template <typename T>
class Node
{
public:
    T val;
    Node* next;
    Node(T value, Node* ptr)
    {
        val = value;
        next = ptr;
    }
};

template <typename T>
class Stack
{
public:
    Stack(T val, Node<T>* ptr)
    {
        dummyHead = new Node<T>(val, ptr);
    }

    void push(T val)
    {
        dummyHead->next = new Node<T>(val, dummyHead->next);
    }

    T pop()
    {
        T res = dummyHead->next->val;
        dummyHead->next = dummyHead->next->next;
        return res;
    }

    bool isEmpty()
    {
        return (dummyHead->next == nullptr);
    }

private:
    Node<T>* dummyHead;
};

class Solution {
public:

    //Performs the operation op on x and y
    int evaluateOperation(std::basic_string<char> op, int x, int y)
    {
        if(op == "+")
            return x + y;
        else if(op =="*")
            return x*y;
        else if(op == "-")
            return x - y;
        else
            return x / y;
    }

    int evalRPN(vector<string>& tokens)
    {
        //Have two stacks, one for the operations and one for the operands
        //When we have an operation and two operands, compute the result and add it to the
        //operands stack
        Stack<int> operands(-1, nullptr);
        Stack<string> operations("*", nullptr);

        int operandsSize = 0;

        for(int i = 0; i < tokens.size(); i++)
        {
            if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/")
                operations.push(tokens[i]);
            else
                operands.push(std::stoi(tokens[i]));
            
            operandsSize++;

            if(operandsSize >= 2 && !operations.isEmpty())
            {
                int top = operands.pop();
                int next = operands.pop();
                int result = evaluateOperation(operations.pop(), next, top);
                operands.push(result);
                operandsSize--;
            }
        }

        return operands.pop();
    }
};
17300