[BOJ] 백준 1935번 후위 표기식2 (Java)

#1935 후위 표기식2

난이도 : 실버 3

유형 : 자료구조/ Stack

1935번: 후위 표기식2

▸ 문제

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

▸ 입력

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

▸ 출력

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

 

 

문제 풀이

후입선출 LIFO구조를 가진 Stack을 활용하여 후위 표기식에 맞춰서 연산을 해주는 문제이다.

 

설계

1. 각 알파벳에 주어진 숫자들을 Map을 통해 저장한다. - Map<Character, Integer>
2. 후위 표기식을 하나씩 조회하여 숫자는 stack에 저장해준다.
3. 만약 연산자가 나오고 stack의 size가 2개 이상이면 stack에 있는 숫자들을 꺼내 연산을 해준다.

 

시뮬레이션

ABC*+라는 후위표기식을 한 번 돌려보자.

 

1. A를 Stack에 저장한다

 

 

2. B,C를 Stack에 저장한다

 

3. *라는 연산을 하기 위해서 맨 위에 있는 두 숫자를 꺼내준 다음 연산을 해준다.

(/,-연산 C와 B가 나오는 순서를 고려해서 나중에 나오는 값을 C위치에 넣어줘야 한다.)

 

 

4. 연산을 한 C*B라는 숫자를 다시 Stack에 넣는다.

 

5. +연산을 하기 위해서 맨 위에 있는 두 숫자를 꺼내어 연산을 해 준 다음 다시 넣어준다.

 

6. 후위 표기식의 모든 탐색이 끝났으면 stack에 남은 마지막 값을 꺼내주면 된다.

 

 

풀이 코드 

import java.io.*;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

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[] line = br.readLine().split("");
		
		Map<Character, Double> numMap = new HashMap<>();
		for(int i=0; i<n; i++) {
			int num =Integer.parseInt(br.readLine());
			numMap.put((char)(65+i), (double)num);
		}
		
		Stack<Double> st = new Stack<>();
		for(int i=0; i<line.length; i++) {
			char c = line[i].charAt(0);
			if(numMap.containsKey(c)) {
				st.push((double)numMap.get(c));
			}else {
				if(st.size()<2)  continue;
				double res = operator(c, st.pop(), st.pop());
				st.push(res);
			}
			
		}
		System.out.println(String.format("%.2f", st.pop()));
	}
	static double operator(char op, double num1, double num2) {
		double res =0;
		if(op=='*') {
			res= num2*num1;
		}else if(op=='/'){
			res= num2/num1;
		}else if(op=='+'){
			res= num2+num1;
		}else {
			res= num2-num1;
		}
		return Math.round(res *100)/100.0;
	}
}