[백준] 1935: 후위 표기식2

 

후위 표기식을 입력하고 계산 결과값을 출력하는 문제이다.

 

 

 

 

입출력 예제이다.

 

 

후위 표기식 ABC*+DE/-는 중위 표기식 (A+(B*C) - (D/E)로 표현할 수 있다.

 

후위 표기식은

피연산자를 스택에 넣고 연산자가 입력되면 pop을 해서 연산한 뒤 결과를 스택에 다시 push하는 방식으로 계산할 수 있다.

 

 

 

package boj;

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

public class Main {

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

        // BufferedReader를 사용하여 입력을 받기 위한 객체 생성
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 피연산자의 개수 입력
        int N = Integer.parseInt(br.readLine());

        // 문자를 저장할 스택 생성
        Stack<Double> stack = new Stack<Double>();
        
        // 후위 표기식 입력
        String input = br.readLine();
        
        // 피연산자의 값을 넣을 배열
        double[] arr = new double[N];

        // 피연산자의 개수 만큼 값 입력
        for(int i = 0; i < N; i++) {
        	arr[i] = Double.parseDouble(br.readLine());
      
        }
        
        double result = 0;
        
        for(int i = 0; i < input.length(); i++) {
        	// 피연산자인 경우
        	if(input.charAt(i) >= 'A' && input.charAt(i) <= 'Z') {
        		stack.push(arr[input.charAt(i) - 'A']);
        	} else { // 연산자인 경우
        		double first = stack.pop();
        		double second = stack.pop();
        		
        		switch (input.charAt(i)) {
        		case '+':
        			result = second + first;
        			stack.push(result);
        			continue;
        			
        		case '-':
        			result = second - first;
        			stack.push(result);
        			continue;
        			
        		case '/':
        			result = second / first;
        			stack.push(result);
        			continue;
        			
        		case '*':
        			result = second * first;
        			stack.push(result);
        			continue;
        		}
        		
        	}
        }
        // 결과 출력
        System.out.printf("%.2f", stack.pop());

	}

}

 

연산자를 만나면 pop을 두 번 하게 되는데

이 때 첫 번째로 pop이 된 요소는 first에,

두 번째로 pop한 요소는 second에 저장한다.

 

후위 연산식은 계산할 때 첫 번째로 pop이 된 요소가 연산자 뒤에 위치하게 되므로 연산자가 +라면

second + first

와 같은 순서로 계산하게 된다.

 

arr[input.charAt(i) - 'A']는 현재 읽은 문자(input.charAt(i))가 어떤 알파벳인지에 따라 배열 arr에서 해당 알파벳에 대응하는 값을 스택에 넣기 위해 사용된다.

 

예를 들어 input.charAt(i)가 'A'일 경우, 실제로는 arr[0]에 해당하는 값이 스택에 push되게 됩니다.

이렇게 하면 피연산자의 값을 가져와 계산할 수 있도록 했다.

 

마지막으로 모든 연산을 마친 후 소숫점 둘째 자리까지만 출력해야 하므로 형식지정자 %.2f로 출력했다.