Leetcode 150 - Evaluate Reverse Polish Notation

Prompt: Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, and /. Each operand may be an integer or another expression.

Example:

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Input: tokens = ["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: This can be solved with a stack. We can pop from the left of the tokens list. If the element popped is a number, then we just append it to the stack. If the ele ment popped is an operand, then we can pop two numbers from the stack, perform the operation on the two numbers and append the result to the stack. The runtime for this solution is O(n) since it just loops through all the elements in tokens.