[백준]1918: 후위 표기식 - JAVA

[백준]1918: 후위 표기식

 

www.acmicpc.net/problem/1918

1918번: 후위 표기식

풀이

후위 표기식 문제이다! 개념상으로는 알고 있었는데 구현하는 방법을 까먹어서 예제 입력을 따라가보면서 어떻게 구현할지 생각해 보았고,

 

숫자가 들어오면 그대로 출력하고, 연산자가 들어오면 스택에 담아서 괄호와 우선순위 연산을 하면서 출력해 주면 된다는 결론을 얻엇다.

 

1. 괄호 연산 - 연산자 입력으로 괄호가 들어왔을 때는 다음과 같이 처리한다.

 

case 1) '('괄호가 들어왔을 때

-> 스택에 그대로 담아준다.

 

case 2) ')'괄호가 들어왔을 때

-> '('괄호가 나올 때까지 연산자 스택에 담아둔 연산자를 모두 꺼내어 출력한 후 '('괄호는 출력하지 않고 꺼내준다.

 

case 3) +, -, /, * 연산자가 들어왔을 때

-> 현재 연산자 보다 연산자 스택에 담아둔 연산자의 우선순위가 높거나 같다면 먼저 출력해 주어야 하므로 꺼내어 출력한다.

이때 연산자 스택에는 '('도 들어있을 수 있다. '('를 만나면 더 이상 꺼내면 안되므로 '('의 우선순위를 가장 낮게 설정해준다.

 

2. 연산자 우선순위 결정

*, /의 우선순위가 가장 높으므로 2로 설정했다.

+, -는 *과 /보다는 낮은 1로 설정했다.

( 는 우선순위를 제일 낮은 0으로 설정했다.

 

코드

import java.util.*;
 
public class Main {    
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        char[] calculation = scan.nextLine().toCharArray();
        
        Stack<Character> op = new Stack<>(); // 연산자를 담을 스택
        StringBuilder sb = new StringBuilder();//정답을 담을 문자열
        for(int i = 0; i < calculation.length; i++) {
            // 연산식이 숫자라면 그대로 문자열에 담아준다.
            if(calculation[i] >= 'A' && calculation[i] <= 'Z') sb.append(calculation[i] + "");
            else { //연산식이 숫자가 아니라면
                if(calculation[i] == '(') op.push(calculation[i]);
                else if(calculation[i] == ')') { //'('이 나올때까지 문자열에 담아준다.
                    while(!op.isEmpty() && op.peek() != '(') {
                        sb.append(op.pop()); //괄호가 아니면 연산자를 꺼내어 문자열에 담는다.
                    }
                    if(!op.isEmpty()) op.pop(); //'('연산자를 꺼내준다.
                }
                else { // + - / * 연산자 일경우
                    while(!op.isEmpty() && precedence(op.peek()) >= precedence(calculation[i])) {
                        sb.append(op.pop());
                    }
                    op.push(calculation[i]);
                }
            }
        }
        //스택에 있는 남은 연산자를 모두 꺼낸다.
        while(!op.isEmpty()) {
            sb.append(op.pop());
        }
        System.out.println(sb);
    }
   
    public static int precedence(char op) {
        if(op == '*' || op == '/') return 2;
        else if(op == '+' || op == '-') return 1;
        else return 0; //스택 안에는 '('도 들어올 수 있다. 하지만 '('는 꺼내져서는 안되기 때문에 제일 낮은 값을 반환하도록 한다.
    }
}