[015] 1918.후위 표기식

https://www.acmicpc.net/problem/1918

1918번: 후위 표기식

---

 

이거 전에 푼 적이 있다. 언젠지 생각하고 있으니까 처음 파이썬 배울 때 과제가 이거였다.

파이썬으로 했을 때도 굉장히... 굉장히 싫었는데 자바로 하려니까 더 안 된다. 우선, 풀이 과정 자체는 다음과 같다

 

1. 문자일 경우 바로 문자열에 추가한다

2. 여는 괄호가 나올 경우, 스택에 넣는다

3. 닫는 괄호가 나올 경우, 스택을 확인하여 괄호 전까지의 연산자를 문자열에 넣는다

4. 연산자일 경우, 스택에 있는 것보다 선순위 연산자나 동순위 연산자일 경우 빼고, 아닐 경우 스택에 넣는다

5. 모든 것이 출력되었을 때, 스택에 남아있는 것 중 괄호를 제외하고 문자열에 추가한다

 

이것을 쉽게 표로 정리해보면

 

이정도인데 이런 식으로 저장과 확인 그리고 출력을 반복하면 된다

근데 이제... 문제는... 이게 길어지니까 문제가 생기는 거지

 

    public void q1918(){
        Scanner sc = new Scanner(System.in);
        Deque<String> deq = new ArrayDeque<>();
        String me = sc.nextLine();
        String temp = "";
        StringBuilder sb = new StringBuilder();
        int ascii = 0;
        int deqAscii = 0;

        String[] arr = new String[me.length()];
        for(int i = 0; i < me.length(); i++){
            temp = String.valueOf(me.charAt(i));
            ascii = (int)me.charAt(i);


            // 문자일 경우
            if(ascii >= 65){
                sb.append(temp);

            // ( < 이 괄호면 스택에 넣고
            }else if(ascii == 40){
                deq.add(temp);
           // ) < 이 괄호면 전에 ( 괄호가 나왔던 곳까지 스택에서 출력해서 sb에 넣기
            }else if(ascii == 41){
                while(!deq.isEmpty()){
                    deqAscii = (int)deq.peek().charAt(0);
                    System.out.println("peek 확인 : " + deq.peek());
                    if(deqAscii == 40 ){
                        deq.removeFirst();
                        break;
                    }
                    sb.append(deq.removeFirst());
                }
            // 괄호를 제외한 연산자일 경우 스택에 쌓음, but 이전에 들어있는 연산자보다 우선순위가 높거나 같을 경우 빼기
            }else{
                System.out.println("현재 temp : " + temp);
                if(!deq.isEmpty()){
                    deqAscii = (int)deq.peek().charAt(0);
                    while(!deq.isEmpty() && ck(deqAscii) >= ck(ascii)){
                        sb.append(deq.pop());

                    }
                }
                deq.add(temp);

            }
        }
        // 마지막에 쌓인 것 처리하기
        while(!deq.isEmpty()){
            sb.append(deq.pop());
        }
           System.out.println(sb);
    }
    static int ck(int item){
        if(item == 40) return 0;
        else if(item == 43 || item == 45) return 1;
        else return 2;
    }

 

처음 풀이는 다음과 같다

그냥 단순하게 아스키 코드로 비교해야지 하는 생각을 했었는데, 우선순위가 계속 엉켜서 답이 제대로 추출되지도 않고, 불필요한 로직이 계속해서 추가되다 보니까(올바르게 다시 해야겠다고 누빔을 하고 하고 하고 하고 하다보니 이제 더 엉망이 되는 그러한) 갈수록 답이 없어지기 시작했다. 

 

어떻게 하지 하고 고민하다가 아스키 코드를 없애고 로직을 단순화하는 과정부터 다시 풀이를 시작했다

문제가 되는 부분은 괄호 제외 연산자인데, 로직을 수행하면서 명확하게 되지를 않았다 (temp와 deqascii가 계속해서 꼬였다 왜인지는 모르겠는데 연산 우선순위에서 계속 문제가 생긴 모양이다...) 로직을 변경하면서 조금 더 쉽게 보이도록 했고, 다중연산을 시행하면서 코드 길이를 최대한 줄였다.

 

    public void q1918(){
        Scanner sc = new Scanner(System.in);
        Deque<String> deq = new ArrayDeque<>();
        String me = sc.nextLine();
        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < me.length(); i++){
            char temp = me.charAt(i);

            // 문자일 경우
            if(Character.isLetter(temp)){
                sb.append(temp);

            // ( < 이 괄호면 스택에 넣고
            }else if(temp == '(') {
                deq.addFirst(String.valueOf(temp));

                // ) < 이 괄호면 전에 ( 괄호가 나왔던 곳까지 스택에서 출력해서 sb에 넣기
            }else if(temp == ')'){
                while(!deq.isEmpty() && deq.peek().charAt(0) != '('){
                    sb.append(deq.pop());
                }
                deq.pop(); // '(' 제거, 괄호 내부 연산자 처리 후 '(' 제거

            // 괄호를 제외한 연산자일 경우 스택에 쌓음, but 이전에 들어있는 연산자보다 우선순위가 높거나 같을 경우 빼기
            }else{
                while(!deq.isEmpty() && ck(deq.peek().charAt(0)) >= ck(temp)){
                    sb.append(deq.pop());
                }
                deq.addFirst(String.valueOf(temp));
            }
        }
        // 마지막에 쌓인 것 처리하기
        while(!deq.isEmpty()){
            sb.append(deq.pop());
        }
           System.out.println(sb);
    }
    static int ck(char item){
        if(item == '(') return 0;
        else if(item == '+' || item == '-') return 1;
        else return 2; // '*', '/'
    }
}

 

 

이걸 또 하게 될줄은 몰랐음