Gidhub BE Developer

LeetCode : 150. Evaluate Reverse Polish Notation

2021-02-08
goodGid
LeetCode

150. Evaluate Reverse Polish Notation

Problem

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

Example

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

[1] Code (21. 02. 08)

class Solution {
    public int evalRPN(String[] tokens) {

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

        for (int i = 0; i < tokens.length; i++) {
            if (isDigit(tokens[i])) {
                stack.push(getIntegerValue(tokens[i]));
            } else if (tokens[i].equals("+")) {
                stack.push(stack.pop() + stack.pop());
            } else if (tokens[i].equals("-")) { // [3]
                int first = stack.pop();
                int second = stack.pop();
                stack.push(second - first);
            } else if (tokens[i].equals("*")) {
                stack.push(stack.pop() * stack.pop());
            } else if (tokens[i].equals("/")) { // [3]
                int first = stack.pop();
                int second = stack.pop();
                int result = second / first;
                stack.push(result);
            }
        }
        return stack.pop();
    }

    private boolean isDigit(String s) {
        return !(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/"));
    }

    // [1]
    private Integer getIntegerValue(String s) {

        // Integer 내장 메소드
        // Integer.valueOf(s);

        // 직접 구현
        int isNegative = 1;
        if (s.charAt(0) == '-') { // [2]
            s = s.substring(1);
            isNegative = -1;
        }

        int value = 0;

        for (int i = 0; i < s.length(); i++) {
            value = (value * 10) + (s.charAt(i) - '0');
        }
        return isNegative * value;
    }
}

Check Point

  1. 1개의 String을 int 값으로 변환하는 방법

  2. getIntegerValue( )에서 음수로 들어오는 경우

  3. ’-‘와 ‘/’일 경우 적용시키는 값의 순서

  • [1] : Integer의 내장 메소드 혹은 직접 구현해서 값을 구할 수 있다.

  • [2] : 음수일 경우 substring으로 음수 자리를 없애준다.

[2] Code (23. 04. 19)

Need to Retry

// Runtime: 23 ms
// Memory Usage: 44.8 MB
// Ref : https://leetcode.com/submissions/detail/936229652
class Solution {
    public int evalRPN(String[] tokens) {

        String regex = "\\d+";
        Stack<String> st = new Stack<>();

        for (String s : tokens) {
            if (s.matches(regex)) {
                st.add(s);
            } else if (s.startsWith("-") && s.substring(1, s.length()).matches(regex)) {
                st.add(s);
            } else {
                int val1 = Integer.parseInt(st.pop());
                int val2 = Integer.parseInt(st.pop());
                switch (s) {
                    case "+":
                        st.add(String.valueOf(val2 + val1));
                        break;
                    case "-":
                        st.add(String.valueOf(val2 - val1));
                        break;
                    case "*":
                        st.add(String.valueOf(val2 * val1));
                        break;
                    case "/":
                        st.add(String.valueOf(val2 / val1));
                        break;
                    default:
                        break;
                }
            }
        }
        return Integer.parseInt(st.pop());
    }
}

Review

  • 처음 풀었을 때보다는 코드가 간결해졌다.

Reference

Index