[Java] BOJ1935 - 후위 표기식2

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

1935번: 후위 표기식2

 

💬 예제 이해하기

예제 입력 1

후위 표기식만 보고 우리가 평소 사용하는 중위 표기식처럼 계산하기는 어려우므로 먼저, 예제를 중위 표기식으로 바꿔보자.

1️⃣ 후위 표기식을 중위 표기식으로 바꾸어보며 연산 순서 파악하기

예제 입력 1을 중위 표기식으로 변환

※ 이렇게 중위 표기식으로 먼저 바꿔본다면 어떤 식을 먼저 해야할지 알 수 있다.

(B*C) 👉 A+((B*C)의 결과) 👉 (D/E) 👉 ((A+(B*C))의 결과) - ((D/E)의 결과)

위의 계산 과정과 입력 예제를 잘 살펴보자.

* 👉 + 👉 / 👉 - 의 순서대로 앞의 피연산자를 이용하여 연산을 한다는 점이 보인다.

 

✨ 나는 Stack을 이용하여 연산자일 경우에만 Stack에 있는 두 피연산자를 pop()하여 연산하고, 피연산자일 경우에는 Stack에 push() 해주었다.

 

❗ Stack에 push() 해줄 때는 앞에 있는 수가 먼저 Stack에 쌓이게 되어 pop()할 때는 위의 후위 표기식과는 반대의 순서로 피연산자가 나온다는 것을 유의하자! (-, /의 경우)

 

2️⃣ 각 영어 대문자에 맞는 수 찾아주기

처음에는 각 영어 대문자에 맞는 수가 무조건 A=1, B=2, C=3,··· 이런 식으로 적용이 되는 줄 알았는데 채점 결과 20%도 채 되지 않아 '틀렸습니다'라는 결과가 떴다.

잘못 생각했을 때의 결과

✨ 그래서 나는 숫자 배열을 하나 만들어 그곳에 각 숫자들을 저장해놓고 아스키코드를 이용하여 각 영어 순서에 맞는 숫자들을 연산하도록 하였다.

ex) 입력 예제 1의 경우 

입력 예제 1의 숫자 배열

위와 같이 배열 arr을 선언하여 값을 담아주고 arr[각 문자열의 아스키코드 값 - 65]을 이용하여 A=arr[65 - 65] = 1, B = arr[66 - 65] = 2, ··· 이렇게 찾도록 구현하였다.

 

✨ 코드 효율

👉 메모리 : 14556 KB
👉 시간 : 128 ms
👉 코드 길이(주석 포함) : 1373 B

 

✔ 소스코드

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

public class Main {  // 후위 표기식2

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String postfix = br.readLine();
        Stack<Double> stack = new Stack<>();
        int[] arr = new int[N];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }


        for (int i = 0; i < postfix.length(); i++) {
            char ch = postfix.charAt(i);
            if(ch == '+') {
                double number = stack.pop() + stack.pop();
                stack.push(number);
//                System.out.println(stack);
            }else if(ch == '-') {
                double first = stack.pop();
                double second = stack.pop();
                stack.push(second - first);
//                System.out.println(stack);
            }else if(ch == '*') {
                double number = stack.pop() * stack.pop();
                stack.push(number);
//                System.out.println(stack);
            }else if(ch == '/') {
                double first = stack.pop();
                double second = stack.pop();
                stack.push(second / first);
//                System.out.println(stack);
            }else {
                stack.push((double)(arr[(int)ch - 65]));
//                System.out.println(stack);
            }
        }

        String result = String.format("%.2f", stack.pop());

        System.out.println(result);
    }

}

 

💡 포인트

1️⃣ 후위 표기식(Postfix)을 중위 표기식(Infix)으로 바꿔보기
2️⃣ 연산자가 나올 때마다 연산자 앞에 있는 두 개의 피연산자를 해당 연산자로 계산해주기

3️⃣ 피연산자를 Stack에서 pop() 해줄 때는 후위 표기식에 나와있는 것과는 반대의 순서로 나오는 점 유의하기

    👉 '-' 와 '/'의 경우, first와 second 변수를 이용하여 정확하게 연산해야 한다
4️⃣ 해당 문자열에 맞는 숫자를 저장해놓았다가 연산에 활용하기
5️⃣ 반드시 답은 소수 두번째 자리까지 나타내기
    👉 Math.round()은 마지막이 0으로 끝날 경우 0을 모두 절삭하므로

         Math.round()보다는 String.format()을 활용하는 것이 좋다