[BOJ] 1918번: 후위 표기식

문제 링크: 백준/BOJ https://www.acmicpc.net/problem/1918

1918번: 후위 표기식

 

오랜만에 다시 풀어봤는데 역시 만만하지 않았다.

후위 표기식 문제는 작년에 학교 자구 시간 실습에서도 다루고, 혼자서도 풀어봤고, 최근 듣는 실습수업에 또 등장했는데...

이쯤 반복했으면 그냥 눈감고도 풀려야 하는 거 아닌가.........ㅠㅠ

하지만 처참하게 4번의 시도만에 통과했다.

멍청한 주인을 만나서 몸이 고생한다.

 

 

문제를 풀기 전 후위 표기식에 대해 간단히 설명하자면,

후위 표기식은 작성된 수식에 연산순서에 대한 정보가 담겨 있다.

우리가 흔히 쓰는 중위 표기식에서는 우리가 사전에 알고 있는 연산자 우선순위를 고려해서 연산 순서를 결정해야 한다.

하지만 후위 표기식에서는 미리 연산자의 우선순위를 고려해서 표기되어있기 때문에 앞에서 읽어나가며 계산하면 된다.

 

문제를 풀 때 처음 잡았던 뼈대는

 

1. 여는 괄호는 연산자 우선순위와 상관없이 스택에 쌓인다.

2. 스택의 top에 있는 원소의 우선순위보다 높은 연산자는 바로 스택에 쌓일 수 있다.

3. 닫는 괄호 만나면 여는 괄호 만날 때까지 스택의 원소들 모두 pop해서 표기식에 추가해준다.

 

1번과 3번은 괄호를 처리하는 방법이다.

여는 괄호는 닫는 괄호가 등장할 때까지 스택에 담겨 있어야 하므로 다른 사칙 연산자들보다 우선순위가 낮다고 가정한다.

 

2번에 대해 추가 설명을 하자면, 스택의 성질을 떠올려 보자.

스택은 LIFO, 즉 늦게 push된 원소일수록 빨리 pop된다.

그럼 스택의 밑에 쌓일수록 더 늦게 pop됨을 알 수 있다.

더 늦게 pop되어서 표기식에 추가된다는 것은 연산자 우선순위가 그만큼 낮다는 것을 의미!!

따라서 스택에 쌓여있는 연산자보다 우선순위가 같거나 낮은 연산자는 새치기를 할 수 없는 것이다.

 

그럼 내가 구현에서 무엇을 놓쳤길래 3번이나 틀렸을까?

새로 등장한 연산자와 스택에 쌓여있는 연산자의 우선순위와 같은 경우를 고려하지 않았던 게 문제였다.

 

반례를 이것저것 만들어보다가

A*B/C => ABC/*

이렇게 출력되는 것을 발견하고 깨달았다.

 

최종 답은 아래 코드와 같다.

/*
postfix 연습
20200503
*/
#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main() {
	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
	string input;
	cin >> input;

	string exp = ""; stack<char>op;
	for (int i = 0; i < input.size(); ++i) {
		if (input[i] >= 'A' && input[i] <= 'Z') {
			exp += input[i];
		}
		else if (input[i] == '(') {
			op.push('(');
		}
		else if (input[i] == ')') {
			while (op.top() != '(') {
				exp += op.top();
				op.pop();
			}
			op.pop();
		}
		else if (input[i] == '+' || input[i] == '-') {
			while (!op.empty() && op.top() != '(') {
				exp += op.top();
				op.pop();
			}
			op.push(input[i]);
		}
		else {
			while (!op.empty() && op.top() != '(' && op.top() != '+' && op.top() != '-') {
				exp += op.top();
				op.pop();
			}
			op.push(input[i]);
		}
	}
	while (!op.empty()) {
		exp += op.top();
		op.pop();
	}
	cout << exp << "\n";
}