ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [ 알고리즘 ] 백준 1918번 후위표기식
    프로그래밍/알고리즘 2019. 5. 2. 15:52

    백준 1918번 후위표기식

    문제 링크

    문제 스크린샷

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

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

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

    문제 풀이

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

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

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

    먼저

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

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

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

      stack에 연산자를 push해준다.

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

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

    4. 닫힌괄호인 경우에는
      stacktop이 열린괄호 이거나 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);
    
        }
    
    
    }
    

    댓글

Designed by Tistory.