[Java/백준/스택(Stack)] 1918번: 후위 표기식, 1935번: 후위 표기식2

문제

 

www.acmicpc.net/problem/1918

1918번: 후위 표기식

www.acmicpc.net/problem/1935

1935번: 후위 표기식2

 

후위 표기식: 골드 4, 후위 표기식2: 실버 3 문제이다.

 

푸는 방식은 비슷해서, 후위 표기식을 풀 수 있으면 후위 표기식2 문제는 자동으로 풀 수 있다.

 

가장 나중에 들어온 데이터가 가장 먼저 나가는 후입선출(LIFO: Last In First Out) 구조의 가장 대표적인 응용 예시이다.

계산을 할 때 Stack을 이용해 중위 표기식을 후위 표기식으로 바꾸고, 해당 결과를 Stack을 이용해 계산할 수 있다.

 

 

계산하는 것은 해당 문제에 포함되지 않으므로 중위 표기식을 후위표기식으로 바꾸는 것만 생각해보자.

예를 들어 중위 표기식 A+B에서 피연산자를 앞으로, 연산자를 뒤로 빼는 AB+가 후위 표기식이 된다.

 

코드 설명

StringBuilder sb가 출력될 값이다.

1. 숫자(피연산자)

그대로 출력한다.

2. 왼괄호 (, +, -, /, *의 경우

우선순위와 스택을 이용해서 출력될 순서를 정한다.

2-1. 연산자 우선순위 정하기

왼쪽 괄호 ( 은 우선순위가 가장 높다. → 3

/, *가 그 다음으로 높다. → 2

+, -가 그 다음이다. → 1

 

2-2. 연산자 스택에 넣기

입력받은 연산자(token)과 Stack top에 있는 연산자를 비교한다.

후위 표기식에서 우선순위가 높은 연산자가 낮은 연산자보다 앞에 위치하는 특징을 이용한다.

 

토큰의 우선순위가 더 높으면 토큰을 출력하지 않고 스택에 그대로 넣는다.

 

토큰의 우선순위가 top보다 낮으면,

스택의 top이 토큰보다 낮아지거나 스택이 빌 때까지 pop한다.

스택에서 pop한 연산자는 그대로 출력한다. 이후 조건이 만족되면 토큰을 스택에 push한다.

 

3. 우괄호 ) 을 만났다면,

왼괄호가 나타날 때까지 스택의 연산자들을 pop해서 출력한다.

왼괄호를 만났으면 그냥 pop하고 출력하진 않는다.

 

 

package boj;

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


/* 후위 표기식 */
public class BOJ1918 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String expression = br.readLine();
		int len = expression.length();
		StringBuilder sb = new StringBuilder();
		Stack<Character> operatorStack = new Stack<Character>();
		
		for(int i = 0; i < len; i++) {
			char token = expression.charAt(i);
			
      // 숫자일 때
			if('A' <= token && token <= 'Z') {
				sb.append(token);
			} else if(token == ')') {
				while(!operatorStack.isEmpty()) {
					if(operatorStack.peek() == '(') {
						operatorStack.pop();
						break;
					}
					sb.append(operatorStack.pop());
				}
			} else {
				while(!operatorStack.isEmpty()) {
					int point = 3; // 왼 괄호
					if(token=='+' || token =='-')
						point = 1;
					else if(token == '*' || token == '/')
						point = 2;
					
					int topPoint = 0;
					if(operatorStack.peek()=='+' || operatorStack.peek() =='-')
						topPoint = 1;
					else if(operatorStack.peek() == '*' || operatorStack.peek() == '/')
						topPoint = 2;
					
					if(topPoint < point) { // token의 우선순위가 더 높을 때 push
						operatorStack.push(token);
						break;
					}
					sb.append(operatorStack.pop());
				}
				if(operatorStack.isEmpty()){
					operatorStack.push(token);
				}
			}
			
		}
		while(!operatorStack.isEmpty()) { // 남아있는 연산자를 sb에 더해준다
			sb.append(operatorStack.pop());
		}
		
		System.out.println(sb);
		
		br.close();
	}
}