[LeetCode] 150. Evaluate Reverse Polish Notation

Problem

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

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

Note that division between two integers should truncate toward zero.

It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any division by zero operation.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

• 1 <= tokens.length <= 10^4
• tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

---

Solution

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        int operand1 = 0;
        int operand2 = 0;
        for (int i = 0; i < tokens.length; i++) {
            if (tokens[i].equals("+")) {
                operand1 = stack.pop();
                operand2 = stack.pop();
                stack.push(operand2 + operand1);
            } else if (tokens[i].equals("-")) {
                operand1 = stack.pop();
                operand2 = stack.pop();
                stack.push(operand2 - operand1);
            } else if (tokens[i].equals("*")) {
                operand1 = stack.pop();
                operand2 = stack.pop();
                stack.push(operand2 * operand1);
            } else if (tokens[i].equals("/")) {
                operand1 = stack.pop();
                operand2 = stack.pop();
                stack.push(operand2 / operand1);
            } else
                stack.push(Integer.valueOf(tokens[i]));
        }
        return stack.pop();
    }
}

• Below is same logic as above without duplicate expression

  class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            if (!tokens[i].equals("+") && !tokens[i].equals("-")
                && !tokens[i].equals("*") && !tokens[i].equals("/")) {
                stack.push(Integer.valueOf(tokens[i]));
            } else {
                int operand1 = stack.pop();
                int operand2 = stack.pop();
                if (tokens[i].equals("+"))
                    stack.push(operand2 + operand1);
                else if (tokens[i].equals("-"))
                    stack.push(operand2 - operand1);
                else if (tokens[i].equals("*"))
                    stack.push(operand2 * operand1);
                else if (tokens[i].equals("/"))
                    stack.push(operand2 / operand1);
            }
        }
        return stack.pop();
    }
  }
  

  Explanation

• 첫 연산은 배열에서 연산자에 해당하는 요소의 이전 두 요소가 피연산자가 되어서 계산이 수행되는데, 첫 연산자를 만나서 계산이 이루어진 후, 다음 요소가 피연산자인 경우와 연산자인 경우 총 2가지가 있다.
• 첫 연산 후 피연산자가 나오면 연산 결과를 저장해놓고, 다음 연산자를 만나서 연산을 수행하면 된다. 하지만 연산자가 나오게 되면 이전 요소들 중에서 피연산자를 찾아서 계산을 수행해야한다.
• 피연산자를 자료 구조에 저장해 놓고 연산자를 만났을 때 꺼내 연산에 사용한 후, 연산 결과를 저장해놓으면 이 연산 결과가 다시 피연산자가 되어 연산을 수행할 수 있다.
• 가장 최근의 연산 결과가 피연산자가 되어야 하므로, 자료 구조 Stack를 선언하여 피연산자를 저장하도록 한다.

  Stack<Integer> stack = new Stack<>();
  

• for반복문을 선언하여 배열 tokens의 요소를 참조하도록 한다. 요소 중 연산자를 발견하면 stack에서 피연산자를 꺼내서 연산을 수행한 후, 연산 결과가 피연산자로 사용되도록 다시 stack에 저장되도록 if조건문을 작성한다.
• 참조한 배열 tokens의 요소가 연산자가 아니라면 피연산자라는 의미가 되므로 stack에 정수로 변환 후 넣어주도록 한다.

  int operand1 = 0;
  int operand2 = 0;
  for (int i = 0; i < tokens.length; i++) {
    if (tokens[i].equals("+")) {
        operand1 = stack.pop();
        operand2 = stack.pop();
        stack.push(operand2 + operand1);
    } else if (tokens[i].equals("-")) {
        operand1 = stack.pop();
        operand2 = stack.pop();
        stack.push(operand2 - operand1);
    } else if (tokens[i].equals("*")) {
        operand1 = stack.pop();
        operand2 = stack.pop();
        stack.push(operand2 * operand1);
    } else if (tokens[i].equals("/")) {
        operand1 = stack.pop();
        operand2 = stack.pop();
        stack.push(operand2 / operand1);
    } else
        stack.push(Integer.valueOf(tokens[i]));
  }
  

• for반복문을 빠져 나오게 되면 마지막 연산 결과가 stack에 저장되게 된다. stack에 남아있는 요소를 반환한다.

  return stack.pop();