백준 1918번 후위 표기식 (JAVA)

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

1918번: 후위 표기식

 

대략적인 개념은 가지고 있었는데 막상 구현하려하니 힘들었습니다.

저는 스택을 이용해 후위 표기법을 표현하였습니다.

먼저 우선순위는 (+ , -) < (* , /)입니다.

저는 다음과 같은 과정을 가지고 수행하였습니다.

1. 알파벳의 경우 StringBuilder에 바로 넣어주었습니다.

2. Stack의 top이 현재 연산자보다 우선순위가 낮은 연산자를 만날 때까지 pop하고 StringBuilder에 넣어주었습니다.

   그리고 현재 연산자를 Stack에 넣어주었습니다. ( 만약 중간에 '(' 연산자가 나온다면 멈춥니다. )

3. '('를 만나면 바로 Stack에 넣어주었습니다.

4. ')'를 만나게 되면 ')'까지 꺼내주었습니다.

5. 마지막으로 남아있는 연산자를 모두 StringBuilder에 넣어주었습니다.

시간복잡도 : O(n)

 

package BOJ.ETC;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

public class BOJ_1918 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String command = br.readLine();
        StringBuilder result = new StringBuilder();
        Deque<Character> operation = new ArrayDeque<>();
        for (int i = 0; i < command.length(); i++) {
            char now = command.charAt(i);
            if (isAlpha(now)) {
                result.append(now);
                continue;
            }
            if(operation.isEmpty() || now == '('){
                operation.offerLast(now);
                continue;
            }
            if(now == '+' || now == '-'){
                while(!operation.isEmpty() && operation.peekLast() != '('){
                    result.append(operation.pollLast());
                }
                operation.offerLast(now);
            }
            if(now == ')'){
                while(!operation.isEmpty() && operation.peekLast() != '('){
                    result.append(operation.pollLast());
                }
                operation.pollLast();
                continue;
            }
            if(now == '*' || now == '/'){
                while(!operation.isEmpty() && (operation.peekLast() == '*' || operation.peekLast() == '/') && operation.peekLast() != '('){
                    result.append(operation.pollLast());
                }
                operation.offerLast(now);
            }
        }
        while (!operation.isEmpty()) {
            result.append(operation.pollLast());
        }
        System.out.println(result.toString());
    }

    private static boolean isAlpha(char ch) {
        if (ch >= 'A' && ch <= 'Z') {
            return true;
        }
        return false;
    }
}

 

 

참조

https://woongsios.tistory.com/288