150.evaluate-reverse-polish-notation.md

150. Evaluate Reverse Polish Notation

Stack

We always evaluate the result of the last two operands with the operator A, B, opeator, that is A operator B. We can use a stack to store the operands and evaluate the result.

(A) (B) operator
A = (a) (b) operator or `a` // A could be a number or a result
B = (c) (d) operator or `b`

// Example 1
(1 2 +) (2 3 *) -
(3) (6) -
 3 - 6 = -3

// Example 2
(3) (2 3 *) +
3 + 6 = 9

fun evalRPN(tokens: Array<String>): Int {
    val stack = Stack<String>()
    for (t in tokens) {
        if (isOperator(t)) {
            val second = stack.pop().toInt()
            val first = stack.pop().toInt()
            val result = when (t) {
                "+" -> first + second
                "-" -> first - second
                "*" -> first * second
                "/" -> first / second
                else -> throw Exception("Invalid")
            }
            stack.push(result.toString())
        } else {
            stack.push(t)
        }
    }
    return stack.peek().toInt()
}

private fun isOperator(c: String): Boolean {
    return c == "+" || c == "-" || c == "*" || c == "/"
}

* **Time Complexity**: `O(n)`, where `n` is the length of the `tokens`.
* **Space Complexity**: `O(n)`.