백준 1918번 [후위 표기식](Java) -yes6686- 티스토리

백준 문제 풀이: 1918 [후위 표기식]

---

문제 링크: https://www.acmicpc.net/problem/1918

문제 설명:

중위 표기법으로 표현된 수식을 후위 표기법으로 변환하는 문제입니다. 연산자는 +, -, *, /로 구성되며, 괄호를 사용할 수 있습니다. 입력으로 주어진 수식을 변환한 후 출력합니다.

입력:

• 한 줄로 이루어진 중위 표기법의 수식이 주어집니다. 수식은 알파벳 대문자(A-Z)와 연산자(+,-,*,/) 및 괄호로 구성됩니다. (1 ≤ 길이 ≤ 100)

출력:

• 후위 표기법으로 변환된 수식을 출력합니다.

---

문제 해결 코드

import java.util.Stack;
import java.util.Scanner;

public class Main {
    private static final String OPERATORS = "+-*/()";

    // 연산자의 우선순위를 반환하는 함수
    public static int getPriority(char operator) {
        switch (operator) {
            case '(':
            case ')':
                return 0;
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
                return 2;
            default:
                return -1;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String infix = scanner.next(); // 중위 표기법 입력
        Stack operatorStack = new Stack<>();
        StringBuilder postfix = new StringBuilder();

        for (int i = 0; i < infix.length(); i++) {
            char token = infix.charAt(i);

            if (Character.isAlphabetic(token)) { // 피연산자일 경우 출력
                postfix.append(token);
            } else if (token == '(') { // 왼쪽 괄호는 스택에 추가
                operatorStack.push(token);
            } else if (token == ')') { // 오른쪽 괄호는 왼쪽 괄호까지 연산자 스택에서 제거
                while (!operatorStack.isEmpty() && operatorStack.peek() != '(') {
                    postfix.append(operatorStack.pop());
                }
                operatorStack.pop(); // 왼쪽 괄호 제거
            } else { // 연산자일 경우
                while (!operatorStack.isEmpty() && getPriority(operatorStack.peek()) >= getPriority(token)) {
                    postfix.append(operatorStack.pop());
                }
                operatorStack.push(token);
            }
        }

        // 남아 있는 연산자를 모두 출력
        while (!operatorStack.isEmpty()) {
            postfix.append(operatorStack.pop());
        }

        System.out.println(postfix.toString()); // 후위 표기식 출력
    }
}

예제

입력:
A*(B+C)

출력:
ABC+*

입력:
A+B*C

출력:
ABC*+

---

코드 설명

• 스택 활용: 연산자와 괄호는 스택에 저장하여 후위 표기법으로 변환합니다.
• 연산자 우선순위: *, /는 +, -보다 높은 우선순위를 가집니다.
• 괄호 처리: 오른쪽 괄호 )를 만나면 왼쪽 괄호 (까지 스택에서 꺼내어 후위 표기법에 추가합니다.

시간 복잡도

• 수식의 길이를 n이라 할 때, 각 문자에 대해 최대 O(n)의 연산을 수행하므로 전체 시간 복잡도는 O(n)입니다.

---

결과

코드는 주어진 중위 표기법을 후위 표기법으로 정확히 변환합니다. 입력 수식의 길이가 최대 100이므로, O(n)의 시간 복잡도로 충분히 효율적입니다.

다른 테스트 사례나 개선 사항이 있다면 댓글로 공유 부탁드립니다!