[알고리즘] 백준 1935 - 후위 표기식2

분류 : 자료구조

1. 문제

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

2. 입력

첫째 줄 : 피연산자의 개수 N
둘째 줄 : 후위 표기식
셋째 줄~N+2번째 줄 : 각 피연산자에 대응하는 값

3. 풀이

*중요!!!!! float말고 double로 해야 풀린다.

float으로 하면 뒤에 소숫점이 달라져서 정답 인정을 안해줌

후위표기식1 문제와 반대로 생각하면 된다.
역으로 문자를 스택에 넣고, 연산자가 나올 때 마다 스택에서 꺼내서 계산해준다.

1. 피연산자 대응 값을 배열로 만든다. (알파벳을 그대로 인덱스로 사용)
2. 후위표기식 길이동안 문자를 확인해준다.
   1) 알파벳일 경우 스택에 넣는다.(대응 숫자로)
   2) 연산자일 경우 스택에서 피연산자를 2개 꺼내 계산한다
   -> 계산한 값은 다시 스택에 피연산자로 넣어준다.
   뒤에 오는 피연산자가 top에 존재하므로, 첫번째 pop할 때의 피연산자가 뒤로, 두번째 pop할 떄의 피연산자가 앞으로 오도록 계산한다.

4. 코드

import java.util.Scanner;
import java.util.Stack;

//20211228
public class postfix2 {

    public static void solution(){
        //char A = 'A';
        //System.out.println((int)A);

        Scanner in = new Scanner(System.in);

        //피연산자 개수
        int N = in.nextInt();

        //개행문자 삭제
        in.nextLine();

        //후위 표기식
        char[] input = in.nextLine().toCharArray();

        //피연산자 대응 값
        double[] num = new double[N];
        for(int i = 0; i<N; i++){
            num[i] = in.nextFloat();
        }


        //피연산자 스택
        Stack<Double> stack = new Stack<>();


        for(int i=0; i<input.length;i++){

            //알파벳이면 스택에 넣음
            if(input[i] >= 'A' && input[i]<='Z'){
                // (int)input[i]-65 -> A를 0이라 생각하고 알파벳을 0부터 대응시켜 인덱스로 사용
                stack.push(num[(int)input[i]-65]);
            }
            else{

                double operand_2; //뒤에 올 피연산자(첫번째 pop)
                double operand_1; //앞에 올 피연산자(두번째 pop)

                operand_2 = stack.pop();
                operand_1 = stack.pop();


                switch (input[i]){
                    case '+':
                        operand_1 += operand_2;
                        break;
                    case '-':
                        operand_1 -= operand_2;
                        break;
                    case '*':
                        operand_1 *= operand_2;
                        break;
                    case '/':
                        operand_1 /= operand_2;
                        break;
                }
                stack.push(operand_1);
            }
        }

        System.out.println(String.format("%.2f",stack.peek()));

    }

}