[JAVA] 백준 후위표기식

www.acmicpc.net/problem/1918

 

중위표기식에서 후위표기식으로 변환하는 문제이다.

중위표기식에서 후위표기식으로 변환

문제만 읽으면 마치 "구현"문제처럼 보인다.

하지만, 문제의 지시내용처럼 괄호를 삽입하고 그에따라서 연산자를 옮기는 방식으로는 풀 수 없다.

 

괄호의 삽입 위치와 정규식의 불규칙적인 특성때문에 삽입하는데, 어려움이 있다.

 

따라서 아래와 같은 방법을 사용한다.

 

1. 피연산자 즉, 대문자 알파벳은 무조건 결과 문자열에 즉시 추가해줍니다.

 

2. 연산자일 경우는 아래와 같이 3가지 경우가 있습니다.

i) 괄호 안에 있는 연산을 제일 먼저 실행하기 때문에 현재 인덱스에 있는 연산자가 '('라면 바로 스택에 넣어줍니다.

ii) '+', '-', '*', '/' 연산자가 등장할 경우 스택에 현재 연산자보다 우선순위가 높거나 같은 기호들은 전부 결과 문자열에 추가해줍니다.

a) '*'와 '/'가 '+'와 '-'보다 우선순위가 높습니다.

b) 따라서, '*'와 '/'가 등장할 경우, 스택이 비거나 혹은 스택의 top이 우선순위가 낮은 기호가 나올 때까지 결과 문자열에 추가해줍니다.

c) '+'와 '-'보다 우선순위가 낮은 기호는 없으므로 스택이 비거나 스택의 top이 괄호의 시작인 '('이 나올 때까지 결과 문자열에 추가해줍니다.

iii) ')'가 등장할 경우 괄호의 끝이므로 스택의 top이 '('가 나올 때까지 결과 문자열에 추가해주고 마지막으로 '(' 또한 pop 해줍니다.

 

3. 반복문을 다 돌고도 스택이 비어있지 않은 경우 남은 연산자들을 결과 문자열에 추가해줍니다.

 

출처: https://jaimemin.tistory.com/828 [꾸준함]

import java.util.*;
import java.io.*;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String str=br.readLine();
        int n=str.length();
        StringBuilder sb=new StringBuilder();
        Stack<Character> st=new Stack<>();

        // 연산자별 우선순위 저장
        HashMap<Character, Integer> map=new HashMap<>();
        map.put('(', 0);
        map.put('+', 1);
        map.put('-', 1);
        map.put('*', 2);
        map.put('/', 2);

        for(int i=0;i<n;i++) {
            char ch=str.charAt(i);
            // 알파벳은 바로 출력
            if('A'<=ch && ch<='Z') sb.append(ch);
            else {
                switch(ch) {
                    case '(':
                        st.push(ch);
                        break;
                    case ')':
                        // 여는 괄호가 나올 때까지 출력
                        while(!st.isEmpty() && st.peek()!='(') {
                            sb.append(st.pop());
                        }
                        // 여는 괄호 pop
                        if(!st.isEmpty() && st.peek()=='(') st.pop();
                        break;
                    default: // 연산자
                        // top우선순위 < ch우선순위여야 push 가능
                        while(!st.isEmpty() && map.get(st.peek())>=map.get(ch))
                            sb.append(st.pop());
                        st.push(ch);
                }
            }
        }
        // 남은 연산자들 모두 출력
        while(!st.isEmpty()) sb.append(st.pop());

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