[BOJ / 스택] 1918 후위 표기식

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

1918번: 후위 표기식

 

1918  후위 표기식

알고리즘 : 스택

흔히 사용하는 중위 표기식 문제를 후위 표기식으로 바꾸는 문제입니다. 후위 표기식이라 하면 헷갈릴 수 있는데 예시로

 

                                       - A+B*C -> ABC*+

                                       - A+B+C -> AB+C+

                                       - A+B*(C+D*E-F/(Z+P))+H -> ABCDE*+FZP+/-*+H+

 

입니다. 두번째와 같은 경우를 ABC++로 처음에 생각하였는데 그러면 결과는 같더라도 계산순서가 다르기 때문에 맞지 않다고 합니다. 원래 식에서도 A,B가 먼저 더해지는 것처럼 AB+C+가 되어야 합니다.

스택을 활용하여 (와 사칙연산을 저장하고 우선순위에 맞게 처리하시면 됩니다.

 

 

 

 

< CODE >

#include <iostream>
#include <string>
#include <stack>

using namespace std;

string input;
stack<char> stk;

string calculate(const string & s)
{
	string ret = "";

	for (int i = 0; i < s.size(); i++)
	{
		switch (s[i])
		{
		case '(':
			stk.push(s[i]);
			break;
		case ')':
			while (!stk.empty() && stk.top() != '(')
			{
				ret += stk.top();
				stk.pop();
			}

			if(!stk.empty())
				stk.pop();
			break;
		case '+':
		case '-':
			while (!stk.empty() && (stk.top() != '('))
			{
				ret += stk.top();
				stk.pop();
			}

			stk.push(s[i]);
			break;
		case '*':
		case '/':
			while (!stk.empty() && (stk.top() == '*' || stk.top() == '/'))
			{
				ret += stk.top();
				stk.pop();
			}
			
			stk.push(s[i]);
			break;
		default:
			ret += s[i];
			break;
		}
	}

	while (!stk.empty())
	{
		ret += stk.top(); stk.pop();
	}

	return ret;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> input;

	cout << calculate(input) << '\n';

	return 0;
}

시간 : 0ms

 

태그 : #BOJ 후위표기식 #백준 후위표기식 #1918 후위표기식 #후위표기식 풀이