[백준] 1918 : 후위 표기식 (JAVA/자바)

문제

BOJ 1918 : 후위 표기식 - https://www.acmicpc.net/problem/1918

풀이

stack 자료구조를 사용해서 풀이하는 문제이다.

여기서 핵심은, 스택에는 연산자만 사용하고, 피연산자는 바로바로 출력한다! 라는 것.

• 연산자의 우선 순위를 지정해서 stack에 넣기 전에, 현재 연산자의 우선순위보다 큰 연산자가 stack의 맨 위에 있다면 없을 때까지 pop한다. (우선순위가 큰 연산자가 먼저 계산되어야 하기 때문)

• )일 경우에는 (가 나올 때까지 stack 안의 연산자를 pop한다!

• 피연산자는 따로 스택에 넣지 않고 그때그때 그냥 StringBulder에 append 해주면 된다.

코드

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

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

        String str = br.readLine();

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

        for (int i = 0; i < str.length(); i++) {
            char now = str.charAt(i);

            switch (now){
                case '+':
                case '-':
                case '*':
                case '/':
                    while (!stack.isEmpty() && priority(stack.peek()) >= priority(now)) {
                        sb.append(stack.pop());
                    }
                    stack.add(now);
                    break;
                case '(':
                    stack.add(now);
                    break;
                case ')':
                    while(!stack.isEmpty() && stack.peek() != '('){
                        sb.append(stack.pop());
                    }
                    stack.pop();
                    break;
                default:
                    sb.append(now);
            }
        }

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

        System.out.println(sb.toString());
    }

    // 연산자 별 우선순위 리턴
    public static int priority(char operator){

        if(operator=='(' || operator==')'){
            return 0;
        } else if (operator == '+' || operator == '-') {
            return 1;
        } else if (operator == '*' || operator == '/') {
            return 2;
        }
        return -1;
    }

}

정리

✔ 알고리즘 분류 - 자료 구조, 스택
✔ 난이도 - 🟡 Gold 3

🤦‍♀️ 오늘의 메모

• 다들 문제를 보자마자 stack을 사용해서 풀어야 한다는 걸 알았다고 하는데 나는 전혀 몰랐다,, stack을 사용해서 풀이하는 문제에는 이런 유형이 있다는 것을 기억해둘 것.
• 연산자만 stack에 넣으면서 처리해주는 방법이 너무 낯설었다,, 열심히 경우의 수를 그려보며 풀이법을 찾으려고 해봤는데 도저히 모르겠어서 블로그를 참고했다!

참고 사이트

https://gre-eny.tistory.com/312