차량기지 알고리즘

3. 알고리즘 상세

입력이 아직 남아있는 동안 다음을 반복한다.

• 입력에서 토큰을 읽어들인다.
• 토큰이 숫자 또는 변수이면 출력 큐에 넣는다.
• 토큰이 함수이면 연산자 스택에 푸쉬한다.
• 토큰이 함수 인자의 구분자(예: 쉼표)이면
• 스택에서 여는 괄호 '(' 가 나타날 때까지 팝하여 출력 큐에 넣는다. 만약 여는 괄호가 나타나지 않으면 구분자의 위치가 잘못되었거나 여는 괄호와 닫는 괄호가 맞지 않는 것이므로 오류를 출력한다.
• 토큰이 연산자 o₁이면, 연산자 스택의 맨 위에 연산자가 없을 때까지 다음을 반복한다.
• 만약 스택에 연산자 o₂가 있다면
• o₁이 왼쪽 결합 연산자이고, 연산의 우선순위가 o₂와 같거나 그보다 낮을 경우,
• 또는 o₁이 오른쪽 결합 연산자이고, 우선순위가 o₂보다 낮을 경우

• 만약 스택에 연산자가 없거나 o₂가 조건을 만족하지 않으면 o₁을 연산자 스택에 푸쉬한다.
• 토큰이 여는 괄호 '(' 일 경우 연산자 스택에 푸쉬한다.
• 토큰이 닫는 괄호 ')' 일 경우
• 연산자 스택에서 여는 괄호가 나타날 때까지 연산자를 팝하여 출력 큐에 넣는다.
• 연산자 스택에서 여는 괄호가 나타나면 팝하되, 출력 큐에는 넣지 않는다.
• 스택을 모두 팝할 때까지 여는 괄호를 찾지 못했다면 괄호가 맞지 않는 것이므로 오류를 출력한다.
• 여는 괄호를 팝한 후 스택 맨 위에 함수 토큰이 남아있다면 출력 큐에 넣는다.

• 연산자 스택이 빌 때까지 토큰을 팝한다.
• 만약 스택에 여는 괄호나 닫는 괄호가 남아있다면 괄호가 맞지 않는 것이므로 오류를 출력한다.
• 그 외의 연산자는 출력 큐에 넣는다.

4. 예제

차량기지 알고리즘을 적용한 예시는 다음과 같다.

`3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3` 수식을 예로 들면 다음과 같다.

먼저, 연산자 우선순위 및 결합 방향은 다음과 같다.^[1]

기호 ^는 지수 연산자를 나타낸다.

이 표를 바탕으로, 각 토큰 별 알고리즘 동작, 출력(역폴란드 표기법) 및 연산자 스택 변화는 다음과 같이 요약할 수 있다.

결과적으로, 중위 표기법 `3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3`은 차량기지 알고리즘을 통해 역폴란드 표기법 `3 4 2 * 1 5 - 2 3 ^ ^ / +`로 변환된다.

4. 1. 간단한 예제

• 모든 숫자는 읽는 즉시 출력에 추가된다.
• 식을 다 읽었으면, 스택에서 모든 연산자를 팝하고 출력에 추가해 나간다.

4. 2. 상세한 예제

최종적으로, 출력 큐에는 `3 4 2 * 1 5 - 2 3 ^ ^ / +` 와 같은 역폴란드 표기법 수식이 생성된다.

5. 복잡도

모든 연산자, 괄호 및 숫자는 단 한 번만 입력에서 읽고, 최대 한 번만 출력 큐에 입력된다. 연산자 및 괄호는 최대 한 번만 스택에 푸시된 후 팝되므로, 모든 입력 토큰에 대해 최대 몇 개의 연산만이 수행된다. 따라서 알고리즘의 실행 시간은 입력 길이에 비례하며, 대문자 O 표기법으로는 O(''n'')이다. 즉, 입력 데이터가 많아져도 처리 시간은 선형적으로 증가하여 효율적이다.

