[BaekJoon] 1918 후위 표기식 (Java)

1.  문제 링크

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

2.  문제

요약

• 후위 표기법은 연산자가 피연산자 뒤에 위치하는 방법입니다.
• 중위 표기식을 후위 표기식으로 바꾸려고 하는데, 바꾸는 방법은 다음과 같습니다.
  • 우선, 주어진 중위 표기식을 연산자의 우선순위에 따라 괄호로 묶어줍니다.
  • 그런 다음 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨줍니다.
• 중위 표기식이 주어졌을 때, 후위 표기식으로 고치는 문제입니다.
• 입력: 첫 번째 줄에 중위 표기식이 주어집니다.
  • 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장합니다.
  • -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식은 주어지지 않습니다.
  • 표기식은 알파벳 대문자와 +, -, *, /, (, ) 로만 이루어져 있으며, 길이는 100을 넘지 않습니다.
• 출력: 첫 번째 줄에 후위 표기식으로 바뀐 식을 출력합니다.

3.  소스코드

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

public class Main {
    static char[] expression;
    static void input() {
        Reader scanner = new Reader();
        expression = scanner.nextLine().toCharArray();
    }

    static void solution() {
        StringBuilder sb = new StringBuilder();
        Stack<Character> operator = new Stack<>();
        for(char elem : expression) {
            if(elem == '(') {
                operator.push(elem);
            } else if(elem == ')') {
                while(!operator.isEmpty()) {
                    char op = operator.pop();
                    if(op == '(') break;
                    sb.append(op);
                }
            } else if(elem == '+' || elem == '-' || elem == '*' || elem == '/') {
                while(!operator.isEmpty() && getPriority(operator.peek()) >= getPriority(elem)) {
                    sb.append(operator.pop());
                }
                operator.push(elem);
            } else {
                sb.append(elem);
            }
        }

        while(!operator.isEmpty()) sb.append(operator.pop());

        System.out.println(sb);
    }

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

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

4.  접근

• 주어진 중위 표기식을 char형 배열로 변경합니다.
• 첫 번째 문자부터 마지막 문자까지 확인하여 후위 표기식을 완성합니다.
  • 괄호가 연산에서 가장 높은 우선순위를 가지기 때문에 괄호를 먼저 확인합니다.
    • 만약 현재 문자가 여는 괄호라면, Stack에 여는 괄호를 넣어줍니다.
    • 만약 현재 문자가 닫는 괄호라면, Stack에서 여는 괄호가 나올 때까지 문자들을 뽑아내고 이를 StringBuilder에 순차적으로 넣어 후위 표기식을 만들어갑니다.
  • 현재 문자가 대문자인지 연산기호인지 확인하고 그에 따라 아래와 같은 작업을 진행합니다.
    • 만약 문자가 대문자라면, StringBuilder에 해당 대문자를 추가하여 후위 표기식을 만들어갑니다.
    • 만약 문자가 연산기호라면 아래와 같은 작업을 진행합니다.
      1. Stack에서 꺼낸 연산기호 혹은 여는 괄호와 현재 문자를 비교합니다.
      2. getPriority() 함수를 통해 해당 문자의 우선순위를 가져올 수 있습니다.
      3. 현재 연산기호의 우선순위보다 Stack에서 꺼낸 연산기호 혹은 여는 괄호의 우선순위가 크거나 같다면 Stack에서 해당 연산기호 혹은 여는 괄호를 제거하고 StringBuilder에 그것을 추가하여 후위 표기식을 만들어갑니다.
      4. 모두 pop을 했다면 현재 연산기호를 Stack에 넣습니다.
  • 위 작업을 모두 완료했다면 Stack에 남은 연산기호들을 뽑아 순차적으로 StringBuilder에 추가함으로서 후위 표기식을 완성합니다.