문제 링크

개요

A*(B+C) 와 같이 중위표기식으로 써진 수식을 ABC+* 과 같은 후위표기식으로 바꿔 출력해야 한다.

접근

  1. 자료구조는 Stack을 이용해서 해결한다.
  2. 연산자 또는 여는 괄호가 나오면 stack에 넣어둔다.
  3. 연산자 stack을 언제 내보내야 하는지 정의해야 한다.
    1. 연산자간의 우선순위를 정의해야 한다. (곱셈 나눗셈과 덧셈 뺄셈간의)
      • stack의 top에 있는 연산자보다 우선순위가 낮은 연산자가 들어 오려 한다면, top을 내보낸다 (먼저 계산해야 하므로)
      • stack의 top에 있는 연산자와 같은 우선순위의 연산자가 들어 오려 한다면, top을 내보낸다 (먼저 계산해야 하므로)
    2. 닫힌 괄호를 만났을 때, 여는 괄호를 만날 때 까지의 연산자들을 내보내야 한다.

코드

public class Main {
    public static void main(String[] args) throws IOException {
        Main main = new Main();

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        String s = bf.readLine();
        main.solution(s);
    }

    public void solution(String s) {
        Stack<Character> stk = new Stack<>();
        StringBuffer sb = new StringBuffer();
        Map<Character, Integer> valueMap = new HashMap<>();

        valueMap.put('*', 1);
        valueMap.put('/', 1);
        valueMap.put('+', 0);
        valueMap.put('-', 0);
        valueMap.put('(', -1);

        for (int i = 0; i < s.length(); i++) {
            Character currentChar = s.charAt(i);

            if (currentChar.toString().matches("[A-Z]")) {
                sb.append(currentChar);
                continue;
            }

            if (currentChar == '(') {
                stk.push(currentChar);
                continue;
            }

            if (currentChar == ')') {
                while (stk.peek() != '(') {
                    sb.append(stk.pop());
                }
                stk.pop();
                continue;
            }

            if (stk.size() > 0) {
                int size = stk.size();

                for (int j = 0; j < size; j++) {
                    Integer currentTopValue = valueMap.get(stk.peek());
                    Integer currentInputValue = valueMap.get(currentChar);

                    if (currentTopValue >= currentInputValue) {
                        sb.append(stk.pop());
                    } else break;
                }
            }

            if (currentChar == '+' || currentChar == '-' || currentChar == '*' || currentChar == '/') {
                stk.push(currentChar);
            }
        }

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

        System.out.println(sb);
    }
}