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

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

1918번: 후위 표기식

 

 

 

 

 

 

 

 

---

 

풀이

문자열에 대해서 for문을 돌면서,

1) 문자가 오는 경우: 문자는 입력 순서 그대로 문자열에 넣어주면 됩니다.

2) 연산자가 오는 경우: 연산자는 기본적으로 스택에 저장해두었다가, 필요한 시기가 오면 스택에서 꺼내 문자열에 붙입니다.

 1. 덧셈, 뺄셈이 오는 경우 - 이전에 있는 덧셈, 뺄셈, 곱셈, 나눗셈은 현재 연산자보다 먼저 계산되어야 합니다. 스택에 저장한 연산을 꺼내 문자열에 붙여줍니다.

 2. 곱셈, 나눗셈이 오는 경우 - 이전에 있는 곱셈, 나눗셈은 현재 연산자보다 먼저 계산되어야 하므로, 스택에 저장된 곱셈, 나눗셈 연산을 꺼내 문자열에 붙여줍니다.

3) 괄호 처리

 여는 괄호는 그냥 그대로 연산자를 저장하는 스택에 넣습니다.

 닫는 괄호가 오는 경우, 스택에서 여는 괄호를 만날 때까지 연산자를 꺼내어 문자열에 붙여주다가, 여는 괄호를 만나면 해당 원스를 스택에서 제거하고, 문자열에 붙이지 않습니다(==괄호 안의 잔여 연산을 모두 처리하는 과정).

 

예전에 이 문제를 스쳐지나가면서 봤을 때는 아이디어가 생각도 안 났는데, 다시보니 풀이가 바로 보입니다. 늘긴 늘었나 봅니다:)

저는 처음에, 이 문제를 '괄호를 만나면 해당 괄호안의 연산을 재귀적으로 처리해주는 방법'으로 풀었었는데, 이 경우, naive하게 구현하면 worst case O(N^2) 시간복잡도를 가지기에 좋은 풀이는 아닙니다. 문제에서는 N이 최대 100이기에 별 상관이 없긴 합니다만, N이 100000이 되면 바로 시간초과가 뜰 수 있습니다.

 

코드

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 str = br.readLine();
        String ans = postfix(str);
        System.out.println(ans);
    }
 
    static String postfix(String str) {
        StringBuilder sb = new StringBuilder();
        Stack<Character> opers = new Stack<>();
 
        for (int i = 0; i < str.length(); i++) {
            char cur = str.charAt(i);
            // 알파벳일 경우: 정답 문자열에 넣어준다.
            if (cur >= 'A' && cur <= 'Z') {
                sb.append(cur);
            }
            // 연산자일 경우: 우선순위에 따라 처리
            else if (cur != '(' && cur != ')') {
                while (!opers.isEmpty() && priority(opers.peek()) >= priority(cur)) {
                    sb.append(opers.pop());
                }
                opers.add(cur);
            }
            // 여는 괄호일 경우: 그냥 넣어주기
            else if (cur == '(') {
                opers.add(cur);
            }
            // 닫는 괄호일 경우: 여는 괄호를 만나기 전까지 남은 연산자 문자열에 붙이기
            else {
                while (opers.peek() != '(') {
                    sb.append(opers.pop());
                }
                opers.pop(); // 괄호 제거
            }
        }
        // 남은 연산자를 문자열 뒤에 붙이기
        while (!opers.isEmpty()) {
            sb.append(opers.pop());
        }
        return sb.toString();
    }
    
    static int priority(char c) {
        if (c == '*' || c == '/') return 2;
        else if (c == '+' || c == '-') return 1;
        else return 0;
    }
}