[BOJ][JAVA] 1918번: 후위 표기식

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

1918번: 후위 표기식

 

중위표기식으로 되어있는 것을 후위 표기식으로 바꾸는 것이다. 기본적으로 스택을 사용해 바꾼다.

이번 문제는 다행히 한번에 맞아서 오답코드를 올리지 않아도 된다.

---

오답노트(푸는 동안 사고과정 및 개선점)

후위 표기식으로 바꿀때는, 수는 그냥 출력하고, 연산자를 스택에 담아서 우선순위에 따라 처리해야된다. 만약 괄호가 있다면 여는 괄호는 그냥 넣고, 닫는 괄호가 오기 전까지 계속 스택에 우선순위를 보며 연산자를 넣다가 닫는 괄호가 오면 여는 괄호가 올 때 까지 싹 빼버리는 과정을 거친다. 이렇게 반복하면 아주 쉽게 후위 표기식을 완성할 수 있다. 

 

후위표기식으로 만들어진 식을 연산하는 건 더 쉽다. 앞에서부터 스택에 넣으면서, 연산자를 만나면 스택에 넣지 않고 pop을 두 번 한다. 첫번 째 pop은 뒤에 올 피연산자이고, 두번째 pop이 앞에 올 피연산자다. 이제 그 두개를 연산해서 다시 스택에 넣고, 이렇게 스택에 요소가 한개 남을 때 까지 반복하면 연산이 끝난다. 

 

연산하는 문제는 아래 문제를 풀면 된다.

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

1935번: 후위 표기식2

 

주의할 점이라고는 스택에 pop이나 peek 시킬 때 스택이 비어있는 지 잘 확인해주는 것 밖에 없다!! 난이도를 가려놓고 푸는 입장에서 개인적인 감상으로는 이게 왜 골드 2인지 모르겠다. 후위표기식의 개념만 알고있다면 손쉽게 풀리는 문제다.

 

정답 코드가 깔끔하게 적히진않았지만 읽는 데는 문제가 없을? 것 같다. 

 

---

정답코드

import java.util.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String input = sc.next();
		StringBuilder sb = new StringBuilder();
		Stack<Character> op = new Stack();
		for (int i = 0; i < input.length(); i++) {
			char t = input.charAt(i);
			if ('A' <= t && t <= 'Z') {
				sb.append(t);
			} else {
				// 연산자 우선순위는 - + 같고 * / 가 높다
				// 뽑아야 될 경우 -> - +일 때 - + * /를 만나면 뽑아야됨.
				// * / 일 때 * / 를 만나면 뽑아야됨.
				if (t == '(') {
					op.push(t);
				}
				if (t == ')') {
					while (!op.isEmpty()) {
						if (op.peek() == '(')
							break;
						else
							sb.append(op.pop());
					}
					op.pop(); // ( 도 빼주기
				} else {
					if (!op.isEmpty()) {
					    if (t == '*' || t == '/') {
					        if (op.peek() == '+' || op.peek() == '-')
					            op.push(t);
					        else {
					            while (true) { // 같거나 높은 우선순위가 아닐때 까지
					                if (!op.isEmpty() && (op.peek() == '*' || op.peek() == '/'))
					                    sb.append(op.pop());
					                else
					                    break;
					            }
					            op.push(t);
					        }
					    } else if (t == '-' || t == '+') {
					        if (op.peek() == '(') {
					            op.push(t);
					        } else {
					            while (!op.isEmpty()) { // 같거나 높은 우선순위가 아닐때 까지
					                if (op.peek() == '(')
					                    break;
					                else
					                    sb.append(op.pop());
					            }
					            op.push(t);
					        }
					    }
					} else {
					    op.push(t);
					}
				}

			}
		}
		while (!op.isEmpty()) {
			sb.append(op.pop());
		}
		System.out.println(sb);

	}
}

 

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요! 로그인 안해도 됩니다 ^_^