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

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

1918번: 후위 표기식

 

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

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

	stack<char> st;
	for(int i = 0; i < s.length(); i++){
		if(s[i] >= 'A' && s[i] <= 'Z'){
			cout << s[i];
		} else if(s[i] == '('){
			st.push(s[i]);
		} else if(s[i] == '*' || s[i] == '/'){
			while(!st.empty() && (st.top() == '*' || st.top() == '/')){
				cout << st.top();
				st.pop();
			}
			st.push(s[i]);
		} else if(s[i] == '+' || s[i] == '-'){
			while(!st.empty() && st.top() != '('){
				cout << st.top();
				st.pop();
			}
			st.push(s[i]);
		} else if(s[i] == ')'){
			while(!st.empty() && st.top() != '('){
				cout << st.top();
				st.pop();
			}
			st.pop();
		}
	}
	while(!st.empty()){
		cout << st.top();
		st.pop();
	}
	return 0;
}

 

1. 피연산자 A~Z는 무조건 출력한다.

2. ( 의 경우 스택에 바로 넣는다.

3. *, /, +, -일 경우 stack의 top의 연산자가 현재 연산자보다 우선순위가 같거나 높을 때 stack의 top 연산자를 출력하고 pop한 뒤 현재 연산자를 스택에 넣는다.

4. ) 가 나오면 스택에서 ( 가 나올 때까지 출력, pop하고 ( 까지 pop해준다.

5. 반복문을 다 돌고난 후 스택이 비어있지 않을 경우 남아 있는 연산자들을 출력, pop한다.

 

핵심: 스택은 우선순위가 낮은 연산자(+, -)부터 큰 연산자(*, /) 순으로 쌓여야 한다.