백준 1918 자바 - 후위 표기식 (boj 1918 java)

문제 : boj1918

 

  전공자라면 과제로 한 번씩 해봤을 그 녀석이다. 후위 표기식으로 변환하는건 스택을 활용하면 된다. 실제 계산을 할 필요가 없고, 단순히 중위 표기식을 후위 표기식으로 바꾸기면 하면 되므로 실제 연산 결과를 유지하지 않아도 되서 더 쉽게 짤 수 있다(원래대로라면 'A'~'Z'도 스택에 넣어서 연산자에 따라 실제 연산이 진행되야 하지만, 이 문제의 경우 단순히 화면상에 출력만 하면 되므로). 이 문제와는 관계없지만 후위 표기식을 활용해 실제 계산해서 공학 계산기처럼 동작하는 자바 코드는 여기(깃헙)에 있다(오래전에 짠거라 좀 코드가 안이쁘긴하다). 다음과 같이 동작한다.

INPUT : 23.3 *  (sin3+ 2.5)/ 43.2
OUTPUT : 1.3766071245476987

INPUT : {(tan45  +cos30) - sqrt4 * log100   }/   10
OUTPUT : -0.21339745962155615

INPUT : 5 / {(sin60 - 0.2) -30 * 20}
OUTPUT : -0.008342593965857868

 

 

  다시 문제 풀이로 돌아와서, String을 받아 각 Character를 순서대로 확인하면서 이하의 규칙을 따르면 된다. 이 때 스택에는 '+', '-', '*', '/', '(' 만 유지하면 된다.

1. 'A'~'Z'라면 바로 출력한다. (코드의 19 line)

2. '(' 라면 그냥 스택에 넣는다. (코드의 23 line)

3. ')' 라면 '('를 만날 때 까지 스택에서 빼면서 전부 출력한다. 당연히 '('는 출력하면 안된다. (코드의 27 line)

4. '+', '-', '*', '/' 라면 스택이 비지 않고, '('를 만나지 않을 때 까지 자신보다 연산자 우선순위가 높은걸 전부 빼면서 출력 후, 스택에 넣는다. 이 문제의 경우 단항 연산자가 없고 기본 사칙연산만 있으므로 단순히 현재 보고 있는 Character가 '+'나 '-' 라면 스택이 비거나 '+', '-'를 만날 때 까지 '*'와 '/'를 스택에서 빼서 출력한 후 현재 보고 있는 Character를 스택에 넣어주면 된다. '*', '/'라면 '+', '-'를 만날 때 까지 빼주면서 출력 후, 현재 보고 있는 문자를 넣으면 된다.

5. 모든 Character를 다 봤다면 스택에 남아있는걸 빼주면서 출력한다.

 

 

  예시로 다음과 같은 경우를 보자.

A+B*C/(D-E)

  진행 과정을 순서대로 그려보면 다음과 같다.

 

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    int[] opPriority = new int[50];
    private void init() {
        opPriority['*'] = opPriority['/'] = 1;
        opPriority['('] = opPriority[')'] = -1;
    }
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        init();
        String s = br.readLine();
        StringBuilder sb = new StringBuilder();
        Stack<Character> stk = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c >= 'A') {
                sb.append(c);
                continue;
            }
            if (c == '(') {
                stk.add(c);
                continue;
            }
            if (c == ')') {
                while (stk.peek() != '(') {
                    sb.append(stk.pop());
                }
                stk.pop();
                continue;
            }
            while (!stk.isEmpty() && opPriority[stk.peek()] >= opPriority[c]) {
                sb.append(stk.pop());
            }
            stk.add(c);
        }
        while (!stk.isEmpty()) {
            sb.append(stk.pop());
        }
        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}