1918. <후위 표기식>

1918번: 후위 표기식 (acmicpc.net)

1918번: 후위 표기식

 

1. 여러분의 마음을 읽어보자.

A+B*C-D/E

ABC*+DE/-​

여기는 문자 뭉탱이 연산자 뭉탱이 문자 뭉탱이 연산자 뭉탱이 순으로 뭉탱이들이 다채로운 case.

 

아마 까다로워할 포인트는

A*(B+C)

ABC+*

처럼 문자 한 뭉탱이가 나오고 연산자 뭉탱이가 나오는  case.

이 두 case가 달라서 구현을 어떻게 접근해야할지 조차 모르는 분들이 많을 것이다.

 

2. 문자는 그대로?

일단 문자의 순서는 변하지 않는다. 다만 연산자들과 괄호라는 녀석들이 중간에 있어서 힘들다.

문자 먼저 처리하자. 문제를 이해해보면 알겠지만 후위표기식은 stack은 무조건 필수다.

 

다만 문자들조차 stack에 넣어버리면 너무 복잡해진다. 따라서 stringbuilder을 생성해서 문자는 나오는 순간 넣어주자

(이러면 아니 이러면 문자랑 연산자랑 순서 꼬이잖아요) 라고 생각할 수도 있겠지만, 그건 구조적으로 불가능하다.

 

이유는 input되는 문자들은 중위표기로 우리가 익숙한 연산표기법이다. 이는 문자와 연산자가 교차로 나오기때문에

문자를 sb에 즉각적으로 넣는다고해서 순서가 꼬이지 않는다. 그 이유는 아래에서 설명하겠다.

 

3. 괄호의 존재

엄청 신경쓰인다 이놈;;; 다만 후위표기식이라 괄호가 있어도 괄호 내 문자가 더 먼저 쓰여야한다 이런법은 없다. 후위표기식은 뭉탱이 뭉탱이들을 연산하고 그 다음 뭉탱이끼리 한다고 생각해야한다. 

괄호 안에녀석의 문자는 굳이 신경쓸 필요없다 1번을 이해했다면 이해할거다. 문제는 연산자이다.

이때의 연산자는 가장 우선시되는 놈이기에 이를 신경쓰는게 두번째 어려운 포인트이다.

이때 stack이 깡패처럼 쓰이는데, 여는 괄호를 stack에다가 넣어주고 이를 제일 우선시 되지 않게 만든다. 이게 포인트다

그렇게 되면 괄호 내 문자는 sb에 가니 신경쓰지 않아도 되고 연산자는 (라는 녀석 위의 포지션에 push된다.

그리고 나서 닫는 괄호를 만나는 순간  stack.peek() != ( 때까지 (while문)을 쓰겠다) sb에 넣어주기만 하면 괄호내 최우선 연산자가 바로 sb에 담기니까 문제없이 구조를 만들 수 있다.

추가적으로 (는 후위표기식에 들어가지 않으니 pop해줘서 없애준다.

 

4.연산자들의 위계질서

우린 초등교육을 받은 학생들이기에 곱하기 나누기가 우선시 되어야하는걸 안다.

자, 문자는 그대로 sb에 append한다.

하지만 연산자가 문제다. 일단 3에서 괄호를 처리했다.

괄호 내 연산자는 (를 스택에 넣음으로써 처리했다.

 

문제는 괄호가 아닌 평범한 연산자들은 어케 처리할까. 예제들을 해보면 알겠지만 

A+B*C

ABC*+

 

 

*가 먼저 나온다.

즉, a+b*c는 +가 먼저 stack에 들어가기에 저 output이 자연스럽다.

A+B*C-D/E

ABC*+DE/-

여기서는 왜 이렇게 나올까.

 

간단하다. 일단 연산자는 기본적으로 다 stack에 들어가야한다.

하지만 위계에 따라서 sb로 갈건지 stay할건지를 정해야하는데, 

곱하기 나누기 같은 위계가 높은 녀석이 stack의 peek에있는 더하기를 만난다치자, 이때 +를 sb에 먼저보내면 되겠는가?

위 예시보면 안되겠다. 즉 곱하기는 더하기 위의 자리에 stack에 push된다.

즉 stack.peek(연산자)의 위계질서 vs str.charAt(i)의 위계질서 간의 싸움이다. 이기는놈이 stack에서 빠져나간다.

진놈은 나중에 stack에 들어간다. 

여기서 잠깐 이때 위계의 싸움을 할때 if를 쓰면 안된다. 이게 어려운점같은데 이기거나 비겨도 stack에서 빠져나가야한다.

위의 예시를 보자 

일단 + ,* 가 차례대로 깔려있다. 그 다음놈은 - 인데 얘는 *한테 위계로 진다. 따라서 *는 sb로 나간다. 

이 다음 그렇다면 -는 +위로 push되야할까? 위의 예제를 보면 그렇지 않다. 따라서 - +는 비겼지만 그래도 +는 나가야한다.

아 따라서 저 싸움은 이기거나 비겨야 빠져나가야 한다는 점을 참고하자.

 

5. 마지막 스택의 잔류값

저 싸움이 끝나지 않아 잔류된 값이 존재할수도 있다. - * 순서대로 깔린다면 pop될 껀덕지가 없으니..

따라서 마지막에 스택을 비워 sb로 넣어주면 자연스레 *- 이런순서가 되니 알맞다.

 

결론. 문제 졸라 복잡 but stack 구현 끝판왕 문제가 아닐까 싶다 갠적으로. 생각할 거 진짜많다.

package 스택과큐;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class _1918_후위표기식_again {
	
	public static int priority(char c ) {
		if(c == '*' || c == '/') {
			return 2;
		}
		else if(c == '+' || c == '-') {
			return 1;
		}
		//여기엔 여는 괄호가 포함되겠다,
		//여는 괄호를 만나고 닫힌 괄호를 만난 순간 연산자가 out되야하기에 그 중간의 연산자가 나가면 안됀다. 따라서 가장 작은 값을 준다.
		else {
			return 0;
		}
	}

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
					BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
					String str = br.readLine();
					
					StringBuilder sb = new StringBuilder();
					Stack<Character> stack = new Stack<>();
					
					
					for(int i=0; i<str.length(); i++){
						if(str.charAt(i) >='A' && str.charAt(i) <= 'Z') {
							sb.append(str.charAt(i));
							
						}
						
						//
						else {
							//여는 괄호를 마주쳤을때.
							if(str.charAt(i) =='(') {
								stack.push(str.charAt(i));
							}
							
							else if(str.charAt(i) == ')') {
								while(!stack.isEmpty() && stack.peek() != '(') {
									sb.append(stack.pop());
								}
								stack.pop();
							}
							//+,-,*,/ 이런 연산자 일때.
							else {
								
								while(!stack.isEmpty() && priority(stack.peek()) >= priority(str.charAt(i))) {
									sb.append(stack.pop());
								}
								
								//default 무조건
								stack.push(str.charAt(i));
							}
						}
						
						
						
					}
					
					while(!stack.isEmpty()) {
						sb.append(stack.pop());
						}
					
					System.out.println(sb);
					

	}

}