[백준][자바(java)][스택] #1935 후위표기식2

<문제>

1935번: 후위 표기식2

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

[입력]

첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이는 100을 넘지 않는다) 그리고 셋째 줄부터 N+2번째 줄까지는 각 피연산자에 대응하는 값이 주어진다. (3번째 줄에는 A에 해당하는 값, 4번째 줄에는 B에 해당하는값 , 5번째 줄에는 C ...이 주어진다, 그리고 피연산자에 대응 하는 값은 정수이다)

[출력]

계산 결과를 소숫점 둘째 자리까지 출력한다.

---

<풀이과정>

첫째 줄에 입력받은 피연산자의 개수 n을 이용하여 A부터 순서대로 n개의 영대문자를 HashMap을 이용하여 세번째줄부터 입력받는 대응값을 저장해준다.

 

이를 이용하여 두 번째 줄에 입력받은 후위 표기식을 스택에 저장해줄 때, 입력받은 영대문자를 대신하여 map에서 영대문자에 해당하는 value값을 불러와 저장해준다. 

 

그리고 스택에 저장된 값들을 이용하여 후위 표기식을 적용해준다.

그렇다면 스택을 이용한 후위 표기식에 대해 알아보자.

후위 표기식 설명

후위 표기식 "82/3-"를 예로 위 그림을 보면, 숫자의 경우 스택에 넣어준다.

세 번째의 경우처럼 "/"와 같은 연산자가 나올경우 스택에 저장되어 있는 숫자 2개를 꺼내어 연산을 실행해준다.

이때, 주의할 점이 있다. 스택의 경우 들어간 순서와 반대로 나오기 때문에 나온순서대로 연산을 실행해주면 

8/2가 아닌 2/8가 되기 때문에 정답이 다르게 나온다. 따라서 나온 순서와 반대로 연산이 되도록 변수를 사용해서 순서를 잘 맞춰주어야한다. 

그리고 연산이 완료되면 결과를 또 스택에 넣어주어야한다. 그렇게 마지막까지 연산을 실행하면 빨간색 상자와 마찬가지로 1이라는 결과가 나옴을 알 수 있다. 

 

위의 방법들을 이용한 코드는 다음과 같다.

---

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;
 
public class Main{
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        int n = sc.nextInt();
 
        String s = sc.next();
 
        Map<Character, Double> m = new HashMap<>();
        Stack<Double> st = new Stack<>();
 
        for (int i = 0; i < n; i++) {
            char c = (char) ('A' + i);
            m.put(c, sc.nextDouble());//'A',1
        }
 
        double result = 0.0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) >= 'A' && s.charAt(i) <= 'Z') {
                st.push(m.get(s.charAt(i)));
            } else if (s.charAt(i) == '*') {
                result = st.pop() * st.pop();
                st.push(result);
            } else if (s.charAt(i) == '/') {
                double n2 = st.pop();
                double n1 = st.pop();
 
                result = n1 / n2;
                st.push(result);
            } else if (s.charAt(i) == '+') {
                result = st.pop() + st.pop();
                st.push(result);
            } else {
                double n2 = st.pop();
                double n1 = st.pop();
 
                result = n1 - n2;
                st.push(result);
            }
        }
        System.out.println(String.format("%.2f", st.pop()));
        //System.out.format("%.2f", st.pop());
    }
}

---

*이 문제는 어떠한 참고 자료를 보지 않았습니다.