[LeetCode] 150. Evaluate Reverse Polish Notation

Posted on | In

Problem

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Note:

  • Division between two integers should truncate toward zero.
  • The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation.

Example 1:

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

Example 2:

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

Example 3:

1
2
3
4
5
6
7
8
9
10
Input: ["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

Explanation 1

  1. We can use a stack to solve this problem. Iterating each element of the array, if the element is a number, then push it to the stack. Else if it’s operator, then we pop two numbers from the stack and calculate their result, then push the result to stack. At the end, there’s only one element in the stack, which is the result value.

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int evalRPN(String[] tokens) {
        if (tokens.length == 1) return Integer.valueOf(tokens[0]);
        Stack<Integer> st = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            if (!tokens[i].equals("+") && !tokens[i].equals("-") &&
                !tokens[i].equals("*") && !tokens[i].equals("/")) {
                st.push(Integer.valueOf(tokens[i]));
            } else {
                int num1 = st.pop();
                int num2 = st.pop();
                if (tokens[i].equals("+")) st.push(num2 + num1);
                if (tokens[i].equals("-")) st.push(num2 - num1);
                if (tokens[i].equals("*")) st.push(num2 * num1);
                if (tokens[i].equals("/")) st.push(num2 / num1);
            }
        }

        return st.pop();
    }
}

Explanation 2:

  1. We can also use recursivly method to solve this problem. We know that operator must be the end of the array, and before the operator, there are should be two numbers. For example, [1,2,+]. Before the operator, it can be another operator, for example, [1, 8, 6, -, +]. Eventually, before the first operator, there are must be two numbers. When hitting the first operator, it will return a number.

  2. In the recursion function, when the last operator is not operator, we can simply return that number. When the last element is operator, then we need to recursivly call the recursion function two times with the end index moving toward the beginning by 1 in each call. After these two functions return the number, then we can calculate it base on the operator and return the result.

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int endInd;

    public int helper(String[] tokens) {
        endInd -= 1;
        String temp = tokens[endInd];

        if (!tokens[endInd].equals("+") && !tokens[endInd].equals("-") &&
           !tokens[endInd].equals("*") && !tokens[endInd].equals("/")) {
            return Integer.valueOf(tokens[endInd]);
        } else {
            int num1 = helper(tokens);
            int num2 = helper(tokens);
            if (temp.equals("+")) return num2 + num1;
            if (temp.equals("-")) return num2 - num1;
            if (temp.equals("*")) return num2 * num1;
            return num2 / num1;
        }
    }

    public int evalRPN(String[] tokens) {
        if (tokens.length == 1) return Integer.valueOf(tokens[0]);
        endInd = tokens.length;
        return helper(tokens);
    }
}