[백준 1918번][Java] 후위 표기식 - 스택, 후위 표기식 변환 알고리즘

 

www.acmicpc.net/problem/1918

1918번: 후위 표기식

 

 

dblab.duksung.ac.kr/ds/pdf/Chap05.pdf

 

위 pdf에 모든 알고리즘 설명이 들어가 있다.

 

꽤 유명한 문제였던 듯하다. 하지만 처음 문제를 접하면 풀기 쉽지 않을 듯한 문제다.

 

 

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
//        InputReader reader = new InputReader();
        InputReader reader = new InputReader("testcase.txt");
        String inOrder = reader.readLine();
        System.out.println(solve(inOrder));;
    }

    private static String solve(String inOrder) {
        Stack<Character> stack = new Stack<>();
        String ret = "";
        for (int i = 0; i < inOrder.length(); i++) {
            char c = inOrder.charAt(i);
            //문자가 나오는 경우
            if(c >= 'A' && c <= 'Z') {
                ret += c;
                continue;
            }
            //닫는 괄호가 나오는 경우
            if(c == ')') {
                while(true) {
                    if(stack.peek() != '(') ret += stack.pop();
                    else {
                        stack.pop(); //여는 괄호 제거
                        break;
                    }
                }
                continue;
            }
            //연산자끼리 우선순위 비교해서 pop 해야 하는 경우. 반드시 하나만 pop하라는 보장은 없다
            while(!stack.isEmpty() && stack.peek() != '(' && c != '('
                    && operatorPriority(stack.peek()) >= operatorPriority(c)) {
                ret += stack.pop();
            }
            stack.push(c);
        }

        while(!stack.isEmpty()) ret += stack.pop();
        return ret;
    }

    private static int operatorPriority(char c) {
        if(c == '*' || c == '/') return 2;
        return 1;
    }

}
class InputReader {
    private BufferedReader br;

    public InputReader() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    public InputReader(String filepath) {
        try {
            br = new BufferedReader(new FileReader(filepath));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    public List<Character> readLineIntoCharList() throws IOException {
        List<Character> l = new ArrayList<>();
        while(true) {
            int readVal = br.read();
            if(readVal == '\n' || readVal == -1) break;
            l.add((char)readVal);
        }
        return l;
    }

    public boolean ready() throws IOException {
        return br.ready();
    }

    public String readLine() throws IOException {
        return br.readLine();
    }
    public int readInt() throws IOException {
        return Integer.parseInt(readLine());
    }
    public Long readLong() throws IOException {
        return Long.parseLong(readLine());
    }
}