백준 1918 후위 표기식 Java

중위 표기식을 후위 표기식으로 바꾸는 문제이다.

 

스택으로 후위 표기식을 계산하는 방법을 배운 적은 있어도

중위 표기식을 후위 표기식으로 바꾸는 알고리즘은 잘 모르고 있었다.

 

이 방법을 어떻게 구현하면 좋을까 고민해봤지만 생각해내기 어려웠다.

그러다 알게 된 알고리즘이 차량기지 알고리즘(Shunting-yardAlgorithm)이다.

 

차량기지 알고리즘은 

중위 표기식을 후위 표기식으로 바꿔주는 알고리즘이다.

 

차량 기지 알고리즘은 스택에 문자열을 전부 넣는 방식이 아닌

연산자만 넣어주고 그 연산자들의 우선순위를 비교하여

출력해주는 방식이다.

 

1. 연산자가 아닌 경우엔 출력한다.

2. 연산자인 경우엔 스택에 넣어준다. 단 ')'는 넣지 않는다.

 

2번의 연산자인 경우에 스택에 넣어줄 때 조건이 있다.

- ')'의 경우엔 '('를 만날 때까지 스택에서 pop해서 출력한다. ')'는 스택에 넣지 않는다.

- '('의 경우엔 스택에 바로 넣어준다.

- ')' 나 '('가 아닌 연산자의 경우엔 스택에 마지막에 있는 연산자보다

  우선순위가 높은 경우에만  스택에 넣을 수 있다.

 

우선순위는 수가 클수록 높은 것이다

( : 0

+, - : 1

*, / : 2

 

예를 들어 스택에 +,*가 있고

스택에 넣어야 하는 연산자가 /라면

스택에 마지막에 있는 *는

/보다 연산 우선순위가 같기 때문에 pop해서 출력하고

스택에 마지막에 있는 +는

/가  우선순위가 더 높기 때문에 스택에 넣는다.

문자열을 다 탐색한 후

스택에 연산자가 남아있다면

전부 pop해서 출력해준다.

 

예를 들어서

A+B-(C*D)인 경우엔

A는 출력

+는 스택에 넣고

B출력 -> AB

-는 스택의 마지막인 +보다 우선순위가 같기 때문에

스택에 아직 들어갈 수 없다.

+출력 -> AB+

-를 스택에 넣고

(는 무조건 스택에 넣는다. -> -, (

C출력 -> AB+C

*는 (보다 우선순위가 높기 때문에

스택에 넣는다 -> -, (, *

D출력 -> AB+CD

)는 (를 만날 때까지 pop해서 출력한다

*출력 -> AB+CD*

( pop

스택에 남아있는 - 출력

AB+CD*-

 

마지막으로 다시 정리하자면

1. 연산자가 아닌 경우엔 출력

2. (는 스택에 push

3. )는 (를 만날 때까지 pop한 후 (를 제외하고 출력

4. +-*/ 연산자들은 스택에 마지막에 있는 연산자보다

  우선순위가 높을 때까지 pop해서 출력 후 스택에 push

5. 문자열을 탐색 후 스택에 남아있는 연산자 pop후 출력

 

연산자의 우선순위를 구하는 메소드를 구현한 후

위에 나온 순서로 구현하면 된다.

 

import java.util.*;
 
public class Q1918 {
    static int precedence(char ch) {
        if (ch == '(') return 0;
        if (ch == '+' || ch == '-') return 1;
        else return 2;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String ans = "";
        Stack<Character> ops = new Stack<>();
        for (char ch : s.toCharArray()) {
            if ('A' <= ch && ch <= 'Z') {
                ans += ch;
            } else if (ch == '(') {
                ops.push(ch);
            } else if (ch == ')') {
                while (!ops.isEmpty()) {
                    char op = ops.pop();
                    if (op == '(') break;
                    ans += op;
                }
            } else {
                while (!ops.isEmpty() && precedence(ops.peek()) >= precedence(ch)) {
                    ans += ops.pop();
                }
                ops.push(ch);
            }
        }
        while (!ops.isEmpty()) {
            ans += ops.pop();
        }
        System.out.println(ans);
    }
}