션팅야드 알고리즘

Shunting-yard algorithm

컴퓨터 과학에서 션팅 야드 알고리즘은 산술적 또는 논리적 표현식 또는 둘의 조합을 구문 분석하는 방법이며, infix 표기법으로 지정되어 있다.RPN(Reverse Follish 표기법)이라고도 하는 사후 처리 표기법 문자열 또는 추상 구문 트리(AST)를 생성할 수 있다.[1]이 알고리즘은 Edsger Dijkstra에 의해 발명되었고 그것의 운영이 철도 션팅 야드의 그것과 닮았기 때문에 "분쇄 야드" 알고리즘으로 명명되었다.Dijkstra는 처음에 MR 34/61의 Matheatisch Centrum 보고서에서 션팅 야드 알고리즘을 설명했다.

RPN의 평가와 마찬가지로 션팅 야드 알고리즘은 스택 기반이다.인픽스 표현은 대부분의 사람들이 익숙한 수학 표기법 형태인데, 예를 들어 "3 + 4" 또는 "3 + 4 × (2 - 1)"이다.변환의 경우 입력 및 출력인 두 개의 텍스트 변수(스트링)가 있다.출력 대기열에 아직 추가되지 않은 연산자를 고정하는 스택도 있다.변환하기 위해 프로그램은 각 기호를 순서대로 읽고 그 기호를 바탕으로 무언가를 한다.위의 예에 대한 결과는 (역 폴란드어 표기법에서) 각각 "3 4 +"와 "3 4 2 1 - × +"가 될 것이다.

션팅 야드 알고리즘은 모든 유효한 인픽스 식을 올바르게 구문 분석하지만 모든 유효하지 않은 식을 거부하지는 않는다.예를 들어 "1 2 +"는 유효한 infix 표현식은 아니지만 "1 + 2"로 구문 분석된다.그러나 알고리즘은 일치하지 않는 괄호가 있는 식을 거부할 수 있다.

션팅 야드 알고리즘은 나중에 운영자 사전 준비 구문 분석으로 일반화되었다.

단순 변환

  1. 입력: 3 + 4
  2. 출력 대기열로 3을 푸시하십시오(숫자를 읽을 때마다 출력 대기열로 푸시됨).
  3. +(또는 ID)를 연산자 스택으로 푸시
  4. 출력 대기열에 4 밀어넣기
  5. 식을 읽은 후 연산자를 스택에서 꺼내어 출력에 추가하십시오.
    이 경우 "+"는 하나만 있다.
  6. 출력: 3 4 +

여기에는 이미 다음과 같은 몇 가지 규칙이 표시된다.

  • 읽으면 모든 숫자가 출력된다.
  • 식을 읽은 후에 모든 연산자를 스택에서 꺼내고 출력에 올리십시오.

그래픽 일러스트레이션

Shunting yard.svg

3방향 철도 연결을 사용한 알고리즘의 그래픽 그림.입력은 한 번에 하나의 기호를 처리한다. 변수나 숫자가 발견되면 출력 a), c), e), h)로 직접 복사된다.기호가 연산자일 경우 연산자 스택 b), d), f)로 밀린다.연산자의 우선순위가 스택 상단에 있는 연산자의 우선순위보다 낮거나 선행 조건이 동일하고 연산자가 연관성을 유지하면, 그 연산자는 스택에서 튀어나와 출력 g)에 추가된다.마지막으로, 나머지 연산자는 스택에서 튀어나와 출력 i)에 추가된다.

알고리즘 세부 정보

