[ boj : 1918 ] 후위 표기식

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

1918번: 후위 표기식

해설 : 중위표현식을 후위 표현식으로 바꾸는 방법인데, 전 이런문제가 좀 벅차더라구요.... 이 기회에서 확실히 머리에 문제 특성을 박아놓고 유연하게 생각하도록 연습해야겠습니다.

 

중위표현식을 후위 표현식으로 변경하려고 보니 연산자 마다 '우선순위'가 주어집니다. 

괄호가 존재하지 않을때는 (+,-) 가 (*,/) 보다 낮아버리죠.

이는 곰곰이 생각하면 (+,-) 가 나올때는 그 전에 나오는 연산자 중에 (*,/) 가 나오고 난 후에 나와야 된다는 뜻입니다.

 

즉, 스택을 사용하여 (*,/)를 박아줬더라면 (+,-) 가 나올땐 (*,/)를 pop 그리고 또한 (+,-) 도 pop 해야됩니다.

그러면 반대로 (+,-) 가 박아져있는 상태이고 (*,/)가 현재일때는 성립하면 안되겠죠. 만약 성립해버리면 (+,-)가 (*,/) 보다 우선순위가 높아져버리는 모순이 생기기 때문입니다.

 

그럼 이걸 유의한채로 생각해보면 연산자가 나올땐 위의 내용처럼 처리해주면 되고, 괄호가 나올땐 '(' 일땐 push ')' 일땐 '(' 를 만날때까지 pop 해주면 됩니다.

 

문자를 만났더라면 그냥 출력해주면 되고요.

 

/*JAVA IO Template Reference : 류호석*/

import java.io.*;
import java.lang.reflect.Array;
import java.lang.reflect.ParameterizedType;
import java.nio.charset.StandardCharsets;
import java.util.*;

import static java.lang.Math.*;

public class Main {
    static FastReader scan = new FastReader();
    //정답은 sb에 append 를 사용하여 출력
    //만약 개행까지 출력하고 싶으면 append('\n')을 추가
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        input();
    }
    static void input(){
        String str = scan.next();
        Stack<Character> st = new Stack<>();

        for(int i=0;i<str.length();i++){
            if(str.charAt(i)=='+' || str.charAt(i)=='-'){
                while(!st.empty() && (st.peek()=='+' || st.peek()=='-' || st.peek()=='*' || st.peek()=='/')){
                    System.out.print(st.peek());
                    st.pop();
                }
                st.add(str.charAt(i));
            }
            else if(str.charAt(i)=='*' || str.charAt(i)=='/'){
                while(!st.empty() && (st.peek()=='*' || st.peek()=='/')){
                    System.out.print(st.peek());
                    st.pop();
                }
                st.add(str.charAt(i));
            }
            else if(str.charAt(i)=='(')
                st.add(str.charAt(i));
            else if(str.charAt(i)==')'){
                while(!st.empty() && st.peek()!='('){
                    System.out.print(st.peek());
                    st.pop();
                }
                st.pop();
            }
            else
                System.out.print(str.charAt(i));
        }
        while(!st.empty()){
            System.out.print(st.peek());
            st.pop();
        }
    }
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;
        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}