[BOJ-JAVA] 1918번: 후위 표기식

문제

https://www.acmicpc.net/problem/1918

1918번: 후위 표기식

우리가 보통 수식을 쓸 때 사용하는 중위 표기법을 후위 표기법으로 변환하는 문제이다.

 

문제풀이

백준 문제 설명을 보면 중위 표기법을 후기표기법으로 변환할 때 괄호를 통해 우선 순위를 표시하고 계산하고 있다. 괄호를 이용한 문제의 경우 stack을 통해 해결할 수 있는 경우가 많다.

 

다만 stack을 어떻게 적용해서 풀 수 있는지 생각하는게 쉽지 않았다.

 

우선 괄호로 표시하는게 연산자의 우선순위에 따라 달라진다. *, /  > +, -  이런 식으로 *와 /연산이 +, -보다 높은 연산자 우선순위가 주어지게 되는데, 우선순위가 높을 경우 낮은 경우보다 먼저 계산되어야한다. 여기서 착안하여 stack에 연산자를 넣는다고 할 때 stack.peek에 있는 연산자와 우선순위를 비교하여 stack.peek 연산자의 우선순위가 높다면 stack.pop을 통해 연산자를 출력하는 방식으로 계산할 수 있다.

 

피연산자는 바로 출력하고, 연산자의 경우 stack에 담는데, 이때 stack.peek와 우선순위를 비교하여 출력하거나 stack에 담는다. 괄호의 경우, 여는 괄호는 stack에 넣고 닫는 괄호가 나오면 stack.peek의 여는 괄호가 나올 때까지 stack.pop을 하여 출력하면 된다.

 

Java Code

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] postfix = br.readLine().toCharArray();
        Stack<Character> operators = new Stack<>();
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<postfix.length; i++) {
            if('A' <= postfix[i] && postfix[i] <= 'Z') {
                sb.append(postfix[i]);
            }
            else if(postfix[i] == '(') {
                operators.push(postfix[i]);
            }
            else if(postfix[i] == ')') {
                while(!operators.empty() && operators.peek() != '(') {
                    sb.append(operators.pop());
                }
                operators.pop();
            }
            else {
                while(!operators.empty() && priority(operators.peek()) >= priority(postfix[i])) {
                    sb.append(operators.pop());
                }
                operators.push(postfix[i]);
            }

        }
        while(!operators.empty()) {
            sb.append(operators.pop());
        }
        System.out.println(sb);
    }
    static int priority(char c) {
        if( c == '(') {
            return 0;
        }
        else if( c == '+' || c == '-') {
            return 1;
        }
        else  {
            return 2;
        }
    }
}

• 연산자 우선순위를 비교할 때 여는 괄호가 나올 수도 있다. 여는 괄호가 나오면 stack.pop을 하면 안되기 때문에 우선 순위를 가장 낮게 잡는다.