[자료구조] 백준 1918번: 후위 표기식 (C++), stack의 특성 LIFO

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

1918번: 후위 표기식

이번 문제는 학교에서 자료구조 과제로 나왔던 키워드이지만 그 당시에 안 했어서 이번 기회에 구현을 해보려 했다.

---

솔루션

[1] 식을 문자열로 받아서 피연산자인지 연산자인지 구분을 한다.

[2] 연산자나 괄호를 스택에 우선순위로 처리해야 하는 *, / 의 조건과 +, -의 조건, (, ) 두 괄호의 조건을 따로따로 처리를 해줘야 한다.

A+B*C

다음 경우를 예로 들어보자. 답으로는 ABC+*가 나와야 한다.

1) A는 피연산자이므로 출력

2) +는 연산자이므로 스택에 push

3) B는 피연산자이므로 출력

4) *는 연산자이므로 스택에 push

5) C는 피연산자이므로 출력

6) 문자열 입력이 끝났으므로 스택에 있는 원소들을 pop 하면서 뒤에 붙여야 함

>> ABC+*

>>>> 즉, 이 문제는 스택의 LIFO (Last In First Out) 특성을 이용해서 풀어야 하는 문제다.

 

한 가지 경우를 더 따져보자. (*와 /의 우선순위)

A+B*C-D/E

1) A는 피연산자이므로 출력

2) +는 연산자이므로 스택에 push

3) B는 피연산자이므로 출력

4) *는 연산자이므로 스택에 push

5) C는 피연산자이므로 출력

6) -는 연산자이지만 현재 스택의 top인 *이 -보다 우선이므로 top을 출력과 동시에 pop

6-2) 다시 현재 스택의 top인 +는 -보다 앞에 있으므로 이 식에서는 -보다 우선순위이다. top 출력 동시에 pop

6-3) - 스택에 push (현재 스택에는 -만 존재)

7) D는 피연산자이므로 출력

8) /는 연산자이므로 스택에 push

9) E는 피연산자이므로 출력

10) 문자열 입력이 끝났으므로 스택에 있는 원소들을 pop 하면서 뒤에 붙여야 함

>> ABC*+DE/-

>> 들어오는 원소가 top보다 우선순위가 작은 경우 pop을 해줘야 하는 것을 알 수 있다.

 

마지막 한 가지 경우를 더 따져보자. (괄호의 스택 push)

A*(B+C)

1) A는 피연산자이므로 출력

2) *는 연산자이므로 스택에 push

3) (는 괄호이므로 일단 스택에 push

4) B는 피연산자이므로 출력

5) +는 연산자이다. 괄호가 push 되어있지 않았다면 *보다 우선순위가 작아서 *가 출력되고, pop이 되어 +가 push 되어야 하지만 현재 top은 '( '이기 때문에 상관없다.

6) C는 피연산자이므로 출력

7) ')'는 닫는 괄호로 '('이 나올 때까지 스택의 원소들을 출력 및 pop 한다.

8) 모든 입력이 다 끝났으므로 스택에 있는 모든 원소들을 출력 및 pop 한다. (남아있는 *가 출력된다.)

>> ABC+*

>> 괄호 처리 방법이었다.

 

이를 토대로 코드를 짜주면 된다.

스택을 활용하여 무엇일 때, 어디까지 pop 하는지 stack을 잘 활용할 수 있어야 한다.

---

[AC 코드]

#include <iostream>
#include <stack>
using namespace std;

int main() {
	string value;
	cin >> value;
	string result = "";
	stack<char> s;
	for (int i = 0; i < value.size(); i++) {
		char a = value[i];
		if (a >= 'A' && a <= 'Z') {
			// 피연산자
			result += a;
		}
		else {
			// 연산자
			if (a == '(') {
				s.push(a);
			}
			else if (a == '*' || a == '/') {
				while (!s.empty() && (s.top() == '*' || s.top() == '/')) {
					result += s.top();
					s.pop();
				}
				s.push(a);
			}
			else if (a == '+' || a == '-') {
				while (!s.empty() && s.top() != '(') {
					result += s.top();
					s.pop();
				}
				s.push(a);
			}
			else if (a == ')') {
				while (!s.empty() && s.top() != '(') {
					result += s.top();
					s.pop();
				}
				s.pop();
			}
		}
	}

	while (!s.empty()) {
		result += s.top();
		s.pop();
	}
	cout << result;
	return 0;
}