백준 1918_후위 표기식_JAVA

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

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));
        Stack<Character> stack = new Stack<>();
        String line = br.readLine();
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < line.length(); i++) {
            char chr = line.charAt(i);
            if(chr >= 'A' && chr <= 'Z') {
                sb.append(chr);
            } else {
                int p = priority(chr); // 현재 연산자 우선순위 구하고
                switch (chr) {
                    case '*':
                    case '/':
                    case '-':
                    case '+':
                        while(!stack.isEmpty() && priority(stack.peek()) >= p) {
                            // 현재 연산자보다 큰 우선순위를 가진 연산자를 만날때까지 모두 pop하고 정답에 저장
                            sb.append(stack.pop());
                        }
                        stack.push(chr);
                        break;

                    case ')':
                        while (!stack.isEmpty() && stack.peek() != '(') {
                            sb.append(stack.pop());
                        } // )는 최우선 연산자이기 때문에 '('를 만날때까지 모두 pop

                        stack.pop(); // 남아있는 '('를 꺼냄
                        break;
                    case '(':
                        stack.push(chr);
                        break;
                }
            }
        }

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

        System.out.print(sb.toString());

    }

    private static int priority(char chr) { // 우선순위 반환
        switch (chr) {
            case '*': return 2;
            case '/': return 2;
            case '-': return 1;
            case '+': return 1;
            default: return 0;
        }
    }
}

 

 

회고

- 전혀 생각이 나질 않아서 블로그를 참고하고 풀었다.

- 다시 풀어봐야겠다.

- 단순 스택만을 써서 푸는 문제중 어려운 문제들은 이런식으로 나올 것 같다.