P.1918 후위 표기식

코드

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

public class P_1918 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String exp = br.readLine();
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < exp.length(); i++) {
            if (exp.charAt(i) >= 'A' && exp.charAt(i) <= 'Z') bw.write(exp.charAt(i));
            else if (exp.charAt(i) == '(') stack.push(exp.charAt(i));
            else if (exp.charAt(i) == ')') {
                while (true) {
                    if (stack.empty()) break;
                    Character pop = stack.pop();
                    if (pop == '(') break;
                    bw.write(pop);
                }
            }
            else {
                int targetPriority = getPriority(exp.charAt(i));
                while (true) {
                    if (!stack.empty() && (getPriority(stack.peek()) >= targetPriority)) bw.write(stack.pop());
                    else break;
                }
                stack.add(exp.charAt(i));
            }
        }

        while (!stack.empty()) {
            bw.write(stack.pop());
        }

        bw.flush();
    }

    private static int getPriority(char op) {
        if (op == '+' || op == '-') return 1;
        else if (op == '*' || op == '/') return 2;
        else return 0;
    }
}

코드 설명

스택을 사용하는 대표적인 문제다.

 

이 문제의 초점은 다음과 같다.

1. 연산자가 아닐 경우 (위 문제에선 알파벳) 바로 출력한다.
2. 여는 괄호일 경우 일단 스택에 넣고, 닫는 괄호일 경우 여는 괄호가 나올 때까지 스택을 pop하면서 출력한다.
3. 연산자가 들어왔을 때는 스택을 pop하면서 자신의 우선순위보다 높거나 같은 연산자를 모두 출력하고 그 후 자신을 push한다.

우선순위의 경우 +, -가 *, /보다 낮다. 

연산자 우선순위를 정할 때 괄호에 의해서 스택이 변하면 안되므로 가장 낮은 우선순위를 두었다.