백준 1918번 후위표기식 :: 마이구미

이번 글은 백준 알고리즘 문제 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

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;
}