[C++] 백준(BOJ) 1918 후위표기식

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

후위표기식

• 중위 표기법(infix notation) :  연산자가 피연산자들 사이에 위치
• 후위 표기법(postfix notation) : 연산자가 피연산자들 뒤에 위치

 

중위 표현식 -> 후위 표현식

현재 연산자보다 우선순위가 높거나 같은 연산자는 모두 출력한 후(ex. * > + ) 현재 연산자를 스택에 넣는다.

** 괄호를 포함한 중위 표현식 -> 후위 표현식의 경우

왼쪽 괄호 (  는 우선순위가 가장 낮은 연산자, 왼쪽 괄호 ( 와 오른쪽 괄호 ) 가 만나면 없어짐

풀이1 (내풀이)

• 세부적으로 케이스를 나눠야하는데 까다로움. (결국 인터넷 참고해서 작성함 https://charles098.tistory.com/10)
  • 피연산자는 순서대로 출력
  • 연산자는
    • ( 이거나 스택(k)이 비어있는 경우, push
    • ) 인 경우, ( 를 만날때까지 pop
    • 스택(k)의 top보다 우선순위가 크면, push
    • 스택(k)의 top보다 우선순위가 작으면, 아닐때까지 pop 반복
    • 스택(k)가 안 비었으면 전부 출력

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

int priority(char ch)
{
	if (ch == '+' || ch == '-') return 1;
	if (ch == '*' || ch == '/') return 2;
	return 0; 
}
int main() {
	string s;
	string ans="";
	stack<char> k; //괄호+연산자 스택
	cin >> s; // A*(B+C)

	for (int i = 0; i < s.length(); i++)
	{
		//0) 피연산자는 출력
		if (s[i] >= 'A' && s[i] <= 'Z')
		{
			ans += s[i];
			continue;
		}

		//연산자 간의 우선순위 비교
		//1) s[i]가 '(' 인 경우, 스택이 비어있는 경우
		if (k.empty() || s[i] == '(')
		{
			k.push(s[i]);
			continue;
		}
		//2) ')'인 경우, '('를 만날때까지 출력
		if (s[i] == ')')
		{
			while (k.top() != '(')
			{
				ans += k.top();
				k.pop();
			}
			k.pop(); //'(' 는 삭제
			continue;
		}
		//3) top보다 우선순위가 크면 push
		if (priority(k.top()) < priority(s[i]))
			k.push(s[i]);

		//4) top보다 우선순위가 작거나 같으면 pop후 반복
		else
		{
			while (!k.empty() && priority(k.top()) >= priority(s[i]))
			{
				ans += k.top();
				k.pop();
			}
			k.push(s[i]);
		}
	}

		//5) 스택이 안 비었으면 전부 출력
		while (!k.empty())
		{
			ans += k.top();
			k.pop();
		}
		cout << ans;
		
	

	
	return 0;
}

---