백준 1918. 후위 표기식

문제 링크

난이도	정답률(_%)
Gold 4	30.919%

설계

고생한 점

• 역시 시간복잡도 계산하기 어렵다 🙄

복잡도 계산

문자열 길이를 n이라고 함. 최대 길이 100.

시간복잡도

• 후위 연산으로 변환 할 때 n번 회전하면서, 연산자일 경우 최대 Stack 길이만큼 연산자를 비교하는 과정이 a번 들어갈 수 있음 (a < n)

공간복잡도

• 입력받은 연산식 char형 길이 n
• 후위 연산식 char형 길이 n
• 후위 연산자가 쌓이는 Stack

풀이

• 중위 연산식 문자열을 후위연산식으로 변환한다.

변환 과정 (모든 문자열을 돌 때까지 1-3 반복)

1. 피연산자일 경우 연산식에 추가
2. 스택이 비었거나 (일 경우 연산자 Stack에 추가
3. 연산자일 경우
   • )가 아닌 연산자의 경우 연산자 Stack의 값과 연산자의 우선순위를 비교한다.
     • 우선순위가 높은 경우, Stack에 연산자를 넣음.
     • 우선순위가 낮거나 같은 경우, 현재 연산자의 우선순위가 높을 때까지 연산자 Stack에서 값을 pop하여 후위 연산식에 추가하고, 연산자 Stack에 현재 연산자를 넣는다.
   • 연산자가 )인 경우
     • 연산자 Stack에서 ( 를 만날 때까지 값을 pop하여 후위 연산식에 추가한다.
4. 모든 연산식을 다 돌았으면 Stack에 남은 연산자들을 후위 연산식에 추가한다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        char[] infixOperations = br.readLine().toCharArray();
        String postfixOperations = makePosfix(infixOperations);

        bw.write(postfixOperations);
        bw.flush();
        bw.close();
    }

    public static String makePosfix(char[] infixOperations) {
        StringBuilder postfixOperations = new StringBuilder();
        Stack<Character> operators = new Stack<>();

        for (char operation : infixOperations) {
            if (operation >= 'A' && operation <= 'Z') {
                postfixOperations.append(operation);
                continue;
            }

            if (operators.isEmpty() || operation == '(') {
                operators.push(operation);
                continue;
            }

            while (!operators.isEmpty()) {
                if (operation != ')') {
                    int priorityGap = getPriority(operators.peek()) - getPriority(operation);

                    if (priorityGap < 0) {
                        break;
                    }
                }

                char operator = operators.pop();

                if (operator == '(') {
                    break;
                }

                postfixOperations.append(operator);
            }

            if (operation == ')') {
                continue;
            }

            operators.push(operation);
        }

        while (!operators.isEmpty()) {
            postfixOperations.append(operators.pop());
        }

        return postfixOperations.toString();
    }

    public static int getPriority(char operator) {
        int priority = 0;

        if (operator == '*' || operator == '/') {
            return 1;
        }

        if (operator == '(') {
            return -1;
        }

        return priority;
    }
}