[백준] 1918번 후위 표기식 JAVA (자바) 풀이

문제 1918번

 : 수식은 일반적으로 3가지 표기법으로 표현

 : 연산자가 피연산자 가운데 위치하는 중위 표기법  ( 예: a+b )

   연산자가 피연산자 앞에 위치하는 전위 표기법 ( 예: +ab )

   연산자가 피연산자 뒤에 위치하는 후위 표기법 ( 예: ab+ )

 :  후위 표기식 장점은 순서를 적절히 조절하여 순서를 정해줄 수 있어서 괄호 등도 필요 없게 된다

 
:  중위 표기식을 후위 표기식으로 바꾸는 방법          a+b*c

    연산자의 우선순위에 따라 괄호로 묶기                  (a+(b*c))

    괄호 안의 연산자를 괄호의 오른쪽으로 옮기기      (a+bc*)

    마지막으로 또 +를 괄호의 오른쪽으로 고치기        abc*+

 
   예시 ) A+B*C-D/E   →    결과: ABC*+DE/- 

 [입력]

  

 :  첫째 줄에 중위 표기식이 주어진다
   
 :  피연산자는 알파벳 대문자, 알파벳 중복 X

 

 :  그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 * 생략금지

 

 :  표기식은 알파벳 대문자와 +, -, *, /, (, ) 로 이루어진다 (길이는 100을 넘지 X)

 [출력]

 :  첫째 줄에 후위 표기식으로 바뀐 식을 출력

 [문제이해]

 

 : 스택에는 괄호와 연산자만 넣는다

 

 : 알파벳은 그때그때 바로바로 출력한다

 

 예)  입력 = A - B  * ( C + D ) 인 경우

 

입력순서
A 입력	- 입력	B 입력	* 입력	( 입력	C 입력	+ 입력	D 입력	) 입력	끝

스   택
						+ [( < +]	+
				(	(	(	(
			* [- < *]	*	*	*	*	*
	-	-	-	-	-	-	-	-

결    과
A	A	A B	A B	A B	A B C	A B C	A B C D	A B C D +	ABCD+*-

 

 [스택 연산]

 

push(e)	스택의 맨 위에 요소 e 추가
pop()	스택의 맨 위 요소를 삭제
peek(s)	스택의 맨 위 요소를 삭제하지 않고 반환
top()	스택 맨 위에 있는 데이터 값 반환
isEmpty()	스택에 원소가 없으면 'True', 있으면 'False' 값 반환
isFull()	스택에 원소가 없으면 'False', 있으면 'True' 값 반환

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
      static int priority(char c){
        if(c=='+' || c=='-')
            return 1;
         else if(c=='*' || c=='/')
             return 2;
         else
             return 0;
     }
     public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Stack<Character> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
         
        String s = br.readLine();
         
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            
            if(c >= 'A') 
                sb.append(c);
                
            else if(c== '(')
                    stack.push(c);
            
            
             else if(c==')'){
                    while(stack.peek()!='('){ //스택 peek가 (일때 멈추란말
                        sb.append(stack.pop());
                    } // ( 전까지 다뽑아
                    stack.pop(); // ( 뽑아
                   
             }
            
            else{
                while (!stack.isEmpty() && priority(stack.peek()) >= priority(c)) {
                sb.append(stack.pop());
                }
            stack.add(c);
            }
        }
         
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        bw.write(sb.toString());
        bw.flush();
    }
}

 

 [해설]

 :  static int priority(char c){  새로운 메서드 만들기
        if(c=='+' || c=='-')                                        
            return 1;                                                                       우선순위 (수가 클수록 높다)
         else if(c=='*' || c=='/')                                                       -   0    =     (
             return 2;                                                                      -   1     =    +,  -
         else                                                                                 -   2     =    *,  / 
             return 0;
      }

 ** 메서드(method)란? **

  - 문제를 처리하기 위한 방법으로 소스 코드로 묶어놓고 필요에 따라 호출하여 동작시키는 기능 

 :  Stack<Character> stack = new Stack<>();  스택선언

 :  StringBuilder sb = new StringBuilder();  문자 이어붙여야해서

 :  String s = br.readLine(); 첫째줄에 중위표기식 입력받기
         
 :  for(int i=0;i<s.length();i++){
             char c = s.charAt(i);  입력받은 문자들을 하나하나 뜯어보려고
            
             if(c >= 'A')  입력받은 문자 아스키 코드가 A이상 즉 알파벳이 나오면 바로 출력
                  sb.append(c);  해당문자 즉 알파벳 나오면 알파벳 바로 출력
                
             else if(c== '(')  입력받은 문자가 열린괄호 ( 이면 스택에 넣기
                   stack.push(c);
            
            
             else if(c==')'){ 입력받은 문자가 닫힌괄호 ) 일 경우
                    while(stack.peek()!='('){  peek가 (일때 멈추란 말, 다른말로 peek가 ( 아닐 동안만 동작
                        sb.append(stack.pop());  (를 스택의 peek로 만들어야하니까 스택에서 ( 직전까지 다뽑기 
                    } 뽑았던 애들 출력하기
                    stack.pop();  이제 스택의 peek는 (이다 이 열린괄호도 스택에서 버리기 대신 출력하진 않는다        
             }
            
             else{  여기는 알파벳도 괄호도 아닌 연산자들끼리만 보는 함수
                   while (!stack.isEmpty() && priority(stack.peek()) >= priority(c)) {  아까 지정한 메서드 참고
                       sb.append(stack.pop());  스택의 peek ≥ 새로 입력받는 문자(연산자) 비교해서 
                   }                                           peek 우선순위 더 높다면 peek 를 스택에서 빼내서 출력
                   stack.add(c);  peek의 우선순위가 더 낮다면 새로 입력받은 문자를 스택에 push 
            }
   }
         
 :  while (!stack.isEmpty()) { 
             sb.append(stack.pop());  스택 빌때까지 남은 연산자 모두 빼서 출력
     }

 :        bw.write(sb.toString());  출력
          bw.flush();
    

이제 풀어보러 갈께요 :)

 

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

1918번: 후위 표기식

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *