백준 1918 - 후위 표기식(C++)

문제

흔히 우리가 사용하는 수식은 중위 표기법으로 (A+B) 사용되고 있으며 이를 후위 표기법(AB+)으로 바꾸는 문제이다.

 

이는 연산자가 피연산자 뒤에 위치하는 방법이다.

 

이를 실행하는 방법은 다음과 같다.

 

1. 중위 표기식을 연산자의 우선순위에 따라 괄호로 묶어준다.
   
   A+B*C == (A+(B*C))
   
   
2. 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨준다.
   
   (A+(B*C)) == (A+BC*) == ABC*+

입력

첫째 줄에 중위 표기식이 주어진다. 단, 알파벳 대문자로만 이루어져 있으며 연산자가 가장 앞에 오거나 곱셈이 생략되는 경우는 주어지지 않는다.

 

표기식은 알파벳 대문자와 +, -, *, /, (, ) 로만 이루어져 있으며, 길이는 100을 넘지 않는다.

 

예제 입력

A*(B+C)

예제 출력

ABC+*

문제 해결

어디서 힌트를 얻을 수 있을까?

 

'괄호로 묶는다'라는 키워드를 통해서 기존에 문제를 풀어봤던 괄호 짝 찾기 등의 스택 관련 문제가 떠올렸다.

 

이 말은 즉 연산자를 차곡차곡 쌓다가 닫는 괄호 ')'를 만나면 여는 괄호 '('가 나올 때까지 연산자를 차례대로 출력해주면 되는 것이다.

 

그리고 연산자의 우선 순위가 있다는 것은 같은 우선 순위를 가진 연산자가 나올때는 바로 전에 나온 연산자를 pop()하고 해당 연산자를 push()하면 된다.

 

그리고 다른 우선 순위를 가졌다는 것은 우선 순위가 낮은 연산자가 절대로 우선 순위가 높은 연산자 위에 쌓이면 안된다는 것을 의미한다. 이는 닫는 괄호 ')'와 같은 역할을 가지게 된다.

 

즉, 다음 그림과 같이 해결하면 된다.

 

코드

#include <iostream>
#include <vector>
#include <string>

std::vector<char> stack;

void solve(const char* str, int size, int idx)
{
	if (idx == size)
	{
		while (!stack.empty())
		{
			std::cout << stack.back();
			stack.pop_back();
		}
		return;
	}
	if (str[idx] >= 'A' && str[idx] <= 'Z')
	{
		std::cout << str[idx];
		solve(str, size, idx + 1);
	}
	else if (str[idx] == '+' || str[idx] == '-')
	{
		if (!stack.empty())
		{
			char c = stack.back();
			if (c == '+' || c == '-')
			{
				std::cout << c;
				stack.pop_back();
				stack.push_back(str[idx]);
			}
			else if (c == '*' || c == '/')
			{
				while (!stack.empty() && stack.back() != '(')
				{
					std::cout << stack.back();
					stack.pop_back();
				}
				stack.push_back(str[idx]);
			}
			else
				stack.push_back(str[idx]);
		}
		else
			stack.push_back(str[idx]);
		solve(str, size, idx + 1);
	}
	else if (str[idx] == '*' || str[idx] == '/')
	{
		if (!stack.empty())
		{
			char c = stack.back();
			if (c == '*' || c == '/')
			{
				std::cout << c;
				stack.pop_back();
				stack.push_back(str[idx]);
			}
			else if (c == '+' || c == '-')
				stack.push_back(str[idx]);
			else
				stack.push_back(str[idx]);
		}
		else
			stack.push_back(str[idx]);
		solve(str, size, idx + 1);

	}
	else if (str[idx] == '(')
	{
		stack.push_back(str[idx]);
		solve(str, size, idx + 1);
	}
	else if (str[idx] == ')')
	{
		while (stack.back() != '(')
		{
			std::cout << stack.back();
			stack.pop_back();
		}
		stack.pop_back();
		solve(str, size, idx + 1);
	}
}

int main(void)
{
	std::string str;

	std::cin >> str;
	solve(str.c_str(), str.size(), 0);
	std::cout << std::endl;
	return 0;
}

문제 출처

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

1918번: 후위 표기식