[ 알고리즘 ] 백준 1918번 후위표기식

백준 1918번 후위표기식

문제 링크

이 문제는 Stack을 이용하는 문제로 평소 학교 공부에서도 많이 풀어보았다고, 생각해서 쉽게 풀 수 있을 것이라 생각했는데 쉽지 않았다.

결국은 다른 사람의 답을 참고하여 해결하였다.

생각해보니 평소에는 후위표기식으로 표현된 식을 계산하는 문제를 많이 풀어보았지, 주어진 식을 후위표기식으로 변환을 시키는 코드를 짜본 적은 없는 것 같다.

문제 풀이

입력받은 문자열을 차례로 비교하는데 총 네가지의 경우가 있다.

1. 알파벳
2. 연산자
3. 열린 괄호
4. 닫힌 괄호

각 경우에 따라서 출력하거나 스택에 넣거나, 스택에 있는 것을 꺼내주는 식으로 해결한다.

먼저

1. 알파벳인 경우에는 그냥 바로 출력해준다. 나는 그냥 StringBuilder를 하나 만들어서 거기다 계속 append해줬다.

2. 연산자인 경우 :
   연산자인 경우가 조금 복잡한데 이 문제에서 연산자는 아래의 네가지가 나온다.
   +, -, *, /
   여기서 곱하기와 나누기는 더하기와 빼기보다 우선순위가 높기 때문에 precedenceMap이라는 것을 만들어 주어서 그 안에 우선순위값을 저장해놓고 비교해주었다.
   이 후, 연산자가 들어왔을 때는 이 때

   • stack이 비었거나
   • stack의 top이 열린 괄호, 즉 ( 이거나
   • stack의 top 보다 지금 들어오는 연산자의 우선순위가 더 높을 때

   stack에 연산자를 push해준다.

   위에 해당하지 않는 경우에는 해당될 때까지 top을 pop해준다음 값을 push해준다.

3. 열린괄호인 경우에는 바로 stack에 push한다.

4. 닫힌괄호인 경우에는
   stack의 top이 열린괄호 이거나 stack이 빌 때까지 pop하여 출력해준다.

위의 방법을 이용해 모든 문자열을 탐색하고 나면, 마지막으로 stack 내부에 남아있는 값을 출력해준다.

---

설명이 조금 복잡하지만 이 분의 영상을 보면 이해가 빠르다.

내가 짠 코드

package Algorithms;

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

/**
 * https://www.acmicpc.net/problem/1918
 * 백준 1918 후위표기
 */
public class Baekjoon1918 {
    private static Map<Character, Integer> precedenceMap = new HashMap<>();

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

        String input = br.readLine().trim();

        initPrecedenceMap();
        Stack<Character> stack = new Stack<>();

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            //알파벳
            if(Character.isAlphabetic(c)){
                sb.append(c);
                continue;
            }
            // 여는 괄호일 때
            if(c =='('){
                stack.push(c);
                continue;
            }

            //닫는 괄호일 때
            if(c==')'){
                while(!stack.isEmpty() && stack.peek() != '('){
                    sb.append(stack.pop());
                }
                if(!stack.isEmpty() && stack.peek() == '('){
                    stack.pop();
                }
                continue;
            }

            //연산자 일때
            while(!stack.isEmpty() && ( precedenceMap.get(stack.peek()) >= precedenceMap.get(c))){
                sb.append(stack.pop());
            }
            stack.push(c);
        }

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

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

    private static void initPrecedenceMap() {
        precedenceMap.put('+', 1);
        precedenceMap.put('-', 1);
        precedenceMap.put('*', 2);
        precedenceMap.put('/', 2);

    }


}