쇼트야드 알고리즘
Shunting yard algorithm |
| 학급 | 구문 분석 |
|---|---|
| 자료구조 | 쌓다 |
| 최악의 경우 성능 | |
| 최악의 경우 공간 복잡도 |
컴퓨터 과학에서 shuntyard 알고리즘은 산술 또는 논리식을 구문 분석하는 방법으로, infix 표기법으로 지정됩니다. RPN(Reverse Polish notation)이라고도 하는 후고정 표기 문자열 또는 AST(Abstract Syntax Tree)를 생성할 수 있습니다.[1] 그 알고리즘은 Edsger Dijkstra에 의해 발명되었고 그것의 작동이 철도 객차의 그것과 닮았기 때문에 " 객차 마당" 알고리즘이라고 이름 지었습니다. Dijkstra는 Mathematisch Centrum 보고서 MR 34/61에서 shuntyard 알고리즘을 처음 설명했습니다.
RPN의 평가와 마찬가지로 shuntyard 알고리즘은 스택 기반입니다. 이픽스 표현은 대부분의 사람들이 사용하는 수학적 표기법의 형태입니다. 예를 들어, "3 + 4" 또는 "3 + 4 × (2 - 1)"입니다. 변환의 경우 입력과 출력의 두 가지 텍스트 변수(문자열)가 있습니다. 출력 큐에 아직 추가되지 않은 연산자를 고정하는 스택도 있습니다. 변환하기 위해 프로그램은 각 기호를 순서대로 읽고 해당 기호를 기반으로 무언가를 수행합니다. 위의 예에 대한 결과는 각각 "34 +"와 "34 21 - × +"입니다.
shuntyard 알고리즘은 모든 유효한 infix 식을 올바르게 구문 분석하지만 모든 유효하지 않은 식을 거부하지는 않습니다. 예를 들어, "12 +"는 올바른 수식이 아니라 "1 + 2"로 구문 분석됩니다. 그러나 알고리즘은 괄호가 일치하지 않는 식을 거부할 수 있습니다.
쇼트 야드 알고리즘은 나중에 연산자 우선순위 구문 분석으로 일반화되었습니다.
단순 변환
- 입력 : 3 + 4
- 3을 출력 큐에 푸쉬합니다(숫자를 읽을 때마다 출력으로 푸쉬됩니다).
- +(또는 해당 ID)를 연산자 스택에 밀어 넣습니다.
- 출력 큐에 4를 밀어 넣습니다.
- 식을 읽은 후 연산자를 스택에서 꺼내고 출력에 추가합니다.
- 이 경우 "+"는 하나뿐입니다.
- 출력 : 34 +
여기에는 이미 몇 가지 규칙이 표시됩니다.
- 모든 숫자는 읽을 때 출력으로 푸시됩니다.
- 식을 읽을 때 모든 연산자를 스택에서 꺼내고 출력에 팝합니다.
그래픽 일러스트레이션
삼방향 철도 분기점을 이용한 알고리즘의 그래픽 그림. 입력은 한 번에 하나의 기호로 처리됩니다. 변수나 숫자가 발견되면 출력 a), c), e), h). 기호가 연산자인 경우 연산자 스택 b), d), f)에 푸시됩니다. 연산자의 우선 순위가 스택 상단의 연산자의 우선 순위보다 낮거나 우선 순위가 같고 연산자가 연관된 상태로 남아 있는 경우 해당 연산자는 스택에서 팝업되어 출력 g)에 추가됩니다. 마지막으로, 나머지 연산자는 스택에서 팝업되어 출력 i)에 추가됩니다.
알고리즘의 세부적인 내용은
/* 이 알고리즘에서 말하는 함수는 사인, 역, 계승과 같은 단순 단일 인수 함수입니다.*/ /* 이 구현은 복합 함수, 가변 수의 인수가 있는 함수 또는 단항 연산자를 구현하지 않습니다.*/ 읽을 토큰이 있는 반면: 토큰을 읽습니다: - 숫자: 출력 큐에 넣으십시오 - 함수: 연산자 스택에 밀어넣습니다 - 연산자1 o: 반면 (연산자 스택의 맨 위에 왼쪽 괄호가 아닌 연산자 o가2 있습니다.) 그리고 (o는2 o보다1 우선순위가 크거나(o와1 o는2 동일한 우선순위를 가지며 o는1 왼쪽 연관성이 있음): 연산자 스택에서 출력 큐로 popo21 - a,": 연산자 스택의 맨 위에 있는 연산자는 왼쪽 괄호가 아닙니다. 연산자 스택에서 연산자를 출력 큐 - 왼쪽 괄호 (") - 연산자 스택 - 오른쪽 괄호 ("") : 밀어 넣습니다. ")"(): 연산자 스택의 맨 위에 있는 연산자는 왼쪽 괄호가 아니지만: {연산자 스택이 비어 있지 않음을 확인합니다} /* 만약 스택이 왼쪽 괄호를 찾지 못하고 소진되면 일치하지 않는 괄호가 있습니다.*/ 연산자 스택의 연산자를 출력 큐 {연산자 스택의 상단에 왼쪽 괄호가 있습니다} 연산자 스택의 왼쪽 괄호를 연산자 스택의 상단에 함수 토큰이 있는 경우 이를 버립니다. {assert} 연산자 스택의 왼쪽 괄호를 팝하고 연산자 스택의 상단에 함수 토큰이 있는 경우 이를 버립니다. 그런 다음 연산자 스택의 함수를 출력 큐에 팝합니다. /* while loop 후 연산자 스택의 나머지 항목을 출력 큐에 팝합니다.*/ 연산자 스택에 토큰이 있는 반면: /* 스택 상단의 연산자 토큰이 괄호인 경우 일치하지 않는 괄호가 있습니다.*/ {assert 스택 상단의 연산자가 (왼쪽) 괄호가 아님} 연산자 스택에서 출력 대기열로 연산자를 팝합니다.
이 알고리즘의 실행 시간 복잡도를 분석하기 위해서는 각 토큰을 한 번 읽고, 각 숫자, 함수 또는 연산자를 한 번 인쇄하고, 각 함수, 연산자 또는 괄호를 한 번씩 스택에 밀어넣고, 한 번씩 스택에서 튀어나올 것이라는 점만 주목하면 됩니다. 따라서, 토큰당 실행되는 작업의 수는 많아야 일정하며, 따라서 실행 시간은 O(n)이며 입력 크기는 선형입니다.
쇼트 야드 알고리즘을 적용하여 접두사 표기법(폴란드 표기법이라고도 함)을 생성할 수도 있습니다. 이렇게 하려면 단순히 구문 분석하고 역방향으로 작업할 토큰 문자열 끝에서 시작하여 출력 큐를 역방향으로 되돌리고(따라서 출력 큐를 출력 스택으로 만들고) 왼쪽 및 오른쪽 괄호 동작을 뒤집습니다(지금 왼쪽 괄호 동작은 지금 오른쪽 괄호를 찾을 때까지 팝업해야 함을 기억). 그리고 연상 조건을 오른쪽으로 바꾸는 것.
상세예
Input: 3 + 4 × 2 ÷ ( 1 − 5 ) ^ 2 ^ 3
교환입니다. 우선순위 연합성 ^ 4 맞다 × 3 왼쪽 ÷ 3 왼쪽 + 2 왼쪽 − 2 왼쪽
기호 ^는 전력 연산자를 나타냅니다.
상품권 액션. 산출량
(RPN에서)교환입니다.
겹겹이 쌓다메모들 3 출력에 토큰 추가 3 + 토큰을 스택에 푸시 3 + 4 출력에 토큰 추가 3 4 + × 토큰을 스택에 푸시 3 4 × + × +보다 우선 순위가 높습니다. 2 출력에 토큰 추가 3 4 2 × + ÷ 출력할 팝업 스택 3 4 2 × + ÷ 및 ×는 동일한 우선순위를 갖습니다. 토큰을 스택에 푸시 3 4 2 × ÷ + ÷ +보다 우선 순위가 높습니다. ( 토큰을 스택에 푸시 3 4 2 × ( ÷ + 1 출력에 토큰 추가 3 4 2 × 1 ( ÷ + − 토큰을 스택에 푸시 3 4 2 × 1 − ( ÷ + 5 출력에 토큰 추가 3 4 2 × 1 5 − ( ÷ + ) 출력할 팝업 스택 3 4 2 × 1 5 − ( ÷ + "(") 찾을 때까지 반복 팝스택 3 4 2 × 1 5 − ÷ + 일치하는 괄호 폐기 ^ 토큰을 스택에 푸시 3 4 2 × 1 5 − ^ ÷ + ^ 우선 순위가 than보다 높습니다. 2 출력에 토큰 추가 3 4 2 × 1 5 − 2 ^ ÷ + ^ 토큰을 스택에 푸시 3 4 2 × 1 5 − 2 ^ ^ ÷ + ^ 오른쪽에서 왼쪽으로 평가됩니다. 3 출력에 토큰 추가 3 4 2 × 1 5 − 2 3 ^ ^ ÷ + 끝. 전체 스택을 출력으로 팝합니다. 3 4 2 × 1 5 − 2 3 ^ ^ ÷ +
입력 : sin (최대 (2,3) ÷ 3 × π)
상품권 액션. 산출량
(RPN에서)교환입니다.
겹겹이 쌓다메모들 죄악 토큰을 스택에 푸시 죄악 ( 토큰을 스택에 푸시 (죄) 맥스. 토큰을 스택에 푸시 최대(죄) ( 토큰을 스택에 푸시 (max (죄) 2 출력에 토큰 추가 2 (max (죄) , 무시 2 (max (죄) 스택의 맨 위에 있는 연산자는 왼쪽 괄호입니다. 3 출력에 토큰 추가 2 3 (max (죄) ) 출력할 팝업 스택 2 3 (max (죄) 스택의 상단에 "(")가 될 때까지 반복합니다. 팝스택 2 3 최대(죄) 일치하는 괄호를 폐기하는 중 출력할 팝업 스택 23 max (죄) 스택 상단의 함수 ÷ 토큰을 스택에 푸시 23 max ÷ (죄) 3 출력에 토큰 추가 23 max 3 ÷ (죄) × 출력할 팝업 스택 2 3 max 3 ÷ (죄) 토큰을 스택에 푸시 2 3 max 3 ÷ × (죄) π 출력에 토큰 추가 2 3 max 3 ÷ π × (죄) ) 출력할 팝업 스택 2 3 max 3 ÷ π × (죄) 스택의 상단에 "(")가 될 때까지 반복합니다. 팝스택 2 3 max 3 ÷ π × 죄악 일치하는 괄호를 폐기하는 중 출력할 팝업 스택 23 max 3 ÷ π × 죄 스택 상단의 함수 끝. 전체 스택을 출력으로 팝합니다. 23 max 3 ÷ π × 죄
참고 항목
참고문헌
- ^ Theodore Norvell (1999). "Parsing Expressions by Recursive Descent". www.engr.mun.ca. Retrieved 2020-12-28.
