[BOJ1918] 후위 표기식

[BOJ1918] 후위 표기식

문제 링크

문제 설명

• 스택의 기본 응용문제라고 할 수 있는 후위표기식 문제이다.
• 후위 표기식은 계산기 프로그램의 기반이 된다고 할 수 있다.
• 일반적으로 주어지는 식(괄호 존재)에 대해 후위 표기식으로 바꾼 식을 출력하면 된다.

코드 리뷰

• 먼저 주어진 문자열을 앞에서부터 탐색하며 피연산자에 대해서는 바로 ans라는 정답을 출력하는 배열 혹은 큐에 넣어준다.
• 연산자를 만났을 경우는 조건이 조금 나뉜다.(괄호 역시 연산자로 간주한다.)
• 먼저 연산자별 우선순위를 부여한다. *와 /는 연산우선순위가 가장 높으므로 3을 부여하였다.
• +와 -는 *,/보다 연산 우선순위가 낮으므로 1을 부여하였다.
• 괄호는 연산자는 아니지만 연산자로 간주하여 풀면 쉽게 해결할 수 있기에 우선순위는 -1로 가장 낮게 부여해놓는다.
• 주어진 문자열을 순차적으로 탐색하다가 연산자를 만났을 때는 스택이 비어있다면 무조건 스택에 넣어준다.
• 왼쪽 괄호역시 새로운 작은 식의 시작으로 볼 수 있으므로 스택에 푸쉬한다.
• 문자열을 이어서 탐색하다가 새로운 연산자를 만났을 때는 조건을 분기시킨다.
  1. 스택의 가장위에 있는 연산자의 우선순위보다 새로운 연산자의 우선순위가 높은 경우는 그 스택에 새로운 연산자를 push한다.
  2. 스택의 가장위에 있는 연산자의 우선순위가 더 높은 경우는 pop하여 ans 배열에 넣어준다. 그 후, 새로운 연산자의 우선순위가 더 높아질 때까지, pop한 후, 스택에 새로운 연산자를 push 한다.
  3. 오른쪽 괄호를 만난 경우는 왼쪽괄호를 만날 때까지 stack을 pop하며 괄호가 아닌 부분들만 ans배열에 저장한다.
  4. 우선순위가 같은 경우 역시 기존에 스택에 있는 연산자를 pop하여 ans배열에 push해준다.
• 모든 문자열 탐색이 끝나고 난 후에 stack에 남아있는 연산자가 있을 수 있으므로 stack이 empty가 될 때까지 pop하여 ans배열에 저장한다.
• 마지막으로 ans배열에 저장된 문자 순서대로 출력한다.

#include <iostream>
#include <cstring>
#include <stack>
#include <queue>
using namespace std;

char str[105];
queue <char> ans;
stack <char> s;

int operationLev(char op) {
	if (op == '*' || op == '/') return 3;
	else if (op == '+' || op == '-') return 1;
	else return -1;
}
int main() {
	cin >> str;
	int length = strlen(str);
	for (int i = 0; i < length; i++) {
		if (str[i] == '*' || str[i] == '/' || str[i] == '+' || str[i] == '-') { //탐색한 문자가 *,+,-,/인 경우
			while (!s.empty()) { 
				if (operationLev(str[i]) <= operationLev(s.top())
					&& (s.top() == '+' || s.top() == '-' || s.top() == '*' || s.top() == '/')) { //현재연산자와 스택의 top 연산자 우선순위 비교
					ans.push(s.top());
					s.pop();
				}
				else break;
			}
			s.push(str[i]);
		}
		else if (str[i] == '(') s.push(str[i]); //탐색한 문자가 왼쪽 괄호인 경우 -> 바로 스택에 push
		else if (str[i] == ')') { //탐색한 문자가 오른쪽 괄호인 경우 -> 왼쪽 괄호를 만날 때까지 스택을 pop하여 ans배열에 저장.
			while (s.top() != '(') {
				ans.push(s.top());
				s.pop();
			}
			s.pop();
		}
		else ans.push(str[i]); // 탐색한 문자가 피연산자인 경우 바로 ans배열에 저장.
	}
	while (!s.empty()) {
		ans.push(s.top());
		s.pop();
	}
	while (!ans.empty()) {
		cout << ans.front();
		ans.pop();
	}
	return 0;
}