[C++/백준 1918번] stack을 사용하여 중위 표기식을 후위 표기식으로 변환 (Postfix Expression)

중위 표기식 (Infix Expression)

 

중위 표기식은 연산자가 피연산자 사이에 오는 연산식을 의미한다.

 

예를 들어 (A+B)*C처럼 우리가 흔히 사용하는 표현법이다.

 

 

 

 

 

 

후위 표기식 (Postfix Expression)

 

후위 표기식은 연산자가 피연산자 뒤에 오는 연산식을 의미한다.

 

예를 들어 중위 표기식 A+B를 후위 표기식으로 나타내면 AB+로 표기할 수 있다.

 

이때 연산자가 여러 개 있을 경우 먼저 오는 연산자를 먼저 계산해 준다.

 

예를 들어 ABC*+라는 후위 표기식이 있으면 B*C를 먼저 하고 +A를 해주면 된다.

즉, 중위 표기법으로 나타내면 A+B*C와 동일하다.

 

 

 

 

 

 

중위 표기식을 후위 표기식으로 변환

 

중위 표기식을 후위 표기식으로 변환할 때에는 stack 자료구조를 사용하여 다음과 같은 규칙을 적용하면 된다.

 

1. 피연산자는 입력받은 순서대로 출력한다.

 

2. 여는 괄호를 입력받으면 그대로 스택에 저장한다.

 

3. 닫는 괄호를 입력받으면 여는 괄호가 나올 때까지 스택에 있는 모든 연산자(여는 괄호 포함)를 출력하고 삭제한다.

 

4. 연산자를 입력받으면 자신보다 우선순위가 낮거나 같은 연산자를 만날 때까지 stack에 저장한다.

 

5. 위 1~4번 과정을 반복하며 수식을 전부 입력받았지만 stack에 남은 연산자가 있을 경우 남은 연산자를 모두 출력한다.

 

따라서 아래와 같은 코드를 통해 중위 표기식을 후위 표기식으로 변환하는 것이 가능하다.

 

#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {
	stack<char> chStackOperator;
	string str;
	cin >> str;
	for (int i = 0; str[i] != '\0'; i++) {
		// 피연산자를 입력받았을 경우
		if (!(str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/' || str[i] == '(' || str[i] == ')'))
			cout << str[i];
		// 여는 괄호를 입력받았을 경우
		else if (str[i] == '(')
			chStackOperator.push(str[i]);
		// 닫는 괄호를 입력받았을 경우
		else if (str[i] == ')') {
			while (!chStackOperator.empty() && chStackOperator.top() != '(') {
				cout << chStackOperator.top();
				chStackOperator.pop();
			}
			if (!chStackOperator.empty())
				chStackOperator.pop();
		}
		// 그 외 연산자를 입력받았을 경우
		else {
			while (!chStackOperator.empty() &&
				(((str[i] == '+' || str[i] == '-') && (chStackOperator.top() == '+' || chStackOperator.top() == '-' || chStackOperator.top() == '*' || chStackOperator.top() == '/')) ||
				((str[i] == '*' || str[i] == '/') && (chStackOperator.top() == '*' || chStackOperator.top() == '/')))) {
				cout << chStackOperator.top();
				chStackOperator.pop();
			}
			chStackOperator.push(str[i]);
		}
	}
	// 입력 종료

	// 입력을 종료했는데 stack에 남은 연산자가 있을 경우
	while (!chStackOperator.empty()) {
		cout << chStackOperator.top();
		chStackOperator.pop();
	}
	cout << endl;
	return 0;
}

 

 

 

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