후위 표기법(Shunting Yard Algorithm)

1. 중위 표기법(Infix Notation)과 후위 표기법(Postfix Notation)

중위 표기법 (Infix Notation)

일반적으로 우리가 사용하는 수식 표현 방식입니다. 연산자가 피연산자 사이에 위치합니다.

• (3 + 4) * 5
• 10 + 2 * 6

후위 표기법 (Postfix Notation)

후위 표기법은 연산자가 피연산자 뒤에 위치하는 표현 방식입니다.

• 3 4 + 5 *
• 10 2 6 * +

후위 표기법은 괄호 없이도 연산자의 우선순위를 명확하게 정의할 수 있습니다.

 

 

---

2. Shunting Yard Algorithm의 동작

알고리즘의 목적은 중위 표기법으로 된 수식을 후위 표기법으로 변환하는 것입니다. 알고리즘은 두 개의 주요 자료 구조를 사용합니다:

• 출력 큐: 결과로 나올 후위 표기법을 저장하는 큐.
• 연산자 스택: 연산자의 우선순위와 괄호를 처리하기 위한 스택.

알고리즘의 규칙

1. 숫자(피연산자)는 바로 출력 큐에 추가합니다.
2. 연산자는 스택에 추가하지만, 스택에 있는 연산자들의 우선순위를 비교해, 더 높은 우선순위의 연산자가 있다면 그 연산자를 스택에서 꺼내 출력 큐에 먼저 추가합니다.
3. 괄호:
   • 여는 괄호 (는 무조건 스택에 추가합니다.
   • 닫는 괄호 )를 만나면, 스택에서 여는 괄호가 나올 때까지 연산자를 출력 큐로 보냅니다. 여는 괄호는 스택에서 제거합니다.

연산자의 우선순위

연산자의 우선순위는 다음과 같습니다:

1. ^: 지수 연산 (우선순위가 가장 높음)
2. *, /: 곱셈과 나눗셈
3. +, -: 덧셈과 뺄셈

우선순위가 같은 연산자끼리는 좌결합성에 의해 왼쪽에서 오른쪽으로 처리됩니다. 하지만 ^ 연산자는 우결합성을 가집니다.

 

---

3. Shunting Yard Algorithm의 동작 예시

중위 표기법:

(3 + 4) * 5 - 6

 

단계별 변환 과정:

1. 토큰: (
   • 여는 괄호는 스택에 넣습니다.
   • 스택: [(]
   • 출력 큐: []
2. 토큰: 3
   • 숫자이므로 출력 큐에 추가합니다.
   • 스택: [(]
   • 출력 큐: [3]
3. 토큰: +
   • 연산자는 스택에 추가합니다.
   • 스택: [(,+]
   • 출력 큐: [3]
4. 토큰: 4
   • 숫자이므로 출력 큐에 추가합니다.
   • 스택: [(,+]
   • 출력 큐: [3, 4]
5. 토큰: )
   • 닫는 괄호를 만나면, 여는 괄호가 나올 때까지 연산자를 출력 큐로 보냅니다.
   • 스택: []
   • 출력 큐: [3, 4, +]
6. 토큰: *
   • 연산자는 스택에 추가합니다.
   • 스택: [*]
   • 출력 큐: [3, 4, +]
7. 토큰: 5
   • 숫자이므로 출력 큐에 추가합니다.
   • 스택: [*]
   • 출력 큐: [3, 4, +, 5]
8. 토큰: -
   • - 연산자는 스택의 *보다 낮은 우선순위를 가지므로, *를 먼저 출력 큐로 보냅니다. 그리고 -를 스택에 넣습니다.
   • 스택: [-]
   • 출력 큐: [3, 4, +, 5, *]
9. 토큰: 6
   • 숫자이므로 출력 큐에 추가합니다.
   • 스택: [-]
   • 출력 큐: [3, 4, +, 5, *, 6]
10. 마지막 단계:
    • 수식이 끝났으므로 스택에 남은 모든 연산자를 출력 큐로 보냅니다.
    • 스택: []
    • 출력 큐: [3, 4, +, 5, *, 6, -]

후위 표기법 결과:

3 4 + 5 * 6 -

이 후위 표기법 수식은 괄호 없이도 연산자 우선순위를 고려한 계산이 가능합니다.

 

 

---

4. Shunting Yard Algorithm의 구현 (C++)

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

using namespace std;

int precedence(char op) {
	if (op == '^') return 3;
	if (op == '*' || op == '/') return 2;
	if (op == '+' || op == '-') return 1;
	return 0;
}

bool isLeftAssociative(char op) {
	return op != '^'; // '^'은 우결합성
}

vector<string> shuntingYard(const string& expression) {
	stack<char> operators;
	vector<string> output;
	string token = "";

	// 문자열을 순차적으로 읽어서 토큰화
	for (size_t i = 0; i < expression.size(); i++) {
		char current = expression[i];

		// 공백 무시
		if (current == ' ') {
			continue;
		}

		// 숫자 토큰인 경우 (여러 자릿수 지원)
		if (isdigit(current)) {
			token += current;
			// 다음 문자가 숫자가 아니면 토큰 완료
			if (i + 1 == expression.size() || !isdigit(expression[i + 1])) {
				output.push_back(token);
				token = "";
			}
		}
		// 여는 괄호는 스택에 추가
		else if (current == '(') {
			operators.push(current);
		}
		// 닫는 괄호는 여는 괄호를 만날 때까지 스택에서 연산자를 출력
		else if (current == ')') {
			while (!operators.empty() && operators.top() != '(') {
				output.push_back(string(1, operators.top()));
				operators.pop();
			}
			operators.pop(); // 여는 괄호 제거
		}
		// 연산자 처리
		else {
			while (!operators.empty() &&
				(precedence(operators.top()) > precedence(current) ||
				(precedence(operators.top()) == precedence(current) && isLeftAssociative(current)))) {
				output.push_back(string(1, operators.top()));
				operators.pop();
			}
			operators.push(current);
		}
	}

	// 스택에 남은 연산자 모두 출력
	while (!operators.empty()) {
		output.push_back(string(1, operators.top()));
		operators.pop();
	}

	return output;
}

int main() {
	string expression = "(3 + 4) * 5 - 6"; // 공백 없이 입력

	vector<string> result = shuntingYard(expression);

	cout << "후위 표기법: ";
	for (const string& token : result) {
		cout << token << " ";
	}
	cout << endl;

	return 0;
}

 

설명:

• precedence 함수: 연산자의 우선순위를 반환합니다.
• isLeftAssociative 함수: 연산자가 좌결합성인지 확인합니다.
• shuntingYard 함수: 중위 표기법 수식을 입력받아 후위 표기법으로 변환한 결과를 반환합니다.

 

---

5. Shunting Yard Algorithm의 장점

1. 간결성: 괄호를 없애고 연산자의 우선순위와 결합성을 명확히 유지하면서 수식을 계산할 수 있습니다.
2. 효율성: 연산자 스택을 사용해 수식을 효율적으로 변환하고 계산할 수 있습니다.
3. 광범위한 사용: 계산기와 같은 수식 파싱에 널리 사용되며, 컴파일러나 인터프리터에서도 수식을 처리할 때 활용됩니다.

 

---

예시 문제 : 백준 1918번