[백준] 1918번: 후위 표기식

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

1918번: 후위 표기식

스택 하면 무조건 나오는 중위 표기식을 후위 표기식으로 바꾸는 문제

자료구조 시간에도 배웠지만 연습삼아 풀어보았다.

 

연산자별로 우선 순위를 정해놓고 식에서 연산자가 나오면 스택에 저장한다.

그리고 다음 연산자가 나올 때마다 스택의 연산자와 우선순위를 비교해서 작거나 같으면 스택에서 pop해서 출력한다.

괄호가 나왔을 때만 신경써서 구현해주자.

 

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

using namespace std;

int priority(char c) {
	if (c == '(' || c == ')') return 0;
	if (c == '+' || c == '-') return 1;
	if (c == '*' || c == '/') return 2;
}

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

	stack<char> s;

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