[Algorithm/Java][백준] 1918 후위 표기식

[BOJ] 1918 후위 표기식

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

문제 접근

입력받은 String을 char 배열로 변환한후 하나씩 접근해서 연산자는 Stack을 이용해 처리하고 StringBuilder의 append를 이용해서 이어 붙여주었다.
중위표기식에서 후위표기식으로 변환할 때, Stack을 이용하는데 현재 연산자보다 stack에 top에 있는 연산자의 우선순위가 높다면 postfix에 추가해준다.
'*'와 '/'를 2, '+' 와 '-'를 1, '('을 0으로 설정해서 위에 방식을 가능하도록 했다.
입력을 받아서 4가지 경우로 나누어서 처리를 하였다.
1.A~Z 사이에 피연산자일 경우 postfix에 추가한다.
2.'('인 경우 Stack에 push한다.
3.')'인 경우 Stack에서 '('가 나올때까지 pop해주어 postfix에 추가한다.
4.다른 연산자일 경우 우선순위를 고려해서 현재 연산자의 우선순위가 stack에 top에 있는 우선순위보다 높아질 때까지 stack에 있는 연산자를 pop해서 postfix에 추가하고, 현재 연산자를 스택에 push한다

Code

import java.util.Scanner;
import java.util.Stack;

public class BOJ1918 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();
        System.out.println(toPostfix(input));
    }
    public static String toPostfix(String infix){
        Stack<Character> op = new Stack<>();
        StringBuilder postfix = new StringBuilder();
        for(char c: infix.toCharArray()){
            if(c >= 'A' && c<= 'Z'){
                postfix.append(c);
            }
            else {
                // 연산자일 때
                if(c=='('){
                    op.push(c);
                }
                else if(c==')'){
                    while (!op.isEmpty() && op.peek() != '(') {
                        postfix.append(op.pop());
                    }
                    if(!op.isEmpty()) op.pop();

                } else {
                    // 스택에 연산자가 저장되어있을때, 현재 연산자보다 우선순위가 닞은 우선순위가 나올때까지 pop해서 postfix에 추가한다.
                    while(!op.isEmpty()&&getPrecedence(op.peek()) >= getPrecedence(c)){
                        postfix.append(op.pop());
                    }
                    op.push(c);
                }
            }
        }
        while(!op.isEmpty()){
            postfix.append(op.pop());
        }
        return postfix.toString();
    }
    // 연산자의 우선순위를 반환한다.
    static public int getPrecedence(char op){
        if(op == '*' || op == '/') return 2;
        else if(op == '+' || op == '-') return 1;
        else return 0;
    }
}

어려웠던 점 / 배운 점 / 느낀 점

중위 표기식을 후위 표기식으로 일단 최대한 많은 예시들을 변환해주고, 규칙을 찾는 과정이 오래 걸렸다.
반례들을 최대한 많이 찾아보고 변환해 보면서 계속 알고리즘을 고쳐나갔다.