후위 표기식 변환 - 스택 활용

피연산자(숫자)를 만난다면 그냥 바로 피연산자를 출력해준다.

연산자를 만난다면 스택에 넣을 것이다.

그런데, 우선순위가 항상 높은 것이 스택의 맨 위에 있도록 스택을 유지하게 넣을 것이다. ( 우선순위가 같다면 먼저 스택에 있던 연산자가 먼저 출력해주는게 맞다 그러므로 같아도 출력해주며 pop해줄것이다.)

왼쪽 괄호 '(' 는 스택에 바로 넣어줄 것이다. ( 우선순위를 제일 낮게 설정 )

오른쪽 괄호 ')' 는 '(' 가 스택에 맨 위에 있을 때까지 스택 안의 연산자들을 출력하면서 pop을 해줄 것이다.

모든 과정을 문자열 끝까지 한 후 스택에 남아있는 연사자들을 모두 출력해준다.

 

중위 표기법	후위 표기법
1+3*8	138*+

 

전체 코드

#include <iostream>
#include <stack>
using namespace std;
stack<char> s;
int prec(char ch) // 문자가 들어오면 우선순위를 반환해줌
{
	switch (ch)
	{
	case '+': case '-':
		return 1;
	case '*': case '/':
		return 2;
	case '(': case ')':
		return 0;
	}
}
void solve(string str)
{
	int idx = 0;

	while (idx < str.length())
	{
		char ch = str[idx];

		switch (ch) {
		case '+': case '-': case '*': case '/':
			while ( !s.empty() && prec(ch) <= prec(s.top()) )
			{ // 현재 문자 ch의 우선순위보다 낮은게 나올때까지
				cout << s.top();
				s.pop();
			}
			s.push(ch);
			break;

		case '(': // 여는 괄호는 스택에 바로 넣어주기
			s.push(ch);
			break;

		case ')':
			while (s.top() != '(') // '(' 만날때까지 출력하면서 pop
			{
				cout << s.top();
				s.pop();
			}
			s.pop(); // '('가 top일테니 pop 한번 더
			break;

		default: // 피연산자(숫자들)
			cout << str[idx];
			break;
		}
		idx++;
	}
	while (!s.empty()) // 스택에 남아있는 연산자들 출력
	{
		cout << s.top();
		s.pop();
	}

}
int main(void)
{
	string str;
	cin >> str;
	solve(str);
}