BOJ_1918 : 후위 표기식

👉 문제링크

1918번: 후위 표기식

---

---

🔸 문제 분석 🔸

• 중위 표기식을 후위 표기식으로 변환해 출력한다.
• 입력되는 피 연산자는 알파벳 대문자, 연산자는 "+-*/()"의 6가지가 사용된다.
• 스택 자료구조를 사용해서 후위 표기식으로 변환할 수 있다.

🔸 코드 🔸

import java.io.*;

public class Main {
    private static class MyStack {
        private int pointer;
        private char[] stack;

        public MyStack() {
            this.pointer = 0;
            stack = new char[100];
        }

        public void push(char c) {
            stack[pointer++] = c;
        }

        public char pop() {
            return stack[--pointer];
        }

        public boolean isEmpty() {
            return pointer == 0;
        }

        public char peek() {
            if (pointer == 0) return '\0';
            else return stack[pointer - 1];
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        char[] input = br.readLine().toCharArray(); // A : 65, Z : 90

        MyStack stack = new MyStack();

        for (char c : input) {
            if (c >= 65 && c <= 90) // 입력 문자가 알파벳일 경우
                sb.append(c);
            else { // 입력 문자가 연산자일 경우
                if (c == '+' || c == '-') { // '+' or '-'
                    if (stack.peek() == '*' || stack.peek() == '/') {
                        while (!stack.isEmpty() && stack.peek() != '(') {
                            sb.append(stack.pop());
                        }
                    } else if (stack.peek() == '+' || stack.peek() == '-')
                        sb.append(stack.pop());
                    stack.push(c);
                } else if (c == '*' || c == '/') { // '*' or '/'
                    if (stack.peek() == '*' || stack.peek() == '/') {
                        sb.append(stack.pop());
                    }
                    stack.push(c);
                } else if (c == '(') { // '('
                    stack.push(c);
                } else { // ')'
                    while (!stack.isEmpty()) {
                        char p = stack.pop();
                        if (p == '(') {
                            break;
                        }
                        sb.append(p);
                    }
                }
            }
        }
        while (!stack.isEmpty())
            sb.append(stack.pop());
        bw.write(sb.toString());
        bw.flush();
    }
}

🔸 코드 해석 🔸

• 라이브러리의 스택은 효율이 조금 안좋다고 알고 있어서 직접 필요한 기능만 추가한 MyStack 클래스를 만들었다.
  • push, pop, 원소 유무 확인, 가장 최근 원소 확인의 기본 기능만 구현했다.
• 입력된 중위 표기식은 char배열로 변환해 input에 저장했다.
• 문자 하나씩 검사하며 계산 후 결과를 출력한다.
  • 알파벳은 아스키코드 값을 확인해서 A부터 Z까지는 바로 출력을 위해 StringBuilder에 저장한다.
  • '+'와 '-'는 직전에 같은 레벨의 연산자가 있었으면 스택에서 꺼내 출력하고, '*'와 '/'가 있었다면 여는 괄호를 만나거나 스택이 모두 빌 때까지 모든 원소를 꺼내서 출력한다.
    • 그 후 방금 입력된 원소를 스택에 추가한다.
  • '*'와 '/'는 같은 레벨의 연산자가 있으면 꺼내서 출력하고, 방금 입력된 원소를 스택에 추가한다.
  • 여는 괄호는 바로 스택에 추가한다.
  • 닫는 괄호는 여는 괄호를 만날 때 까지 연산자들을 스택에서 꺼내 출력한다.
• 입력된 모든 문자를 처리했으면, 스택에 남은 연산자를 모두 꺼내서 출력한다.

---

🔸 end 🔸

• 스택을 직접 구현한 건 거의 없었는데, 좋은 연습이 된 것 같다.
  • 특히 당장 push할 때 값을 저장할 인덱스를 pointer값으로 설정했는데, pop과 peek할때는 -1이 되어야 하는 걸 모르고 잘못 사용해서 오류가 났었다.
• 골드 2치고는 기본적인 자료구조라 쉽게 풀린 것 같다. 다만 정답률이 낮은 이유와 같은 것 같은데, 반례를 찾는게 너무 번거로워서 테스트 케이스를 그냥 넣어보는 식으로 오류를 잡은 것 같다.
  • +-는 추가 조건 2개, */는 추가조건 1개 라는 위 코드의 결과 같이 디테일한 확인이 필요했다.