중요한 용어는 토큰(파서), 함수(수학), 연산자 연관성 및 운영 순서를 참조하십시오.
/* 이 구현은 복합함수, 변수 개수의 함수와 단항 연산자를 구현하지 않는다.*반면 또 토큰을 읽을 수 있는 시간이 토큰이:-:출력 큐-함수에 넣:연산자 스택-교환원 o1에 이를 추진하는 동안(는 연산자 o2 토큰의 많은 읽고 있는 연산자 스택의 맨 위에서 왼쪽 괄호 및 전기o2 하보다 다른.so1보다 높은 순위 또는 그들이 같은 선행과 o1 있는 것은left-associative-)연산자 스택에:연산자 스택의 출력 큐로 팝 o2 푸시 o1-왼쪽 괄호(즉"("):연산자 스택- 올바른 괄호(즉")")에 밀:톤일 때는 연산자그는 t연산자 스택의 op은 왼쪽 괄호가 아님: { 연산자 스택이 비어 있지 않다고 가정함} /* 왼쪽 괄호를 찾지 못하고 스택이 소진되면 일치하지 않는 괄호가 있다. */ 연산자 스택에서 연산자를 출력 대기열 {operator 스택 상단에 왼쪽 괄호가 있음}에 연산자 스택에서 왼쪽 괄호를 열고 연산자 스택 상단에 함수 토큰이 있으면 삭제한 다음: 연산자 스택에서 함수를 팝업하십시오.또는 출력 대기열로 스택 /* 작업자 스택의 나머지 항목을 출력 대기열로 팝업하십시오. */ 연산자 스택에 토큰이 있는 동안: /* 스택 상단에 있는 연산자 토큰이 괄호라면 일치하지 않는 괄호가 있다. */ {스택 위에 있는 연산자가 (왼쪽) 괄호가 아님}이(가) 연산자 스택에서 출력 대기열로 연산자를 팝업

이 알고리즘의 실행 시간 복잡성을 분석하려면 각 토큰을 한 번 읽고, 각 숫자, 함수 또는 연산자를 한 번 출력하고, 각 함수, 연산자 또는 괄호를 스택에 밀어넣어 스택에서 한 번 튀어나오게 된다는 점만 유의하면 된다. 따라서 t당 실행된 연산 수가 최대 일정하게 된다.OKen, 그리고 실행 시간은 따라서 O(n)—입력 크기로 선형이다.

션팅 야드 알고리즘은 접두사 표기법(폴란드 표기법이라고도 함)을 제작하는 데도 적용할 수 있다.이렇게 하려면 단순히 구문 분석할 토큰 문자열의 끝에서 시작하여 뒤로 작동하며, 출력 대기열을 반대로 하고(따라서 출력 대기열을 출력 스택으로 만들기), 왼쪽 및 오른쪽 괄호 동작을 뒤집으십시오(지금 왼쪽 괄호 동작이 현재 오른쪽 괄호를 찾을 때까지 팝업되어야 함을 기억함).그리고 연관성 조건을 오른쪽으로 바꾼다.

상세 예시

입력: 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 − ^ ÷ + ^의 우선 순위가 precedence보다 높음
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 ^ ^ ÷ +

입력: 죄 (최대 (2, 3 ) ÷ 3 × )

토큰 액션 출력 =
(RPN)		 연산자
쌓다		 메모들
죄를 짓다 스택에 토큰 푸시 죄를 짓다
( 스택에 토큰 푸시 (죄악)
맥스. 스택에 토큰 푸시 최대(죄)
( 스택에 토큰 푸시 (최대 (죄)
2 출력에 토큰 추가 2 (최대 (죄)
, 무시 2 (최대 (죄)
3 출력에 토큰 추가 2 3 (최대 (죄)
) 출력할 팝업 스택 2 3 (최대 (죄) 스택의 맨 위에 "(") 있을 때까지 반복
팝 스택 2 3 최대(죄) 일치하는 괄호 삭제
출력할 팝업 스택 2 3 max (죄악) 스택 맨 위에 있는 기능
÷ 스택에 토큰 푸시 2 3 max ÷ (죄)
3 출력에 토큰 추가 2 3 최대 3 ÷ (죄)
× 출력할 팝업 스택 2 3 max 3 ÷ (죄악)
스택에 토큰 푸시 2 3 max 3 ÷ × (죄)
π 출력에 토큰 추가 2 3 max 3 ÷ π × (죄)
) 출력할 팝업 스택 2 3 max 3 ÷ × (죄악) 스택의 맨 위에 "(") 있을 때까지 반복
팝 스택 2 3 max 3 ÷ × 죄를 짓다 일치하는 괄호 삭제
출력할 팝업 스택 2 3 max 3 ÷ ÷ × 죄 스택 맨 위에 있는 기능
종지부를 찍다 전체 스택을 출력으로 팝업 2 3 max 3 ÷ ÷ × 죄

참고 항목

참조

  1. ^ Theodore Norvell (1999). "Parsing Expressions by Recursive Descent". www.engr.mun.ca. Retrieved 2020-12-28.

외부 링크