[백준] 1918번 후위 표기식 (Java)

1918 후위 표기식

 

1. 문제 분석

---

• 연산자의 우선순위를 생각해야 하는 문제입니다.
• 주의해야 할 점은 A + B + C의 경우에는 앞에 있는 +가 우선순위가 더 높기 때문에 ABC++가 아닌 (A + B) + C로 묶어서 AB+C+가 나와야 합니다.
• 그리고 추가로 괄호로 묶여서 제공되는 연산자의 경우에는 가장 우선순위가 높기 때문에 가장 먼저 처리해줘야 합니다.
• 알파벳에 해당하는 (A ~ Z)는 바로 문자열에 추가하고, 연산자(+, -, *, /)는 Stack에 저장해야 합니다.

 

 

 

2. 핵심 아이디어

---

• Stack에는 연산자 들이 저장됩니다. 즉 먼저 들어온 연산자들은 아래쪽에 쌓이게 됩니다.
• 첫 번째 아이디어는 "("가 스택에 들어왔을 때입니다.
  
  
  • "("는 일단 스택에 넣어줍니다. 그다음 연산자를 받아주고, 닫는 괄호 ")"가 들어왔을 때, 괄호 내부에 있는 연산자를 뽑아주는 작업을 해야 합니다.
  • 그 이유는 괄호 안에 있는 연산자가 어떤 연산자인지 상관없이 우선순위가 높기 때문입니다.
  • 이때는 while에 조건을 넣어서 "("가 나올 때까지 pop을 해서 뽑아내서 정답 문자열 뒤에 붙여줍니다. 이때 "("는 정답에 포함되면 안 됩니다.
    
    
• 두 번째 아이디어는 이전에 스택에 들어온 연산자 중에서 나보다 우선순위가 높은 연산자가 있는지 확인해서 추출해야 합니다.
  
  
  • 후위 표기식에서는 알파벳 뒤에는 우선순위가 높은 순서로 연산자가 붙습니다.
  • A + B * C 라면 우선순위가 높은 순서로 ABC*+ 이렇게 붙게 됩니다.
  • 그래서 이미 스택에 들어온 연산자들 중에서 내가 현재 가지고 있는 연산자 보다 높은 우선순위가 존재하면 안 됩니다.
    
    
• 세 번째 아이디어는 수식의 모든 순회를 끝냈을 때, Stack에 남아있는 연산자들을 순서대로 추출해서 정답 문자열에 더해줘야 합니다.

 

 

 

3. 코드 작성

---

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String notation = br.readLine();
        Stack<Character> operator = new Stack<>();
        StringBuilder builder = new StringBuilder();

        for (int i = 0; i < notation.length(); i++) {
            char value = notation.charAt(i);
            if (value >= 'A' && value <= 'Z') {
                builder.append(value);
            } else if (value == '(') {
                operator.add(value);
            } else if (value == ')') {
                // 닫는 괄호가 나오면 여는 괄호가 나올 때까지 빼서 연산자만 추출한다. (괄호안에 연산자가 우선순위가 있기 떄문에)
                while (!operator.isEmpty()) {
                    char popVal = operator.pop();
                    if (popVal == '(') {
                        break;
                    }
                    builder.append(popVal);
                }
            } else {
                // 괄호가 아닌 경우에는 이전 연산자가 현재 연산자보다 우선순위가 높은지 확인 후 추출
                while (!operator.isEmpty() && checkPriority(operator.peek(), value)) {
                    builder.append(operator.pop());
                }
                operator.add(value);
            }
        }
        // 남아있을 수 있는 부분이 있어서 나머지 모두 추출해서 뒤에 붙여줌
        while (!operator.isEmpty()) {
            builder.append(operator.pop());
        }
        System.out.println(builder);
    }

    public static boolean checkPriority(char peekVal, char val) {
        int peekValWeight = setWeight(peekVal);
        int valWeight = setWeight(val);
        // 같은 순위의 연산자라면 먼저 나온 것이 우선순위가 크기 때문에 등호가 필수
        return peekValWeight >= valWeight;
    }

    public static int setWeight(char val) {
        if (val == '(') return 0;
        return val == '+' || val == '-' ? 1 : 2;
    }
}