[JAVA] BOJ(백준) - 후위 표기식2 - 1935

문제내용

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

1935번: 후위 표기식2

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

입력

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

후위 표기식을 앞에서부터 계산했을 때, 식의 결과와 중간 결과가 -20억보다 크거나 같고, 20억보다 작거나 같은 입력만 주어진다.

출력

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

 

---

문제 접근 방법

이문제는 후위표기식이 만들어과정을 알기만 하면 풀수 있는 문제다.

먼저 중위표기식에서 후위표기식으로 만든느 방법을 보면 아래와 같다.

 

중위 표기식 : A-B*C+D 

1. 괄호 치기
   ((A - (B * C)) + D)
2. 연산자 넘기기
   -> (A - (BC)*) + D)
   -> (A(BC)*-) + D)
   -> (A(BC)*-)D)+
3. 괄호 제거
   ABC*-D+

중위 표기식 A-B*C+D 는 후위 표기식 ABC*-D+ 로 변하게 된다.

 

그럼 이제 문제에 접근 했던 순서를 말해보겠다.

1. 소숫점
   소숫점 둘째자리 까지 출력해줘야 하기 때문에 int가 아닌 double을 활용해줘야 한다.
2. 알파벳에 따른 값찾기
   주어진 후위표기식에서 알파벳에따라 값이 달라지기 때문에 해당 알파벳에 맞는 값으로 연산해줘야 한다. 그러기 위해 '탐색중인 알파벳' - 'A' 을 이용하면 된다. 이계산을 통해 몇번째 알파벳을 탐색한지 알 수 있기 때문에 해당 알파벳에 대응하는 값으로 연산이 가능하다.
   
   
3. 후위 표기식 계산
   후위 표기식(문자열) ABC*-D+ 가 주워 졌을때 스택에 차례대로 값을 삽입하면서 연산자가 나오면 삽입했던 피연산자 두개를 뽑아 내가 지금 탐색한 연산자에 맞는 계산을 해주고, 계산한 값을 다시 스택에 넣어주것을 반복하면 마지막에 남은 스택요소가 최종 결과값이 된다.

자세한 내용은 풀이를 보자.

 

---

풀이

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

public class Main {
	static Stack<Double> st = new Stack<Double>();//연산값 넣을 스택
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		Double[] arr = new Double[N];
		String str = br.readLine();
		
		for(int i=0; i<N; i++) {
			arr[i] = Double.parseDouble(br.readLine());
		}
		
		postfix(arr,str);//후위표기 연산
		System.out.println(String.format("%.2f", st.pop()));//출력
	}
	
	//후위 표기 연산
	public static void postfix(Double[] arr, String str) {
		int idx = 0;//arr 인덱스
		
		for(int i=0; i<str.length(); i++) {
			char temp = str.charAt(i);
			//피연산자일때와 연산자일때로 나눔
			if('A'<=temp && temp<='Z') {
				idx = temp - 'A';
				st.add(arr[idx]);
			}else {
				//연산자나오면 스택에 피연산자 2개 뽑고 계산 후 다시 스택에 삽입
				double valueB = st.pop();
				double valueA = st.pop();
				double result = cal(valueA, valueB, temp); 
				st.add(result);
			}
		}
	}
	
	//연산자 나왔을때 스택에 피연산자값 2개 뺀거 계산
	public static double cal(double A, double B, char temp) {
		double value = 0;
		switch (temp) {
		case '+':
			value = A+B;
			break;
		case '-':
			value = A-B;
			break;
		case '/':
			value = A/B;
			break;
		case '*':
			value = A*B;
			break;
		}
		return value;
	}
}

---

마치며

이번엔 후위표기식을 계산하는 방법을 알아봤다. 전에 풀었던 자료구조 문제와 마찬가지로 스택을 사용했는데 전에 스택을 몇번 사용해서 그런지 크게 어렵지 않은 문제였다.