Description:
Since the number is last in first out, So I employ a stack to import numbers from the String array in sequence. If the element we read is an operator instead of a number, not import it. Pop from the stack two times, save them separately, like to be int num2 (first) and int num1, then do the num1 (operator) num2 and push the result back to the stack.
T: O(n)
S: O(n)
There's a better solution which has S: O(1). Need to apply recursion method.
Code:
代碼寫的丑 it's kind of ugly so far.
`java
class Solution {
public int evalRPN(String[] tokens) {
Stack<String> stack = new Stack<>();
int index = 0;
while (index < tokens.length) {
int num1 = 0;
int num2 = 0;
switch (tokens[index]) {
case "+":
num2 = Integer.parseInt(stack.pop());
num1 = Integer.parseInt(stack.pop());
stack.push(Integer.toString(num1 + num2));
break;
case "-":
num2 = Integer.parseInt(stack.pop());
num1 = Integer.parseInt(stack.pop());
stack.push(Integer.toString(num1 - num2));
break;
case "*":
num2 = Integer.parseInt(stack.pop());
num1 = Integer.parseInt(stack.pop());
stack.push(Integer.toString(num1 * num2));
break;
case "/":
num2 = Integer.parseInt(stack.pop());
num1 = Integer.parseInt(stack.pop());
stack.push(Integer.toString(num1 / num2));
break;
default:
stack.push(tokens[index]);
break;
}
index++;
}
return Integer.parseInt(stack.pop());
}
}
`
