공부 88일차: 백준 1918번 후위 표기식 자바 Java

1918 후위 표기식

 

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

1918번: 후위 표기식

 

 

 

---

백준 1918번 문제 후위 표기식

---

문제

---

 

 

 

 

---

과정 생각해보기

---

 

https://gimbalja.tistory.com/165

후위표기식2 문제와 연관짓지 않을 수 없다

 

피연산자나 연산자 중 하나만 스택에 넣는 점에서 비슷하다

이 문제는 피연산자를 넣었던 후위 표기식2와 달리 연산자를 스택에 넣는다

 

 

 

---

정답 인정 코드

---

 

https://takeknowledge.tistory.com/83

이 블로그를 참고했다

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
 
public class Main {
    //우선순위 부여
    public static int priority(char ch) {
        if(ch == '(')
            return 0;
        else if(ch == '+' || ch == '-')
            return 1;
        else                 // (ch == '*' || ch == '/')
            return 2;
    }
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Stack<Character> st = new Stack();
        
        String str = br.readLine();
        
        for(int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            if('A' <= ch && ch <= 'Z') { //알파벳(피연산자)이라면
                bw.write(ch);    //그대로 출력한다
            } else if(ch == '(') {    //괄호 시작이라면
                st.push(ch);    //스택에 ( 추가
            } else if(ch == ')') {    //괄호 끝이라면
                while(!st.empty()) {
                    if(st.peek() == '(') {
                        st.pop();        //스택에서 ( 만나면 버리고 멈추기
                        break;
                    }
                    bw.write(st.pop());    //스택 빌 때까지 연산자 출력
                }
            } else {    //괄호 없는 사칙연산이라면
                //스택이 비어있지 않고, 스택의 끝에 있는 값의 우선순위가 높거나 같다면(즉, *나 /라면)
                while(!st.empty() && priority(st.peek())>=priority(ch)) {
                    bw.write(st.pop());    //연산자 출력
                }
                st.push(ch);    //우선순위 작은 연산자면 다시 스택에 넣는다
            }
        }
        
        while(!st.empty()) {
            bw.write(st.pop());    //스택 빌 때까지 남은 연산자 차례대로 출력
        }
        bw.flush();
        bw.close();
    }
}

 

우선순위를 주는 게 굉장히 새로웠다

 

 

 

---

한 시간 동안 혼자 생각해봤는데 자꾸 알파벳만 스택에 넣으려고 하고 계속 예외 상황 생각하고

짜봐도 다시 보면 한 예제에만 적용되고... 완전 지쳤다

발전이 있나 싶어서 내일부턴 다시 복습할 듯