In this problem, we are going to write a program which calculates the value of Reverse Polish notation.
Here are some quick thoughts on how to solve this:
- If the token is an operator, we gonna use the value of the two previous numbers for the calculation.
- And since we want to get the latest elements that we have, Stack will be helpful.
Using Stack
For example, we have a notation: ["4","13","5","/","+"].
Since the first 3 elements are integer, the stack will push all 3 of them in: stack = ["4", "13", "5"].
Then, the next token is: "/", which is an operator. We pop the two latest element in the stack, which is "13", and "5" to conduct the division, stack = ["4"]. The result is 2 since we just take the int value. We push that 2 back in the stack. stack = ["4", "2"].
Lastly, "+" is an operator token, we pop "4" and "2" from the stack to conduct the addition, stack = []. The result is "6". Push "6" back into the stack, stack = ["6"].
Since there is no more token to visit, the final result is returned, which is 6.
With this example, we have the algorithm:
- Initialize an empty Stack.
- Traverse through each token in the
tokenslist. - If a token is not an operator, add it to the stack.
- If the token is an operator: pop the two latest element in the stack, compute based on the operator and push back the result
- Return the last element in stack after visiting all the tokens.
Here is the solution in Java
class Solution {
public boolean contains(String[] operators, String token) {
for (String op: operators) {
if (op.equals(token)) {
return true;
}
}
return false;
}
public int evalRPN(String[] tokens) {
/**
Reverse polish notation:
3 4 + => 3 + 4
3 4 x 5 6 x + => 3 * 4 + 5 * 6
- When we hit an operator, pop out the latest 2 operands and calculate the result
Then put back the result into the stack for later calculation
- Return the last elements in the stack which is the final result
*/
String[] operators = {"+", "-", "*", "/"};
Stack<String> stack = new Stack<>();
for (String t: tokens) {
// System.out.println(stack.toString());
if (!contains(operators, t)) {
stack.push(t);
} else {
int second = Integer.parseInt(stack.pop());
int first = Integer.parseInt(stack.pop());
int result;
if (t.equals("+")) {
result = first + second;
} else if (t.equals("-")) {
result = first - second;
} else if (t.equals("*")) {
result = first * second;
} else {
result = first / second;
}
stack.push(String.valueOf(result));
}
}
return Integer.parseInt(stack.pop());
}
}
Top comments (0)