[BOJ] 1935번 후위표기식 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        String s = br.readLine();
        int idx = 0;
        Stack<Double> stack = new Stack<>();

        double[] arr = new double[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Double.parseDouble(br.readLine());
        }

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if ('A' <= c && c <= 'Z') {
                stack.push(arr[c - 'A']);
            } else {
                double b = stack.pop();
                double a = stack.pop();

                if (c == '*') {
                    stack.push(a * b);
                } else if (c == '/') {
                    stack.push(a / b);
                } else if (c == '+') {
                    stack.push(a + b);
                } else if (c == '-') {
                    stack.push(a - b);
                }
            }
        }

        System.out.printf("%.2f", stack.pop());
    }
}

📄 해설

접근

• 스택을 사용해서 후위 표기식을 계산하는 방법을 알고 있어야 하고, 알파벳별 지정된 숫자를 배열에 저장해두고 사용한다는 것에 접근해야한다.
• 먼저 스택을 사용해서 후위 표기식을 계산하는 방법은 다음과 같다.
  1. 피연산자를 만나면 스택에 넣는다.
  2. 연산자를 만나면 스택에서 숫자 두 개를 꺼내서 계산하고 그 결과를 다시 스택에 넣는다.
  3. 마지막에 스택에 남아있는 수가 최종 연산 결과이다.
• 그리고 알파벳별로 지정된 숫자를 배열에 저장해둔다는 것은 다음과 같다.
  • A ~ Z 를 각각 아스키 코드 연산을 통해 배열의 0번 인덱스부터 25번 인덱스까지 다음과 같이 할당한다고 생각하면 된다. arr[{알파벳} - 'A']
• 결과 값이 실수가 나올 수 있으므로, 모든 변수를 실수형 타입으로 사용해준다.

과정

• A 부터 Z 까지 순서대로 숫자가 입력되므로, 순서대로 배열에 넣어준다.
• 이후 입력된 문자열의 모든 문자를 확인할 때까지 다음과 같은 과정을 반복한다.
  1. 연산자가 아닌 경우는 아스키 코드 연산을 통해 인덱스를 얻고, 그 인덱스로 배열에 접근해서 해당 값을 스택에 넣는다.
  2. 연산자를 만나면 스택에서 숫자 두개를 꺼내서 계산하고 그 결과를 다시 스택에 넣어준다.
• 스택의 마지막 원소가 연산의 결과값이므로, 스택에서 꺼내서 소숫점 둘째자리까지 출력해준다.