백준 1918번 - 후위 표기식 (Java 8)

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

1918번: 후위 표기식

코드:

스택 사용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static Stack<Character> stack = new Stack<>();
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        //식 읽기, 저장할 배열 생성
        String postfixExpression = br.readLine();

        //알파벳은 큐에, 연산기호는 스택에 넣고, 특정조건일때 답지로 방출
        for (int i = 0; i < postfixExpression.length(); i++) {
            char ch = postfixExpression.charAt(i);

            //연산자 만날때
            if (isOperator(ch)) {
                //이전 연산자가 더 높은 우선순위일 경우
                while (!stack.isEmpty() && priority(stack.peek()) >= priority(ch)) {
                    sb.append(stack.pop());
                }
                stack.push(ch);

            // '('일 때
            } else if (isOpen(ch)) {
                stack.push(ch);

            // ')'일 때, : '(' 만날때 까지 출력하도록 한다.
            } else if (isClose(ch)) {
                while (!stack.isEmpty() && stack.peek() != '(') {
                    sb.append(stack.pop());
                }
                // '(' 만나면 버림 : 해당 괄호 내용들을 어디까지 출력해주는지 알려주는 역할을 하고 버려진다.
                stack.pop();

            // 알파벳은 바로 저장한다.
            } else {
                sb.append(ch);
            }
        }
        while(!stack.isEmpty()){
            sb.append(stack.pop());
        }
        System.out.println(sb);
    }

	//괄호의 우선순위를 낮춤으로써 A*(B+C+D) 와 같은 식에서 첫 +를 만나면 바로 출력되는 상황을 막을 수 있다.
    public static int priority(char ch){
        if(ch == '(' || ch == ')'){
            return 0;
        }
        if(ch == '+' || ch == '-'){
            return 1;
        }
        // ch == +,- 일 때
        return 2;
    }

    public static boolean isOperator(char ch) {
        if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
            return true;
        }
        return false;
    }
    public static boolean isOpen(char ch) {
        if (ch == '(') {
            return true;
        }
        return false;
    }
    public static boolean isClose(char ch) {
        if (ch == ')') {
            return true;
        }
        return false;
    }
}

 

엄청 오랜 시간을 썼다. 고수들의 인지과정을 파헤쳐보고 싶다.

참고 :

yanghi님 블로그