[백준] 1918 후위 표기식 - Java

 

 

 

문제 이해는 어렵지 않은데 어떻게 풀어야 할 지 정말 고민을 많이 한 문제이다.

스택의 관점에서 생각해보자.

 

연산자 : + - * / 

문자 : A~Z

 

스택과 문자열을 만들고, 스택에 어떤 연산자가 들어가있는지에 따라 연산자에 대한 처리를 해 줘야 한다.

연산자의 우선순위도 정해진다.

+ - 는 * / 보다 우선순위가 떨어진다.

 

1. 문자가 입력되면 바로 출력한다.

 

2. 연산자가 입력되면 스택의 가장 위쪽에 들어가 있는 연산자의 종류에 따라서 다른 연산을 한다.

 2-1. 입력된 연산자의 우선순위가 스택의 꼭대기에 들어있는 연산자의 우선순위보다 높을 때, 스택의 요소를 하나하나   지우고 지운 값을 출력한다. 스택의 꼭대기에 들어있는 연산자의 우선순위가 입력된 연산자의 우선순위보다 작을 때   까지 반복한다.

 

3. '(' 와 ')'는 따로 처리해 준다.

'(' 가 입력되면 스택에 넣어 주고, ')'가 입력되면 스택에 '('가 나올 때 까지 스택의 요소들을 지우고 지운 값을 출력한다.

 

코드를 통해 알아보자.   

 

import java.util.*;

public class Main {
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();

		String str = sc.nextLine();

		Stack<Character> st = 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) == '(') {
				st.push('('); // ( 나오면 스택에 넣어
			} else if (str.charAt(i) == ')') {
				char check = '0'; // 임시값
				while (check != '(') { // ) 가 나오면 스택에 저장된게 ( 가 될때까지 뽑아낸다.
					check = st.pop();
					if (check == '(') { // ( 가 나오면 브레이크
						break;
					} else {
						sb.append(check); // (가 아니면 스택에 저장된 거 출력
					}
				}
			} else if (str.charAt(i) == '+' || str.charAt(i) == '-') {
				// +와 - 는 같고 *와 / 는 다름. 즉 계산에 우선순위가 있다.
				if (st.empty()) {
					st.push(str.charAt(i));
				} else {
					while (st.peek() == '*' || st.peek() == '/' || st.peek() == '-' || st.peek() == '+') {

						sb.append(st.pop());
						
						if (st.empty()) {
							break;
						}
					}
					st.push(str.charAt(i));
				}
			} else if (str.charAt(i) == '*' || str.charAt(i) == '/') {
				if (st.empty()) {
					st.push(str.charAt(i));
				} else {
					while (st.peek() == '*' || st.peek() == '/') {

						sb.append(st.pop());

						if (st.empty()) {
							break;
						} 
					}
					st.push(str.charAt(i));
				}
			}
		}
		for (int i = 0; i < st.capacity(); i++) {
			if (st.empty()) {
				break;
			} else {
				sb.append(st.pop());
			}
		}

		System.out.print(sb);

	}
}