[Java] 백준 1918번 후위 표기식 - 스택

https://mygumi.tistory.com/181

백준 1918번 후위표기식 :: 마이구미

스택 구조를 활용해 중위 표기식을 후위 표기식으로 바꾸는 문제.

각 operator의 우선순위를 매겨, 스택에서 자신보다 우선순위가 낮은 것을 만날때까지 pop해서 붙이는 것은

생각도 못함...

package class4;

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

public class g3_1918{
    public static void main(String[] args){
        FastScanner fs = new FastScanner();
        PrintWriter pw = new PrintWriter(System.out);

        List<Character> sb = new LinkedList<>();
        Stack<Character> st = new Stack<>();

        String str = fs.next();
        for (char c : str.toCharArray()){
            switch (c){
                case '+':
                case '-':
                case '*':
                case '/':
                    int pri = prior(c);
                    while (!st.empty() && prior(st.peek()) >= pri){
                        sb.add(st.pop());
                    }
                    st.push(c);
                    break;
                case '(':
                    st.push(c);
                    break;
                case ')':
                    while (st.peek() != '('){
                        sb.add(st.pop());
                    }
                    st.pop();
                    break;
                default:
                    sb.add(c);
                    break;
            }
        }

        while (!st.empty()){
            sb.add(st.pop());
        }
        for (Character cc : sb){
            pw.print(cc);
        }
        pw.close();
    }

    static int prior(char c){
        if (c == '*' || c == '/'){
            return 2;
        }
        else if (c == '+' || c == '-'){
            return 1;
        }
        // '(' ')'
        return 0;
    }

    static void sort(int[] a){
        ArrayList<Integer> L = new ArrayList<>();
        for (int i : a) L.add(i);
        Collections.sort(L);
        for (int i = 0; i < a.length; i++) a[i] = L.get(i);
    }

    static class FastScanner{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");
        String next(){
            while (!st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt(){
            return Integer.parseInt(next());
        }

        int[] readArray(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = nextInt();
            return a;
        }

        long nextLong(){
            return Long.parseLong(next());
        }
    }
}