Back to solutions

Evaluate Reverse Polish Notation

MediumStack & Queue

Evaluate an arithmetic expression given in Reverse Polish (postfix) notation.

Open problem
Constraints
  • 1 <= tokens.length <= 10^4
  • Operators are + - * /

Operand stack

Time O(n)Space O(n)

Push numbers onto a stack. On an operator, pop the two operands, apply the operation, and push the result. The final stack value is the answer.

#include <bits/stdc++.h>
using namespace std;

int evalRPN(vector<string>& tokens) {
    stack<long long> st;
    for (string& t : tokens) {
        if (t == "+" || t == "-" || t == "*" || t == "/") {
            long long b = st.top(); st.pop();
            long long a = st.top(); st.pop();
            if (t == "+") st.push(a + b);
            else if (t == "-") st.push(a - b);
            else if (t == "*") st.push(a * b);
            else st.push(a / b);
        } else st.push(stoll(t));
    }
    return st.top();
}