[BOJ] 1918번_후위 표기식_스택 (C++)

[문제]

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

후위 표기법은 연산자가 피연산자 뒤에 위치하는 방식이다. 이 방법의 장점은 우리가 흔히 쓰는 중위 표기식과 달리 괄호나 우선순위를 생각하지 않아도 돼서 훨씬 직관적이다. 예를 들어, 중위표기식에서 1x(2+3)이라는 연산을 할 때 괄호가 없다면 2+3을 먼저 연산할 수 없다. 하지만 후위표기식으로 표현한다면 472+x로 괄호없이 표현할 수 있다.

중위 표기식을 후위 표기식으로 바꾸는 방법을 간단히 설명하면, 주어진 중위 표기식을 연산자의 우선순위에 따라 괄호로 묶어준다. 그런 다음 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨주면 된다.

예를 들어 1+2x3은 (1+(2x3))의 식과 같게 된다. 그 다음에 안에 있는 괄호의 연산자 x 를 괄호 밖으로 꺼내게 되면 (1+23x)이 된다. 마지막으로 또 +를 괄호의 오른쪽으로 고치면 123x+ 가 되게 된다.

다른 예를 들어 그림으로 표현하면 A+B*C-D/E를 완전하게 괄호로 묶고 연산자를 이동시킬 장소를 표시하면 다음과 같다.

이러한 사실을 통해 중위 표기식이 주어졌을 때 후위 표기식으로 고치는 프로그램을 작성하는 문제이다.

• 입력
  첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 x가 생략되는 등의 수식은 주어지지 않는다. 표기식은 알파벳 대문자와 +, -, *, /, (, ) 로만 이루어져 있으며, 길이는 100을 넘지 않는다.

[사용 알고리즘]

스택

[풀이 핵심]

• 연산 순서의 우선 순위는 다음과 같다.

  1. 괄호 안에 들어있는 연산
  2. *와 /가 들어있는 연산
  3. +와 -가 들어있는 연산

• 스택을 활용하여 다음과 같은 순서로 변환할 수 있다.

  1. str[i]가 피연산자일 경우 result 문자열에 추가한다.
  2. 스택이 비어있고 str[i]가 연산자일 경우 스택에 push한다.
  3. 스택의 top에 있는 연산자가 str[i]보다 우선순위가 낮을 경우 str[i]을 스택에 push하고, 스택의 top에 있는 연산자가 str[i]보다 우선순위가 높을 경우 스택의 top에 있는 연산자가 str[i]보다 우선순위가 낮아 질 때까지 pop하여 result 문자열에 추가한다. (단, 여는 괄호는 닫는 괄호가 나왔을 때만 pop한다.)
  4. 닫는 괄호가 나오면 여는 괄호가 나올 때까지 스택을 pop하여 result 문자열에 추가한다.
  5. str을 전부 순회했으면 스택에 남아있는 남은 연산자들도 pop하여 result 문자열에 추가해준다.
  6. result 문자열을 출력하면 정답이다.

[코드]

//boj1918번_후위 표기식_스택

#include<iostream>
#include<stack>

using namespace std;

int main() {
	string str;
	cin >> str;

	string result = "";

	stack<char> s;

	for (int i = 0; i < str.size(); i++) {
		if (str[i] >= 'A' && str[i] <= 'Z') {
			result += str[i];
		}
		else {
			if (s.empty()) {
				s.push(str[i]);
			}
			else {
				if (str[i] == '(') {
					s.push(str[i]);
				}
				else if (str[i] == '+' || str[i] == '-') {
					while (!s.empty() && s.top() != '(') {
						result += s.top();
						s.pop();
					}
					s.push(str[i]);
				}
				else if (str[i] == '*' || str[i] == '/') {
					while (!s.empty() && s.top() != '(' && s.top() != '+' && s.top() != '-') {
						result += s.top();
						s.pop();
					}
					s.push(str[i]);
				}
				else if (str[i] == ')') {
					while (!s.empty() && s.top() != '(') {
						result += s.top();
						s.pop();
					}
					s.pop();
				}
			}
		}
	}

	while (!s.empty()) {
		result += s.top();
		s.pop();
	}

	cout << result;

	return 0;
}