[백준] 1918번 후위 표기식

1918번: 후위 표기식

input과 stack의 top이 있을 때

 

1. 현재 input이 사칙연산인 경우

 

input의 우선순위 > top의 우선순위 라면

우선순위가 더 낮은 top을 계산해주면 안 되므로

우선순위가 더 높은 input을 stack에 push해준다.

 

input의 우선순위 <= top의 우선순위 라면

우선순위가 더 높은 top부터 계산해줘야 하므로

input의 우선순위 > top의 우선순위가 될 때까지 pop해준 뒤

우선순위가 더 높은 상태가 된 input을 stack에 push해준다.

 

이때 top이 왼쪽 괄호일 수도 있는데

연산자 우선순위는

괄호 > 곱셈과 나눗셈 > 덧셈과 뺄셈

순으로 괄호가 가장 높은 우선순위를 갖지만

괄호는 계산에 들어가지 않으므로 우선순위를 가장 낮게 매겨준다.

 

2. 현재 input이 알파벳인 경우

결괏값에 바로 넣어준다.

 

3. 현재 input이 왼쪽 괄호인 경우

stack에 push해준다.

 

4. 현재 input이 오른쪽 괄호인 경우

top이 왼쪽 괄호가 될 때까지 pop해준다.

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

int Priority(char a) {
	if (a == '(') return 0; //괄호는 연산하지 않기 때문에 가장 낮은 우선순위로 취급해준다
	else if (a == '*' || a == '/') return 2;
	else return 1;
}

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

	stack <char> op;

	for (int i = 0; i < infix.size(); i++) {
		if (infix[i] >= 'A'&&infix[i] <= 'Z') postfix += infix[i]; //알파벳은 결과에 바로 추가
		else if (infix[i] == '(') op.push(infix[i]); //왼쪽 괄호는 push
		else if (infix[i] == ')') { //왼쪽 괄호가 나올 때까지 pop
			while (op.top() != '(') {
				postfix += op.top();
				op.pop();
			}
			op.pop();
		}
		else { //연산자가 나오면 현재 연산자의 우선순위와 top의 우선순위를 비교
			while (!op.empty() && Priority(infix[i]) <= Priority(op.top())) { //현재 연산자의 우선순위가 top의 우선순위보다 작거나 같다면 더 커질 때까지 pop
				postfix += op.top();
				op.pop();
			}
			op.push(infix[i]); //현재 연산자의 우선순위가 top의 우선순위보다 크다면 push
		}
	}

	while (!op.empty()) {
		postfix += op.top(); //남은 연산자들이 있으면 추가해준다
		op.pop();
	}

	cout << postfix;

	return 0;
}