공부 87일차: 백준 1935번 후위 표기식2 자바 Java

1935 후위 표기식2

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

1935번: 후위 표기식2

 

 

---

백준 1935번 문제 후위 표기식2

---

문제

---

 

 

 

 

 

---

과정 생각해보기

---

 

역시나 스택 문제

주어진 예제로 여러 번 그림을 그려본 결과, 우선 숫자와 연산자를 분리해야겠다고 생각했다

 

 

생각해본 방법은

1) 숫자가 나오면 푸시하고 다른 스택에 연산자를 넣어서 계산

그러나 스택에 남은 숫자가 1일 때, / 등 숫자 순서를 지켜야 하는 경우 등에서 막혔다

특히 연산자가 나란히 있을 때가 골치였다

 

 

그래서 숫자를 스택에 푸시하는 건 유지하고, 연산자를 마주할 때마다 계산하고 스택에 다시 넣는 걸 생각해봤다

->다시 넣지 않으면 스택에 남은 숫자가 1이 되므로 대상이 되는 피연산자를 두 개씩 꺼낼 수 없다

 

 

!!숫자면 스택에 넣고, 연산자면 맞게 계산한 후 다시 스택에 넣는 것이 핵심!!

 

 

 

---

정답 인정 코드

---

 

이렇게 나열되는 경우가 있으면 switch가 적절한 것 같아서 써봤다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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());
        double[] arr = new double[n];    
        String postfix = br.readLine();
        int length = postfix.length();
        
        Stack<Double> st = new Stack();
 
        for(int i = 0; i < n; i++) {
            arr[i] = Double.parseDouble(br.readLine());    //숫자 배열 생성
        }
 
        double result = 0;
        for(int i = 0; i < length; i++) {
            char ch = postfix.charAt(i);
            if('A'<=ch && ch <='Z') {    //요소가 알파벳이라면 스택에 넣는다
                st.push(arr[ch-'A']); 
            //알파벳은 순서대로 주어지므로 'A'를 빼면 해당하는 숫자에 맞는 인덱스값이 나온다 
            //arr[idx]에 저장된 숫자가 해당 알파벳 대신 스택에 들어간다
                
            }else {    //요소가 연산자라면
                    double right = st.pop(); //식 기준 오른쪽에 있는 숫자 먼저 꺼내짐
                    double left = st.pop();
                    
                    switch(ch) {    //연산자가
                        case '+' :    // +라면
                            result = left + right;
                            st.push(result);
                            break;
                        case '-' :    // -라면
                            result = left - right;
                            st.push(result);
                            break;
                        case '*' :    // *라면
                            result = left * right;
                            st.push(result);
                            break;
                        case '/' :    // /라면
                            result = left / right;
                            st.push(result);
                            break;
                    }
            }
            
        }
            System.out.printf("%.2f",st.pop());
 
    }
 
}

 

위의 설명과 주석에 적은 대로 짠 코드

 

 

 

---

스택 문제는 정말 다양한 듯.. 재밌지만 아직 어렵고 오래 걸린다