백준 1918번 :: 후위 표기식

 

이제 골드 문제도 하나씩 도전해보고 있는 요즘

 

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

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

        String infix = br.readLine();
        char[] chars = infix.toCharArray();

        Stack<Character> stack = new Stack<>();
        StringBuilder answer = new StringBuilder();

        for (char aChar : chars) {
            if (aChar >= 'A' && aChar <= 'Z') {
                answer.append(aChar);
            } else if (aChar == '(') {
                stack.push(aChar);
            } else if (aChar == ')') {
                // 괄호가 제대로 닫힐 때까지 스택에서 연산자를 꺼내 결과에 추가
                while (!stack.isEmpty() && stack.peek() != '(') {
                    answer.append(stack.pop());
                }
                // 앞에 있는 여는 괄호 제거
                stack.pop();
            }
            // * / 연산자일 경우
            else if (aChar == '*' || aChar == '/') {
                // 스택에 이미 우선순위가 더 높은 연산자가 있다면 결과에 추가
                while (!stack.isEmpty() && (stack.peek() == '*' || stack.peek() == '/')) {
                    answer.append(stack.pop());
                }
                stack.push(aChar);
            }
            // 그 외 연산자
            else {
                // 스택에 이미 우선순위가 더 높은 연산자가 있다면 결과에 추가
                while (!stack.isEmpty() && stack.peek() != '(') {
                    answer.append(stack.pop());
                }
                stack.push(aChar);
            }
        }
        // 스택에 남아있는 모든 연산자를 결과에 추가
        while (!stack.isEmpty()) {
            answer.append(stack.pop());
        }

        System.out.println(answer);
    }
}

 

스택 문제라고 했으니 스택으로 접근해보려고 했지 스택 문제라는걸 몰랐다면? 아마 접근도 못했을 것 같다..

 

1. 처음 생각한 방법 : 입력받은 값에 괄호가 있는지 여부에 따라 경우를 나누려고 했는데 시도해보다가 방향이 잘못된듯 하여 패스

 

2. 스택으로 접근 시도

 - 연산자를 담을 스택과 답을 담을 배열을 만들고

 - 어떤 연산자가 들어오는지에 따라 스택에 push를 할 것인지 pop을 하여 답 배열에 add 해줌 

 

3. 연산자의 우선순위를 따져야함

 - * 나 / 일 경우, 바로 꺼내면 됨 ( 우선순위가 높으니까)

 - 근데 그게 아니라면 우선순위가 낮기 때문에 열린 괄호가 있을 때까지 스택에서 pop

 

4. 처음에 답을 담을 배열을 만들었다가 StringBuilder에 바로 넣기로 결정함 ( 시간에는 차이 없는 듯? 메모리만 살짝 줄었음)