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

<문제>

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

1918번: 후위 표기식

<풀이>

1. 어떤 접근으로 문제를 접근하려고 했는지

    1) A ~ Z 문자(피연산자)일 경우 출력한다.

    2) 이때 스택이 비어있으면 그냥 스택에 연산자를 push 한다.

    3) 스택이 비어있지 않을경우 스택의 최상단 연산자와 들어오려는 연산자의 우선순위를 비교한다. 

    4) 만약 스택의 최상단보다 들어오려는 연산자의 크기가  들어오려는 연산자가 스택의 최상단에 있는 연산자보다 크기가 같거나 작을 때까지 본인보다 우선순위가 큰 연산자는 출력한다. 

    5) 위 과정에서 괄호는 예외처리를 해야하는데 여는 괄호일 경우 그냥 스택에 바로 넣는다. 
    6) 닫는 괄호일경우 여는 괄호가 나올 때까지 출력하고 여는 괄호는 출력하지 않고 스택에서 pop 시킨다.

2. 문제를 해결하기 위한 기능

연산자 우선순위 계산하는 기능

연산자를 스택에 조건에 맞게끔 넣는기능

 

<문제를 풀면서 어려웠던 점>

당연히 괄호의 연산우선순위를 제일 높게 뒀는데 이렇게 뒀을 경우 제대로 문제가 해결되지 않았다. 디버깅을 통해 여는 괄호 같은 경우 무조건 닫는 괄호가 나와야지 여는 괄호 전까지 다 pop을 해야 해서 괄호의 연산자 우선순위 크기를 제일 작게 뒀다.

<코드>

import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        String s = br.readLine();
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if((int)'A'<= (int)c && (int)c <= (int)'Z' ) {
                sb.append(c);
            }
            else {
                if(c == ')') {
                    while(!stack.isEmpty() && stack.peek() != '(') {
                        sb.append(stack.pop());
                    }
                    stack.pop();
                }
                else if(c == '(') {
                    stack.push(c);
                }
                else {
                    while(!stack.isEmpty() && checkPriority(stack.peek()) >= checkPriority(s.charAt(i))) {
                        sb.append(stack.pop());
                    }
                    stack.push(s.charAt(i));
                }
            }
        }
        while(!stack.isEmpty()) {
            if(stack.peek() != '(') sb.append(stack.pop());
        }
        System.out.println(sb);
    }
    public static int checkPriority(char c) {
        if(c == '+' || c == '-') return 1;
        else if(c == '*' || c == '/' ) return 2;
        return 0;
    }
}