[백준] JAVA 자바 : 후위 표기식 (1918번)

---

중위 표기식을 후위 표기식으로 바꾸는 문제이다.
분명 이거 작년에 자료구조 수업 들으면서 배웠는데… 하 알고리즘이 기억이 안 나서 한 시간 정도 애 먹었다…

아니 진짜 바본가 왜 이걸 생각을 못 하지?? 스택은 하나만 써도 충분하고, 알파벳을 만나면 그냥 바로 StringBuilder에 담으면 된다… 알파벳을 굳이 스택에 넣을 필요가 없는데 왜 계속 그걸 붙잡고 있었지?????

그리고 ‘(‘랑 ‘)’를 잘 처리해 줘야 한다… ‘(‘를 만나면 스택에 담지만, 이것을 스택에서 빼는 것은 그 어떤 연산자도 할 수 없고 오로지 ‘)’만이 가능하도록 설정해 주어야 한다. 그렇지 않으면 괄호의 우선순위가 이상해져버림.

‘+’와 ‘-‘는 모든 연산자를, ‘*’와 ‘/’는 ”와 ‘/’만 출력 가능한 것처럼 ‘(‘는 ‘)’만이 pop() 가능한 것.

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

public class Postfix_1918 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Stack<Character> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        
        String str = br.readLine();
        for (int i=0; i<str.length(); i++) {
            char c = str.charAt(i);
            switch (c) {
            case '(': // '('를 만나면
                stack.push(c); // 일단 스택에 넣는다
                break;
            case ')': // ')'를 만나면
                while (stack.peek() != '(') { // '('가 앞에 나온
                    sb.append(stack.pop()); // 모든 연산자를 출력
                }
                stack.pop(); // '(' 제거
                break;
            case '*':
            case '/':
                // '*'나 '/'의 경우, 우선되므로 '+'나 '-'는 출력하지 않고 직전의 '*'와 '/'만 모두 출력한다
                while (!stack.isEmpty() && (stack.peek() == '*' || stack.peek() == '/')) {
                    sb.append(stack.pop());
                }
                stack.push(c); // 자신을 담음
                break;
            case '+':
            case '-':
                // '+'나 '-'의 경우 우선순위가 가장 낮으니 직전의 연산자를 모두 출력한다
                // 그러나 '('가 나오면 멈춘다. 이건 위에서 case ')'에서 처리해야 함!
                while (!stack.isEmpty() && stack.peek() != '(') {
                    sb.append(stack.pop());
                }
                stack.push(c);
                break;
            default: // 알파벳의 경우
                sb.append(c); // 그냥 그대로 출력한다
                break;
            }
        }
        
        // 반복문을 다 돌았는데 남은 연산자가 있다면 모두 출력한다
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        
        System.out.print(sb);
    }

}

사실 이것도 상당히 애 먹었던 문제라서… 시간이 될 때 다시 풀어봐야 할 것 같다.

 

로그인

 

 

작성일자: 2023-09-04