[JAVA] 백준 (실버3) 1935번 후위 표기식2

링크

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

---

문제 설명

(정답률 48.240%)
후위 표기식과 각 피연산자에 대응하는 값들이 주어져 있을 때, 그 식을 계산하는 프로그램을 작성하시오.

---

입력 예제

5
ABC*+DE/-
1
2
3
4
5

---

출력 예제

6.20

---

나의 코드

import java.io.*;
import java.util.*;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        //입력된 후위 표기식을 문자열 배열로 생성
        String[] strings = br.readLine().split("");
        //피연산자를 키로 입력된 대응 값을 값으로 받을 HashMap 생성
        HashMap<String, Double> map = new HashMap<>();
        Stack<Double> stack = new Stack<>();
        double answer = 0;

		//우선 입력된 피연산자와 수를 대응시킨다
        //이미 HashMap에 존재하는 키일 경우 continue
        for (String s : strings) {
            if (Character.isAlphabetic(s.charAt(0))) {
                if (map.containsKey(s)) 
                    continue;                
                map.put(s, Double.parseDouble(br.readLine()));
            }
        }

		//스택을 이용하여 계산을 진행
        for (String s : strings) {
        	//s가 알파벳일 경우 s의 값에 해당하는 수를 스택에 push
            if (Character.isAlphabetic(s.charAt(0))) {
                stack.push(map.get(s));
            //s가 연산일 경우 연산을 진행하고 결과 값을 다시 스택에 push하여 반복한다
            } else {
                double second = stack.pop();
                double first = stack.pop();
                if (s.equals("+")) {
                    answer = first + second;
                } else if (s.equals("-")) {
                    answer = first - second;
                } else if (s.equals("*")) {
                    answer = first * second;
                } else if (s.equals("/")) {
                    answer = first / second;
                }
                stack.push(answer);
            }
        }

		//소수 둘째자리까지 출력
        System.out.printf("%.2f", answer);
    }
}

---

정리

처음 본 후위 표기식(postfix expression)에 대한 이해가 먼저 필요했다.
우리가 일반적으로 사용하는 사칙연산은 중위 표기식(infix expression)이라 한다.
후위 표기식은 중위 표기식보다 우선 순위를 고려할 필요가 없어 훨씬 직관적이다.
가령 4 (7 + 2) 이라는 연산을 할 때, 후위 표기식으로는 472+로 표기할 수 있다. 왼쪽부터 차례로 읽어가면서 연산이 나오면 연산 앞에 숫자 두개를 계산하면 된다.