[백준, 자바] 1918번 - 후위 표기식

jinvicky·2023년 12월 14일

ALG

목록 보기

17/62

후위 표기법

중위 표기식을 후위 표기식으로 바꾸는 방법

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

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

        String str = br.readLine();
        Stack<Character> stack = new Stack<>();

        Map<Character, Integer> map = new HashMap(); //우선순위 store
        map.put('(', 0); //미추가시 NullPointerException
        map.put(')', 0); //미추가시 NullPointerException
        map.put('+', 1);
        map.put('-', 1);
        map.put('*', 2);
        map.put('/', 2); // */가 +-보다 우선순위 값이 더 커야 한다.

        for (int i = 0; i < str.length(); i++) {
            char currentChar = str.charAt(i);

            if (currentChar >= 'a' && currentChar <= 'z' || currentChar >= 'A' && currentChar <= 'Z') {
                sb.append(currentChar);
            } else if (currentChar == '(') {
                stack.add(currentChar);
            } else if (currentChar == ')') {
                while (!stack.isEmpty() && stack.peek() != '(') {
                    sb.append(stack.pop());
                }
                stack.pop(); //마지막으로 (를 pop()
            } else { // 사칙연산자.
                while(!stack.isEmpty() && map.get(stack.peek()) >= map.get(currentChar)) {
                    sb.append(stack.pop());
                }
                stack.add(currentChar);
            }
        }

        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }

        System.out.println(sb.toString());
    }

}

결과

오답
(결과 상관없이 이 벨로그에 올린 모든 알고리즘 코드는 정답이다.)

풀이

내가 틀린 이유는 연산자의 우선순위에 따라 다른 로직을 잘 처리하지 못했기 때문이다.
스택이 비었을 경우는 사실 스택에 넣는 것 외에는 할 일이 없다.

핵심1 : 연산자들 간의 우선순위에 따른 pop()과 push()

스택이 !isEmpty()라면 스택의 top과 currentChar의 우선순위를 비교한다.

큰 경우 : 우선순위가 높은 것부터 진행하므로 pop() 해야 함.

같은 경우 : 앞에서부터 순서대로 진행하므로 pop() 해야 함.

핵심2 : ()처리

(는 무조건 스택에 push()한다.
)는 (를 만날때까지 계속 stack에서 pop()한다.

우선순위 계산

() > */ > +- 순으로 우선순위가 높다. 이것을 int값으로 표현한다면 if문에서 더 쉽게 비교할 수 있다.

참고 추천

https://velog.io/@yanghl98/백준-1918-후위-표기식-JAVA자바
위 사이트가 switch문을 써서 깔끔히 짰다.

분기처리를 잘해서 알파벳인지 체크하는 조건문조차 없애고 default로 처리했으며,
우선순위의 경우 함수로 처리해서 순위별로 int값을 리턴하도록 했다.

Q. 의문

왜 (,)를 우선순위 저장하는 map에 추가하지 않으면 런타임 에러가 나는 지 알아내지 못했다.

 Map<Character, Integer> map = new HashMap(); //우선순위 store
        map.put('(', 0); //미추가시 NullPointerException
        map.put(')', 0); //미추가시 NullPointerException