6. 구현 예시 (C 언어)

cpp

#include

#include

#include

// 연산자 우선순위 반환

int op_preced(const char c)

{

switch (c) {

case '!': return 4;

case '*': case '/': case '%': return 3;

case '+': case '-': return 2;

case '=': return 1;

default: return 0;

}

}

// 연산자 결합성(좌결합성 또는 우결합성) 판별

bool op_left_assoc(const char c)

{

switch (c) {

case '*': case '/': case '%': case '+': case '-': return true; // 좌결합성

case '=': case '!': return false; // 우결합성

default: return false;

}

}

// 연산자의 피연산자 개수 반환

unsigned int op_arg_count(const char c)

{

switch (c) {

case '*': case '/': case '%': case '+': case '-': case '=': return 2;

case '!': return 1;

default: return c - 'A'; // 함수의 경우, A()는 0개, B()는 1개, C()는 2개...

}

}

// 토큰 유형 판별 매크로

#define is_operator(c) (c == '+' || c == '-' || c == '/' || c == '*' || c == '!' || c == '%' || c == '=')

#define is_function(c) (c >= 'A' && c <= 'Z')

#define is_ident(c) ((c >= '0' && c <= '9') || (c >= 'a' && c <= 'z'))

// Shunting Yard 알고리즘 구현: 중위 표기법 -> 후위 표기법 변환

bool shunting_yard(const char *input, char *output)

{

const char *strpos = input, *strend = input + strlen(input);

char c, *outpos = output;

char stack[32]; // 연산자 스택

unsigned int sl = 0; // 스택 길이

char sc; // 스택 요소 기록용

while (strpos < strend) {

c = *strpos++;

if (c == ' ') {

continue; // 공백 무시

} else if (is_ident(c)) {

• outpos++ = c; // 식별자는 출력 큐에 추가

• outpos++ = sc;

• outpos++ = sc;

• outpos++ = sc;

• outpos++ = sc;

• outpos++ = sc;

• outpos = 0; // 출력 문자열 종료

• -nargs;

• `op_preced` 함수: 연산자의 우선순위를 반환한다.
• `op_left_assoc` 함수: 연산자의 결합성(좌/우)을 판별한다.
• `op_arg_count` 함수: 연산자에 필요한 피연산자 개수를 반환한다.
• `shunting_yard` 함수: 차량기지 알고리즘을 구현하여 중위 표기법을 후위 표기법으로 변환한다.
• 입력 문자열을 토큰(피연산자, 연산자, 함수, 괄호 등)으로 분리한다.
• 연산자 우선순위와 결합성에 따라 스택을 조작한다.
• 후위 표기법으로 변환된 수식을 출력한다.
• `execution_order` 함수: 후위 표기법 수식을 바탕으로 실행 순서를 생성하고 출력한다.
• 피연산자는 스택에 푸시, 연산자는 스택에서 피연산자를 팝하여 연산 후 결과를 다시 푸시한다.
• 각 연산 단계를 출력한다.
• `main` 함수: 입력 예시를 설정하고, `shunting_yard`와 `execution_order` 함수를 호출한다.

• 함수, 식별자, 연산자를 명확히 구분한다.
• 괄호 불일치, 구분자 오류, 피연산자 부족 등의 오류를 처리한다.
• `#define` 매크로를 활용하여 코드 가독성을 높였다.

• 입력: `a = D(f - b * c + d, !e, g)`
• 출력: `afbc*-d+e!gD=`
• 실행 순서:

참조

_[1] 웹사이트 Parsing Expressions by Recursive Descent http://www.engr.mun.[...] 1999-01-01
_[2] 간행물 Algol 60 translation : An Algol 60 translator for the X1 and making a translator for Algol 60 https://ir.cwi.nl/pu[...] 1961-11-01
_[3] 문서
_[4] 논문 Algol 60 translation : An algol 60 translator for the x1 and making a translator for algol 60 http://repository.cw[...] Stichting Mathematisch Centrum 1961-01-01