백준 1918 - 후위표기식

solved.ac 백준 골드문제 포스팅

문제

후위표기식

• 연산자 우선순위 기준으로 연산자를 스택에 PUSH 또는 기존 스택에 있던 연산자를 POP 하여 후위표기식 작성
• 컴퓨터가 계산하는 방식

연산자 우선순위

문제

기존에 자료구조 시간에 스택 계산기를 만든 경험을 떠올리며 문제를 풀었다.
하나의 스택과 StringBuilder를 이용하여 피연산자는 StringBuilder에 append하고
연산자가 나올 경우 우선순위에 따라 규칙을 정해 Stack에 Push Pop 하였다.

연산자를 A라고 하면, A보다 높거나 같은 우선순위의 연산자들은 모두 POP하여
StringBuilder에 append하고, A를 스택에 Push하는 기본적인 개념이다.
괄호의 경우 예외적으로 append하지 않는다.

코드 - JAVA

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


class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        Stack<Character> stack = new Stack<>();
        StringBuilder str = new StringBuilder();
        for(int i=0; i<input.length(); i++){
            if(input.charAt(i)=='('){ // 괄호 예외처리
                stack.push(input.charAt(i));
            }else if(input.charAt(i)==')'){
                while(stack.peek()!='('){
                    str.append(stack.pop());
                }
                stack.pop();
            }else if(input.charAt(i)>='A'&&input.charAt(i)<='Z'){
            //피연산자는 append
                str.append(input.charAt(i));
            }else{
                if(input.charAt(i)=='+'||input.charAt(i)=='-'){
                //우선순위가 상대적으로 낮은 두 연산자
                    if(!stack.isEmpty()){
                        while (stack.peek()!='('){
                            str.append(stack.pop());
                            if(stack.isEmpty())
                                break;
                        }
                    }
                    stack.push(input.charAt(i));
                }else if(input.charAt(i)=='*'||input.charAt(i)=='/'){
                //우선순위가 젤 높은 연산자
                    if(!stack.isEmpty()){
                        while(stack.peek()=='*'||stack.peek()=='/'){
                            str.append(stack.pop());
                            if(stack.isEmpty())
                                break;
                        }
                    }
                    stack.push(input.charAt(i));
                }
            }
        }
        while(!stack.isEmpty())
        //반복문이 끝나면 stack에 남아있는 연산자 append
            str.append(stack.pop());
        System.out.print(str.toString());
    }
}

후기

빠른 시간안에 풀려고 모든 처리를 조건문으로 수행하였는데, 사실 switch로 수행하는게 더 맞는 선택이라 생각이 든다.