[BOJ][Java]Q1918 - 후위 표기식

 

1918번: 후위 표기식

중위 표기로 주어진 계산식을 후위표기로 바꾸는 문제이다.

학부생때 배웠던 기억이 진짜 어렴풋이 나서 어떻게든 스택으로 해보려고 삽질 삽질을 하다가

종이 3장 낭비 후 규칙 발견해서 풀었다.

나는 정말 전위중위후위순회 문제가 싫다 ; 

 

생각해낸 과정

Operand의 순서는 입력과 출력에서 바뀌지 않고 있는 것을 보고 힌트를 얻었다.

Operand는 만나자마자 출력하고, Operator를 스택에 넣어 순서를 바꿔주면 된다.

 

---

풀이

주어진 중위순회식을 한글자씩 now에 저장하며 반복문을 돈다.

1. now가 Operand면 출력
2. now가 Operator면
   (stack에 담긴)지나온 연산자들 중 now보다 우선순위가 높은 연산자가 나중에 출력되면 안되니까, 
   stack에서 하나씩 peek해서 now보다 우선순위가 높거나 같으면(같을 경우 먼저 등장한 연산자를 먼저 출력해야함) pop하여 출력한다.
   그리고 나서 now를 push해준다.
3. now가 괄호일 경우
   '('이면 stack에 push한다.
   ')'이면 stack에서 '('가 나올때까지 pop하여 출력한다.

괄호도 stack에 들어가므로 우선순위를 " ( , ) < +, - < *, / " 이렇게 설정해줌

안그러면 2번조건에서 (를 출력하니까!

 

---

전체 코드

import java.io.*;
import java.nio.Buffer;
import java.util.*;

public class Main{
    /*[골드3]Q1918 - 후위표기식*/
    final static int OPERAND = 0;
    final static int BRACKET = 1;       //(,)
    final static int OPERATOR_1 = 2;    //+,-
    final static int OPERATOR_2 = 3;    //*,/

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

        Stack<Character> operators = new Stack<>();

        for(int i = 0; i<str.length();i++){
            char now = str.charAt(i);
            int nowType = getType(now);
            switch(nowType){
                case OPERAND:
                    //operand는 그냥 출력함
                    sb.append(now);
                    break;
                case OPERATOR_1:
                case OPERATOR_2:
                    //operator를 만나면 stack에 들어있는 연산자들 차례로 검사해서 now보다 우선순위 높거나 같으면 출력함
                    while(!operators.isEmpty() && getType(operators.peek())>=nowType){
                        sb.append(operators.pop());
                    }
                    //now보다 우선순위 높은 애들 다 나왔으면 now push
                    operators.push(now);
                    break;
                case BRACKET:
                    //'('만나면 push함
                    if(now =='(')   operators.push(now);
                    //')'만나면 '('나올때까지 pop해서 출력함 - 단, 괄호는 출력안함
                    if(now == ')'){
                        while(!operators.isEmpty() && operators.peek() != '('){
                            sb.append(operators.pop());
                        }
                        operators.pop(); //'('도 빼줌
                    }
                    break;
            }
        }
        while(!operators.isEmpty()){
            sb.append(operators.pop());
        }
        System.out.println(sb);
    }
    //연산자인지, 피연산자인지, 괄호인지 구분
    private static int getType(char c){
        if(c=='+'||c=='-')  return OPERATOR_1;
        else if(c=='*'||c=='/') return OPERATOR_2;

        else if(c>='A' && c<='Z') return OPERAND;
        else return BRACKET;
    }

    //c1이 우선이면 true, c2가 우선이면 false
    private static boolean isPrior(char c1, char c2){
        int p1, p2;
        p1 = (c1 == '+' || c1 == '-')? 0:1;
        p2 = (c2 == '+' || c2 == '-')? 0:1;

        if(p1>p2)   return true;
        else    return false;
    }
}