백준 1918 Java: 중위 표기식을 후위 표기식으로 바꾸는 Stack 규칙

백준 1918은 중위 표기식의 operand는 바로 출력하고, operator는 stack에서 우선순위와 괄호를 처리하는 문제다. 예전에 비슷한 문제를 풀었어도 오랜만에 다시 보니 시간이 걸렸다. 그때 남긴 “알고리즘은 꾸준함이 중요하다”는 메모와 함께, 조건문을 줄인 현재 풀이를 정리한다.

문제를 바꾸어 읽기

중위 표기식은 operator가 operand 사이에 온다.

A*(B+C)

후위 표기식은 operator를 두 operand 뒤에 둔다.

ABC+*

후위 표기식에는 계산 순서를 위한 괄호가 필요 없다. 입력은 대문자 operand가 한 번씩 나오고 +, -, *, /, (, )만 사용하므로 unary minus나 exponent의 associativity는 고려하지 않는다.

Stack에 무엇을 남길까

output에는 순서가 확정된 token만 넣고, stack에는 아직 출력 시점을 결정하지 못한 operator와 여는 괄호를 둔다.

Operand

대문자이면 즉시 output에 붙인다.

여는 괄호 (

stack에 넣는다. 괄호 안 operator가 밖의 operator와 섞이지 않게 하는 경계다.

닫는 괄호 )

stack top에서 (를 만날 때까지 operator를 output으로 옮긴 뒤 (를 버린다. 괄호 자체는 후위 표기식에 출력하지 않는다.

Operator

stack top이 (가 아니고, top의 우선순위가 현재 operator보다 높거나 같으면 pop한다. 문제의 네 operator는 모두 left-associative라 같은 우선순위도 먼저 들어온 것을 출력한다. 그 뒤 현재 operator를 push한다.

입력을 모두 읽은 뒤 stack에 남은 operator를 차례로 출력한다.

Java 풀이

java.util.Stack보다 Deque 구현인 ArrayDeque를 stack으로 사용했다. 반복 문자열 연결 대신 StringBuilder를 써서 output을 만든다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(
            new InputStreamReader(System.in)
        );
        String expression = reader.readLine();

        StringBuilder postfix = new StringBuilder(expression.length());
        Deque<Character> operators = new ArrayDeque<>();

        for (int index = 0; index < expression.length(); index++) {
            char token = expression.charAt(index);

            if ('A' <= token && token <= 'Z') {
                postfix.append(token);
                continue;
            }

            if (token == '(') {
                operators.push(token);
                continue;
            }

            if (token == ')') {
                while (operators.peek() != '(') {
                    postfix.append(operators.pop());
                }
                operators.pop();
                continue;
            }

            while (!operators.isEmpty()
                && operators.peek() != '('
                && precedence(operators.peek()) >= precedence(token)) {
                postfix.append(operators.pop());
            }
            operators.push(token);
        }

        while (!operators.isEmpty()) {
            postfix.append(operators.pop());
        }

        System.out.println(postfix);
    }

    private static int precedence(char operator) {
        return switch (operator) {
            case '*', '/' -> 2;
            case '+', '-' -> 1;
            default -> 0;
        };
    }
}

A+B*C-D/E를 따라가 보기

Token	Output	Stack
A	A
+	A	+
B	AB	+
*	AB	* +
C	ABC	* +
-	ABC*+	-
D	ABC*+D	-
/	ABC*+D	/ -
E	ABC*+DE	/ -
끝	ABC*+DE/-

여기서 stack 표기는 왼쪽이 top이다. -를 만났을 때 *와 +를 모두 꺼내는 이유는 두 operator의 우선순위가 현재 -보다 높거나 같기 때문이다.

원래 풀이에서 단순화한 부분

처음 작성한 code는 stack이 비었는지와 우선순위가 높은지를 여러 branch로 나눴고, 괄호에도 임의의 priority 값을 줬다. 괄호는 일반 operator가 아니라 pop의 경계이므로 priority 함수에 넣지 않는 편이 역할이 분명하다.

또한 answer += value는 매번 새 문자열을 만들 수 있다. 입력 길이가 이 문제에서는 작더라도 반복 누적에는 StringBuilder가 의도를 더 잘 드러낸다.

복잡도와 경계 조건

각 token은 stack에 최대 한 번 들어가고 한 번 나온다.

• 시간 복잡도: O(N)
• 공간 복잡도: O(N)

확인할 expression은 다음과 같다.

A+B      -> AB+
A+B*C    -> ABC*+
A*(B+C)  -> ABC+*
A+B*C-D/E -> ABC*+DE/-

문제는 올바른 식만 준다. 일반 parser를 만든다면 mismatched parenthesis, whitespace, multi-character operand, unary operator와 right-associative operator까지 별도 처리해야 한다.

다른 stack·queue 문제는 큐 2 Java 풀이, 전체 풀이 목록은 알고리즘·문제풀이에서 이어서 볼 수 있다.

참고 자료

• 백준 1918 후위 표기식
• Java ArrayDeque API