[백준]1918. 후위 표기식

[백준]1918. 후위 표기식

📄 링크

후위 표기식

---

💡 문제 분석

중위 표기식을 입력으로 받아 후위 표기식으로 출력하는 문제입니다.
후위 표기식은 괄호가 필요 없기 때문에 입력으로 받아도 출력하지 않습니다.

보통 이런 수식 문제들은 스택을 이용하는 경우가 많은 것 같습니다. ArrayDeque을 이용해서 풀어보았습니다.

1. ‘(‘

• 열린 괄호가 나온다면 스택에 푸시합니다

2. ‘)’

• 닫힌 괄호가 나온다면 열린 괄호가 나올 때까지 출력합니다.

3. A ~ Z

• 그대로 출력합니다

4. Operator

• 자신보다 우선순위가 낮은 연산자가 나올 때까지 스택에서 뽑아서 출력합니다
• 우선순위를 리턴하는 함수를 만들었습니다.

• 마지막엔 스택이 빌때까지 뽑아서 출력합니다.

---

⌨️ 코드

import java.util.ArrayDeque;
import java.util.Scanner;

public class Boj1918_tk {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        String s = sc.next();
        ArrayDeque<Character> stk = new ArrayDeque<>();
        for(int i= 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(c == '(') {
                stk.push(c);
            }
            else if(c == ')') {
                while(!stk.isEmpty() && stk.peek() != '(') {
                    sb.append(stk.poll());
                }
                stk.poll();
            }
            else if(c >= 'A' && c <= 'Z') {
                sb.append(c);
            }
            else {
                int p = getPriority(c);
                while(!stk.isEmpty() && getPriority(stk.peek()) >= p) {
                    sb.append(stk.poll());
                }
                stk.push(c);
            }
        }
        while(!stk.isEmpty())
            sb.append(stk.poll());
        System.out.println(sb);
    }

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