[JAVA] 백준 1918 후위 표기식

 

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

 

문제분석

중위 표기법을 후위 표기법으로 바꿔서 출력하는 문제다. 후위 표기법으로 나타내진 문제를 stack을 활용하여 계산하는 문제는 많이 봤어도, 중위 표기법 -> 후위 표기법을 나타내는 문제여서 다소 어렵다.

이 문제를 풀기 위해서는 "연산자의 우선순위" 를 고려해야 한다. A+B*C가 있다면, ABC를 먼저 출력하고 연산자를 출력하면 된다. 이때, *를 먼저 출력하고 +를 출력해야 한다. 또한, 같은 우선순위여도 + - 순서를 고려해야 하기 때문에, 같은 우선순위여도 먼저 출력해야 한다.

 

 

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split("");
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        ArrayDeque<String> stack = new ArrayDeque<>();

        for (int i = 0; i < arr.length; i++) {
            if (arr[i].equals("+")
                    || arr[i].equals("-")
                    || arr[i].equals("*")
                    || arr[i].equals("/")) { // 연산자의 경우
                if (stack.isEmpty()) {
                    stack.push(arr[i]);
                } else {
                    while (!stack.isEmpty() && priority(arr[i]) <= priority(stack.peek())) {
                        // 내 연산자보다, 이전 연산자가 우선순위 높은 경우 이전 연산자 출력 후 내 연산자 push
                        bw.write(stack.pop());
                    }
                    stack.push(arr[i]);
                }

            } else if (arr[i].equals("(")) {
                stack.push(arr[i]);
            } else if (arr[i].equals(")")) {
                // "(" 나올때까지 pop하면서 출력
                while (!stack.isEmpty() && !stack.peek().equals("(")) {
                    bw.write(stack.pop());
                }
                stack.pop();
            } else {// 무조건 출력에 추가
                bw.write(arr[i]);
            }
        }
        while (!stack.isEmpty()) {
            bw.write(stack.pop());
        }

        bw.newLine();
        bw.close();

    }

    public static int priority(String s) {
        if (s.equals("/") || s.equals("*")) {
            return 2;
        } else if (s.equals("+") || s.equals("-")) {
            return 1;
        }
        return 0;
    }
}