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

 

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

1918번: 후위 표기식

 

단순히 infix에서 postfix로 변환하는 문제이다. 스택을 이용해 해결 가능할 듯하다.

모든 식이 괄호로 묶여있는 것이 아니므로 연산자의 우선순위를 고려해서 하면 될 듯하다.

 

infix를 한글자씩 읽으면서 진행

1) 피연산자 -> 바로 출력

2) '(' -> 스택에 push

3) * or / -> 본인과 우선순위가 같은 연산자 (* or /)가 스택에 있으면 pop해서 출력 (+ or - or '(' 나오면 중지 )

4) + or - -> '('가 나올때까지 or 스택이 빌때까지 pop해서 출력

5) ')' -> '('가 나올떄까지 pop해서 출력

 

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
string infix;
stack<char> s;

int main(void) {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> infix;

	for (ll i = 0; i < infix.length(); i++) {
		if (infix[i] >= 'A' && infix[i] <= 'Z') {
			cout << infix[i];
		}
		
		else if (infix[i] == '+' || infix[i] == '-') {
			while (!s.empty() && s.top() != '(') {
				cout << s.top();
				s.pop();
			}
			s.push(infix[i]);
		}

		else if (infix[i] == '*' || infix[i] == '/') {
			while (!s.empty() && s.top() != '(' && s.top() != '-' && s.top() != '+') {
				cout << s.top();
				s.pop();
			}
			s.push(infix[i]);
		}

		else if (infix[i] == '(') {
			s.push(infix[i]);
		}

		else if (infix[i] == ')') {
			while (s.top() != '(') {
				cout << s.top();
				s.pop();
			}
			s.pop();
		}

	}
	while (!s.empty()) {
		cout << s.top();
		s.pop();
	}
}