백준 1918 자바 - 후위표기식

문제

---

 

 

 

문제해결

---

- 기본 원리는 연산자는 스텍에 저장하고, 피연산자는 바로 출력하는 것이다

1. 피연산자일 경우 바로 출력한다

2. ) 일 경우 (가 나올때까지 스텍에 쌓인 연산자를 출력한다, (는 출력하지 않는다

3. ( 일 경우 무조건 스텍에 집어넣는다

4. ( 를 제외한 연산자를 스텍에 집어넣을때, 맨 위에 있는 연산자보다 우선순위가 높을 경우에는 스텍에 바로 집어넣고, 아닐 경우 우선순위가 더 높은 연산자를 먼저 출력한다

import java.util.Scanner;
import java.util.Stack;

public class B1918 {
    //연산자 우선순위 정하기
    public static int precedence(char c){
        if (c=='(') return 0;
        if (c=='+' || c=='-') return 1;
        else return 2;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();

        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (c>='A' && c<='Z'){
                //연산자가 아닌 경우엔 출력
                System.out.print(c);
            } else if (c==')'){
                //(가 나올때까지 출력
                while (!stack.isEmpty()){
                    char tmp = stack.pop();
                    if (tmp=='(') break;
                    System.out.print(tmp);
                }
            } else if (c=='('){//피연산자가 아닐때
                //(는 무조건 스텍에 집어넣음
                stack.push(c);
            } else {
                //연산자 우선순위가 더 큰경우에만 스텍에 집어넣기
                //우선순위가 같거나 낮은경우 우선 스텍에 있는 연산자 전부 출력 후 집어넣기
                while (!stack.isEmpty() && precedence(stack.peek())>=precedence(c)){
                    System.out.print(stack.pop());
                }
                stack.push(c);
            }
        }
        //스텍에 남아있는 연산자 전부 출력
        while (!stack.isEmpty()){
            System.out.print(stack.pop());
        }
    }
}

 

출처: https://dundung.tistory.com/133