백준 1918번 (java)

접근

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

다시 한번 풀어봐야할 문제여서 기록하기로 했다.
일단 이 문제는 우리가 잘 알고 있는 중위 표기식을 후위표기식을 만드는 문제이다.

방법

이 문제를 풀 때 몇 가지 상황을 고려해야 한다.

첫 번째, 먼저 연산자와 피연산자를 구별할 부분을 구현해야 한다.
➡️ switch-case-default
➡️ 혹은 아스키코드 값을 이용해서 65와 90사이이면 피연산자

두 번째, 연산자 사이의 순위를 매길 수 있는 함수를 따로 구현해야 한다
➡️ +,-가 /,*보다 연산 우선수위가 낮다는 걸 return 값으로

세 번째, 그래서 어떻게 할것인가?
연산자는 stack을 이용해서 쌓는다
그리고 피연산자는 계속 StringBuilder에 추가하는 것
추가하다가 중간중간에 비교를 통해서 stack에서 꺼내야할 상황이 생기면 꺼내고 StringBuilder에 추가하는 것이다.

네 번째, 그래서 언제 stack에서 꺼내는가?

1. 현재 stack 맨 꼭대기에 있는 연산자가 '('이 아니면서 맨 꼭대기에 연산자의 순위보다 낮거나 같은 연산자가 들어올 경우
   즉 st.peek()의 우선순위 > = 들어오는 연산자

2. ')'인 경우 '('을 만날 때까지 pop()하여 StringBuilder에 더해줌

그리고 마지막으로
A+B+C의 후위 표현식이 AB+C+임을 기억하자
나는 ABC++인줄 알고 헤맸다.

풀이(자바코드)

import java.util.*;
import java.io.*;


public class Main{


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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String input = br.readLine();

        Stack<Character> st = new Stack<>();

        StringBuilder sb = new StringBuilder();


        for(int i=0;i<input.length();i++){
            char in = input.charAt(i);
             switch (in){
                 case '*' :
                 case '-' :
                 case '+' :
                 case '/' :
                 {
                     while(st.size()!=0&& prior(in) <= prior(st.peek()) && st.peek()!='(') {
                         sb.append(st.pop());
                     }
                     st.add(in);
                     break;
                 }
                 case '(' : {
                     st.add(in);
                     break;
                 }
                 case ')':{
                     while( st.size()!=0 && st.peek()!='(') {
                         sb.append(st.pop());
                     }
                     st.pop();
                     break;
                 }
                 default: sb.append(in);
             }
        }

        while(st.size()!=0){
            sb.append(st.pop());
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();

    }

    static int prior(char x){
        if(x=='-') return 0;
        if(x=='+') return 0;
        else return 1;
    }

}