[백준/자바] 1918 : 후위 표기

https://www.acmicpc.net/problem/1918

1918번: 후위 표기식

---

이 문제는 중위 표기식을 후위 표기식으로 변환하는 문제이다.

스택이나 큐를 사용하면 되겠다고 생각은 했지만 연산 순서나 괄호를 어떻게 처리해야 할지 모르겠어서 결국 여러 답변을 참고했다 😢

 

풀이에서 주요한 부분은 연산 우선순위를 정하는 함수와 기호 별 처리 조건문이다.

 

1. 연산 우선순위 함수

처음에는 괄호가 우선순위가 가장 높다고 생각했는데, 결국 괄호 내 기호들의 우선순위를 정해야 하므로

곱셈/나눗셈(*, /) -> 덧셈/뺄셈(*, -) -> 괄호순으로 우선순위를 정하였다.

 

2. 기호 별 처리 조건문

 

• 여는 괄호: 스택에 push
• 닫는 괄호: 스택의 pop이 여는 괄호가 나올 때까지 pop해 StringBuilder에 append
• 연산자: 스택의 탑에 위치한 연산자의 우선순위가 현재 연산자의 우선순위보다 크면 pop -> append

전체 풀이과정은 다음과 같다.

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

public class Boj_1918 {

   public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       StringBuilder sb = new StringBuilder();

       char[] str_arr = br.readLine().toCharArray();
       Stack<Character> stk = new Stack<Character>();

       for (char str : str_arr) {
           if (str >= 'A' && str <= 'Z')
               sb.append(str);
           else if (str == '(') { // 여는 괄호이면 그냥 push
               stk.push(str);
           } else if (str == ')') { // 여는 괄호가 나올 때까지 pop
              while (stk.peek() != '(')
                   sb.append(stk.pop());
               stk.pop(); // 여는 괄호 스택에서 빼주기
           } else {
               // 연산자 우선순위 비교
               while (!stk.isEmpty() && priority(stk.peek()) >= priority(str)) {
                   sb.append(stk.pop());
               }
               stk.push(str);
           }
       }

       while (!stk.isEmpty()) {
           sb.append(stk.pop());
       }
   
       System.out.println(sb);
   }

   public static int priority(Character str) {
       if (str == '+' || str == '-') {
           return 1;
       } else if (str == '*' || str == '/') {
           return 2;
       } else {
           return 0;
       }
   }
}