[leetcode -Java] 150. Evaluate Reverse Polish Notation

1. 문제

---

*- 입력받은 String배열 tokens을 역폴란드 표기법(후위표기법)으로 정해진 수를 만들어라 *

2. 의사 코드

---

입력받은 배열 tokens의 연산자 or 피연산자를 확인하여 서로 다른 Stack에 넣고 연산자(+,-,*,/)가 나왔을 때 숫자가 담긴 Stack의 값을 꺼내어 연산을 하면 될 것 같았다.

1. tokens의 요소가 숫자인지 확인
    boolean 타입의 메서드 생성

2. tokens의 요소가 연산자인지 확인
    boolean 타입의 메서드 생성

3. 숫자가 담길 Stack과 연산자가 담길 Stack 구분 및 필요한 변수 선언
    int sum = 0; // 결과 변수
    String stringTokens = Arrays.toString(tokens); // 배열의 모든 요소 확인하기 위해 문자 변환
    Stack<Integer> stack = new Stack<>(); // 숫자가 담길 Stack
    Stack<Character> operStack = new Stack<>(); // 연산자가 담길 Stack

4. 반복문을 활용하여 문자열로 변경한 tokens의 각 요소 확인
    for(int i=0; i<tokens.length(); i++) {
        if 숫자면 ? stack에 추가
        else if 연산자면 ? operStack에 추가

        if 연산자(+,-,*,/)가 나오면 ? 숫자가 담긴 Stack의 요소들 각각 연산하여 sum 반환
    }

3. 시도

---

class Solution {
    public boolean isNum(char token) {
        return token >= '0' && token <= '9';
    }
    public boolean isOperator(char token) {
        return token == '+' || token == '-' || token == '*' || token == '/';
    }

    public int evalRPN(String[] tokens) {
        int sum = 0;
        String stringTokens = Arrays.toString(tokens);
        Stack<Integer> stack = new Stack<>();
        Stack<Character> operStack = new Stack<>();


        for(int i=0; i<stringTokens.length(); i++) {
            // 피연산자 넣는 용도(숫자)
            System.out.println("charAt(i) = " + stringTokens.charAt(i));
            if(isNum(stringTokens.charAt(i))) {
                stack.add(stringTokens.charAt(i));
            } else if(isOperator(stringTokens.charAt(i))) {
                operStack.add(stringTokens.charAt(i));
            }

            if(isOperator(stringTokens.charAt(i))) {
                if(stringTokens.charAt(i) == '+') {
                    System.out.println("stack = " + stack);
                    System.out.println("operStack = " + operStack);
                    for(int j=0; j<stack.size(); j++) {
                        System.out.println("size = " + stack.size());
                        System.out.println("peek = " + stack.peek());

                        int pop = (int)stack.pop();
                        sum += pop;

                        System.out.println("pop = " + pop);
                        System.out.println("+ = " + sum);
                    }
                } 
                   // 일단 위의 + 연산부터 확인 하고 아래의 나머지 연산을 진행하려 주석 처리

                // else if(stringTokens.charAt(i) == '-') {
                //     for(int j=0; j<stack.size(); j++) {
                //         sum -= (int)(stack.get(i));
                //         System.out.println("- = " + sum);
                //     }
                // } else if(stringTokens.charAt(i) == '*') {
                //     for(int j=0; j<stack.size(); j++) {
                //         sum *= stack.get(i);
                //         System.out.println("* = " + sum);
                //     }
                // } else if(stringTokens.charAt(i) == '/') {
                //     for(int j=0; j<stack.size(); j++) {
                //         sum /= stack.get(i);
                //         System.out.println("/ = " + sum);
                //     }
                // }
            }
        } // for
        System.out.println("sum = " + sum);
        System.out.println("stack = " + stack);
        System.out.println("operStack = " + operStack);

        return sum;
    }
}

일단 의도한대로 숫자Stack과 연산자Stack은 잘 나뉘었다. 그러나 숫자를 저장한 Stack은 Character로 연산을 할 때 아스키코드로 반환되는 것이 문제였다. 이후에 코드를 수정하며 굳이 연산자와 피연산자를 따로 배열에 저장할 필요가 있을까? 라는 생각이 들었고, 단순히 다음 값이 연산자인지만 확인하면 될 것이라 생각했다. 아래는 수정해본 코드이다.

class Solution {
        public boolean isNum(char token) {
            return token >= '0' && token <= '9';
        }
        public boolean isOperator(char token) {
            return token == '+' || token == '-' || token == '*' || token == '/';
        }

        public int evalRPN(String[] tokens) {
            int sum = 0;
            Stack<Integer> stack = new Stack<>();

            for(String token : tokens) {
                // System.out.println("1 token.charAt(0) = " + token.charAt(0));
                if(isNum(token.charAt(0))) {
                    stack.push(Integer.parseInt(token));
                    // System.out.println("stack = " + stack);
                    // System.out.println("2 token.charAt(0) = " + token.charAt(0));
                } else if(isOperator(token.charAt(0))) {
                    int a = stack.pop();
                    int b = stack.pop();
                    // System.out.println("token = " + token);
                    if(token.equals("+")) {
                        stack.push(a+b);
                        // System.out.println("+ stack = " + stack);
                    } else if(token.equals("-")) {
                        stack.push(a-b);
                        // System.out.println("- stack = " + stack);
                    } else if(token.equals("*")) {
                        stack.push(a*b);
                        // System.out.println("* stack = " + stack);
                    } else if(token.equals("/")) {
                        stack.push(a/b);
                        // System.out.println("/ stack = " + stack);
                    }
                }
            } // for
            // System.out.println("sum = " + sum);
            // System.out.println("stack = " + stack);

            return stack.peek();
        }
    }

첫 테스트 케이스는 성공했지만 여러 숫자가 연속해서 들어올 때 처리가 안되는 중이었고 Stack이 비었는데도 계속해서 pop을 하는 EmptyStackException 에러도 발생했다. else if 보다 switch를 사용하면 가독성을 높일 수 있을 것 같았고 요소가 숫자인지 확인하는 메서드 또한 matches함수를 이용하면 쉽게 해결될 것으로 보였다. 아래는 최종 코드이다.

class Solution {
        public boolean isOperator(String token) {
            return token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/");
        }

        public int evalRPN(String[] tokens) {
            Stack<Integer> stack = new Stack<>();

        for (String token : tokens) {
            // System.out.println("token = " + token);
            if (token.matches("-?\\d+")) {
                stack.push(Integer.parseInt(token));
                // System.out.println("stack = " + stack);
            } else if (isOperator(token)) {
                int b = stack.pop();
                int a = stack.pop();

                switch (token) {
                    case "+":
                        stack.push(a + b);
                        // System.out.println("+ stack = " + stack);
                        break;
                    case "-":
                        stack.push(a - b);
                        // System.out.println("- stack = " + stack);
                        break;
                    case "*":
                        stack.push(a * b);
                        // System.out.println("* stack = " + stack);
                        break;
                    case "/":
                        stack.push(a / b);
                        // System.out.println("/ stack = " + stack);
                        break;
                }
            }
        }

        return stack.peek();
        }
    }