1918 자바 ] 후위 표기식(풀이)

※ 문제

출처(https://www.acmicpc.net/problem/1918)

---

문제 이해하기.

문제를 이해하려면 '후위표기식'을 이해해야한다. 설명하기에 앞서 우리가 사칙연산을 할 때 흔히 사용하는 표기식은 '중위표기식'이다.

 

ex) A+B*C/(D-E) → 이것이 '중위 표기식'

 

계산하고자하는 '표기식'의 연산자를 비연산자 보다 뒤에 위치한 식이 '후위 표기식'이다.

예를들어, 중위 표기식 'A+B'를 → 후위 표기식으로 바꾸면 'AB+'가 된다. 그렇다면 더 복잡한 '식'을 예로들어 보자.

 

ex) 중위 표기식 'A+B*C/(D-E)'를 → 후위 표기식으로 바꾸면 'ABC*DE-/+'가 된다.

 

처음에 이해가 잘 안될 수 있는데 사칙연산 순서를 생각하면 바로 이해가 될 것이다.

변환과정을 순서대로 정리한 상단 이미지 내용 참고

---

1. 성공

 1) 설계

  - 문제를 이해했다면 어떻게 코딩을 할 지 구상을 해보자. 먼저, 계산식의 우선순위를 정리했다.

먼저, 연산자별 우선순위를 지정한다. 

HashMap<String, Integer> map = new HashMap<>();
map.put("(", 1);
map.put("+", 2);
map.put("-", 2);
map.put("*", 3);
map.put("/", 3);

map을 이용해 우선순위를 지정했다.

① '괄호 열기'를 찾은 후 먼저 계산해야한다. 

② 덧셈보다 곱셈을 먼저 계산한다.

③ 덧셈보다 나눗셈을 먼저 계산한다.

④ 남은 덧셈을 바꿔주면 끝

 

더 이해를 돕기위해 아래 코드와 주석을 참고하자.

 2) 코드

import java.io.*;
import java.util.HashMap;
import java.util.Stack;
import java.util.regex.Pattern;

public class Main {
    static Stack<String> stack = new Stack<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        HashMap<String, Integer> map = new HashMap<>();
        map.put("(", 1);
        map.put("+", 2);
        map.put("-", 2);
        map.put("*", 3);
        map.put("/", 3);

        String str = br.readLine();
        String[] arr = str.split("");

        for(int i=0; i<arr.length; i++) {
            if(Pattern.matches("^[A-Z]*$", arr[i])) { // 정규표현식 문자인 경우 바로 출력
                bw.write(arr[i]);
            } else if(arr[i].equals("(")) { // 우선 순위가 가장 큰 괄호 열기를 체크하여 stack의 저장
                stack.push(arr[i]);
            } else if(arr[i].equals(")")) { // 괄호 닫기를 체크(괄호 닫기는 우선 순위 체크용 이기 때문에 stack의 push할 필요 없음)
                while(!stack.isEmpty()) {
                    if(stack.peek().equals("(")) { // stack은 'FILO' 구조여서 '괄호 열기'가 나오면 제거하고 반복문 종료
                        stack.pop();
                        break;
                    }
                    bw.write(stack.pop()); // 괄호안에 연산자 모두 출력
                }
            } else {
                // 우선순위가 가장 높은 괄호안에 계산은 상단 조건문에서 처리하기 때문에 여기서부터는 그 밖에 연산자를 우선순위에 따라 처리하는 로직이다.
                while(!stack.isEmpty() && map.get(stack.peek()) >= map.get(arr[i])) {
                    bw.write(stack.pop());
                }
                stack.push(arr[i]);
            }
        }
        while (!stack.isEmpty()) { // 마지막 남은 연산자를 모두 출력한다.
            bw.write(stack.pop());
        }

        bw.flush();
        bw.close();
    }
}

---

문제의 예제는 모두 통과하였으나 정확도의 이슈가 해결되지 않은 분은 아래 반례로 확인해보기 바랍니다.

※ 반례

문제 : A+B*C/(D-E)
ABC*DE-/+

문제 : A+(B*C)*D*E+F
ABC*D*E*+F+

문제 : A*B+C+D+E*F*G+E
AB*C+D+EF*G*+E+

문제 : A*B/C*D/E
AB*C/D*E/

문제 : A+B*C*((D-E)*G)
ABC*DE-G**+