[백준] 1918 후위 표기식

후위표기식

알고리즘[접근 방법]

후위 표기식은 연산자가 피연산자 뒤에 있는 표기식이다. 예를 들어 3+5X2 는 352X+가 된다.
Stack 자료 구조를 활용해서 푸는 문제이다.
이 문제에서 핵심은 피연산자는 바로 출력하고 스택에는 연산자와 괄호만 사용하는 것이다.

스택의 규칙은 다음과 같다.

• 우선 순위가 더 높은 연산자는 낮은 연산자의 밑에 있을 수 없다. 만약 스택의 top보다 우선 순위가 더 낮은 연산자가 입력될 경우 더 낮은 우선 순위를 가진 연산자가 나올 때까지 pop한다.
• )가 입력 될 경우 (가 나올 때까지 pop한다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;

public class Main {

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

        String[] input = br.readLine().split("");

        Stack<String> stack = new Stack<>();

        for (String s : input) {
            if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
                while (!stack.isEmpty() && priority(stack.peek()) >= priority(s)) {
                    sb.append(stack.pop());
                }
                stack.push(s);
            } else if (s.equals("(")) {
                stack.add(s);
            } else if (s.equals(")")) {
                while (!stack.isEmpty() && !stack.peek().equals("(")) {
                    sb.append(stack.pop());
                }
                stack.pop();
            } else {
                sb.append(s);
            }
        }

        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }

        wr.write(sb.toString());
        wr.flush();
        wr.close();
        br.close();

    }

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

}