• 백준 1918번 후위표기식 :: 마이구미
    알고리즘 풀이/스택, 큐 2017. 7. 9. 15:21
    반응형

    이번 글은 백준 알고리즘 문제 1918번 "후위표기식" 을 다뤄본다.

    자료구조 수업을 들어봤다면, 문제 제목을 보자마자, 스택을 활용하는 문제라는 걸 알 수 있다.

    먼저 이론을 이해하고 푼다면, 쉬운 문제가 된다. (참고 자료)


    문제는 중위 표기식을 후위 표기식으로 바꾸는 문제가 된다.

    중위 표기식이란, 우리가 사용하는 수식이 된다. ex) a * (b + c)

    후위 표기식이란, 컴퓨터가 사용하는 수식이 된다. ex) abc+*


    중위 표기식에서 후위 표기식으로 바꾸는 과정은 아래와 같다.


    1. 피연산자(a,b,c)는 출력한다. 
    2. 연산자는 앞 연산자(스택의 맨 위)를 살펴서 출력하거나 대기한다(스택에 넣는다, 대기 된 자료들은 나중에 대기 된 연산자가 먼저 나온다, LIFO, 스택을 이용) 
    3. 연산자의 대기(스택에 push)여부는 연산자간의 우선순위에 따른다.


    스택에는 연산자만 사용하고, 피연산자는 바로바로 출력한다.

    먼저, 스택의 자료를 위해 연산자에 우선순위를 둔다. '*', '/', '+', '-', '(', ')'


    public static int priority(char ch) { switch (ch) { case '*': case '/': return 2; case '+': case '-': return 1; case '(': case ')': return 0; } return -1; }


    스택의 top보다 다음 연산자의 우선순위가 클 경우 push 하고, 그렇지 않을 경우, pop한다.

    (우선순위가 같다면, 먼저 스택에 들어온 연산자를 먼저 내보내야하기 때문에 클 경우만 push를 한다.)

    그리고, 알다시피 괄호는 우선적으로 처리해줘야하기 때문에, 괄호가 닫히면 이전 괄호까지 pop을 해준다.


    for (int i = 0; i < len; i++) {
        int p = priority(s[i]);
        char ch = s[i];
    
        switch (ch) {
            case '+':
            case '-':
            case '*':
            case '/':
                while (!stack.isEmpty() && priority(stack.peek()) >= p) {
                    sb.append(stack.pop());
                }
                stack.push(ch);
                break;
            case '(':
                stack.push(ch);
                break;
            case ')':
                while (!stack.isEmpty() && stack.peek() != '(') {
                    sb.append(stack.pop());
                }
                stack.pop();
                break;
            default:
                sb.append(ch);
        }
    }


    마지막으로 쌓인 스택을 비워주면 끝이다.

    정답 비율에 겁 먹고 안풀고 있었는데 이론만 알고 있다면, 쉬운 문제에 속한다. 


    Github - https://github.com/hotehrud/acmicpc/blob/master/algorithm/stack/1918.java


    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
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    private void solve() {
        // http://mygumi.tistory.com/181
        char[] s = sc.readLine().toCharArray();
        int len = s.length;
     
        Stack<Character> stack = new Stack<Character>();
        StringBuilder sb = new StringBuilder();
     
        for (int i = 0; i < len; i++) {
            int p = priority(s[i]);
            char ch = s[i];
     
            switch (ch) {
                case '+':
                case '-':
                case '*':
                case '/':
                    while (!stack.isEmpty() && priority(stack.peek()) >= p) {
                        sb.append(stack.pop());
                    }
                    stack.push(ch);
                    break;
                case '(':
                    stack.push(ch);
                    break;
                case ')':
                    while (!stack.isEmpty() && stack.peek() != '(') {
                        sb.append(stack.pop());
                    }
                    stack.pop();
                    break;
                default:
                    sb.append(ch);
            }
        }
     
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
     
        System.out.println(sb.toString());
    }
     
    public static int priority(char ch) {
        switch (ch) {
            case '*':
            case '/':
                return 2;
            case '+':
            case '-':
                return 1;
            case '(':
            case ')':
                return 0;
        }
        return -1;
    }
    cs


    반응형

    댓글 2

Designed by Tistory.