데이터 구조의 표현식 구문 분석: 표기법, 연관성 및 우선 순위 유형

게시 됨: 2020-10-07

구문 분석 은 형식 문법에 맞는 자연어 또는 컴퓨터 언어로 표현된 일련의 기호를 분석하는 프로세스입니다 . 데이터 구조에서의 표현식 구문 분석 은 산술 및 논리 표현식의 평가를 의미합니다. 먼저 산술 표현식이 어떻게 작성되는지 봅시다.

연산자나 괄호 역할을 할 수 있는 상수, 변수 및 기호를 사용하여 표현식을 작성할 수 있습니다. 이 모든 표현은 특정 규칙을 따라야 합니다. 이 규칙에 따라 표현식의 구문 분석은 문법에 따라 수행됩니다.

산술 표현식은 Notation 형식으로 표현됩니다 . 이제 산술에서 표현식을 작성하는 세 가지 방법이 있습니다.

중위 표기법
접두사(폴란드어) 표기법
후위(역 폴란드어) 표기법

그러나 표현식을 작성할 때 원하는 표현식의 출력은 동일하게 유지됩니다. Notation 유형을 시작하기 전에 Data Structure의 Parsing 표현식에서 Associativity와 Precedence가 무엇인지 살펴보겠습니다.

초보자이고 데이터 과학에 대해 더 자세히 알고 싶다면 최고의 대학에서 제공하는 데이터 과학 과정을 확인하십시오.

읽기: 데이터 구조의 그래프

연관성

시작하기 전에 연관성 속성이 무엇인지 알아야 합니다. 유효한 증거를 제공하기 위해 표현식에서 괄호를 재배열하는 규칙을 제공합니다. 이는 괄호를 재배열할 때 상위 방정식과 동일한 값을 제공해야 함을 의미합니다. 연산자를 대체하는 유효한 규칙을 제공합니다.

두 개 이상의 연산자를 포함하는 표현식에서 피연산자의 순서가 바뀌지 않는 한 수행된 연산은 중요하지 않습니다. 표현식이 괄호와 중위어를 사용하여 작성된 경우 위치를 변경해도 값이 변경되지 않습니다.

인도 유럽 언어에서 표현식은 왼쪽에서 오른쪽으로 읽히기 때문에 대부분의 중위 연산자는 왼쪽 연관입니다. 연산자는 동일한 우선 순위로 평가됩니다. 권력 상승은 중위 연산자를 고려하는 데 사용되는 규칙입니다. 접두사 연산자는 일반적으로 오른쪽 결합이고 후위 연산자는 왼쪽 결합입니다.

일부 언어에서는 연산자와 피연산자에 동일한 값이 제공되며, 여기서 연관성은 이 언어 시퀀스를 명시적으로 만드는 것으로 간주되지 않습니다. 일부 언어에서 연산자는 비연관적이지만 이는 대괄호를 사용하는 데 필요한 복잡한 표현식을 사용해야 하므로 프로그래머의 복잡성이 증가합니다.

데이터 구조의 우선 순위

우선 순위는 연산자가 표현식 문에서 따라야 하는 순서를 의미합니다. 이것은 중위 표기법으로 작업하는 동안 일반적으로 사용됩니다.

두 연산자 사이의 <operator> <operand> <operator> 피연산자 의 상황에서 연산자를 할당하는 선호도는 상당히 까다롭습니다. 따라서 연산자 우선 순위 규칙을 따라 계산합니다. 예를 들어, 여기서 곱셈이 우선순위가 높으며, 나중에 덧셈 연산이 수행된다.

가장 일반적이지만 그렇게 명확하지 않은 규칙은 곱셈과 나눗셈 연산이 더하기와 빼기 전에 수행되어야 한다는 것입니다. 일반적으로 동일한 방식으로 수집되므로 모든 운영자에게 동일한 중요성이 제공됩니다.
이 연산을 논리적 형식으로 보면 "and"와 "or"에 변형이 보입니다. 많은 언어가 "또는" 연산에 더 높은 우선 순위가 부여되는 동일한 중요성을 제공합니다. 일부 언어는 곱셈 또는 "&", "&" 더하기 "또는"을 동등한 우선 순위로 간주합니다. 여기서 대부분의 언어는 가장 높은 우선 순위로 산술 연산을 제공합니다.
우선 순위를 적절하게 할당하지 않아 오버로딩이 발생합니다. 많은 언어가 벡터 대수 표현식보다 부정(참/거짓) 더 높은 우선 순위를 제공하는 반면 일부 언어는 동일한 우선 순위를 제공합니다.

더 읽어보기: 데이터 구조 프로젝트 아이디어

표기법의 종류

이제 연산자 위치가 Notation 유형을 결정하는 방법을 알아보겠습니다.

1. 중위 표기법

중위 표기법에서 연산자는 피연산자 사이에 사용됩니다. 식을 읽는 동안 중위 표기법은 인간에게 매우 쉽습니다. 그러나 컴퓨터 알고리즘과 관련하여 중위 인수를 처리하는 데는 상당한 시간과 공간이 소요됩니다. 예: p + q

<피연산자> <연산자> <피연산자>

중위 표기법은 평가를 수행하기 위해 추가 정보가 필요합니다. 규칙은 연산자 Associativity , 예: p * ( q + r ) / s

연관성 규칙은 표현이 왼쪽에서 오른쪽으로 수행되어야 하므로 p에 의한 곱셈이 q를 나누기 전에 수행되어야 한다고 제안합니다.
유사하게, 우선순위에 대한 규칙은 덧셈과 뺄셈 연산이 수행되기 전에 곱셈과 나눗셈 연산이 수행되어야 한다고 제안합니다.

2. 접두사 표기법

여기서 연산자가 먼저 쓰여지고 피연산자가 뒤따릅니다. 폴란드 표기법이라고도 합니다. 예: +pq

<연산자> <피연산자> <피연산자>

예: p * ( q + r ) / s

평가는 왼쪽에서 오른쪽으로 수행해야 하며 대괄호는 등식 패턴을 변경하거나 변경하지 않습니다. 여기서 덧셈은 '*'의 왼쪽에 '+' 위치가 있으므로 곱하기 전에 덧셈을 완료해야 합니다.

여기에서 모든 연산자는 바로 왼쪽에 있는 값에 대해 연산을 수행합니다. 예를 들어 위의 "+"는 "q"와 "r"을 사용합니다. 이를 명확히 하기 위해 괄호를 요약할 수 있습니다.

((p (qr +) *) s /)

따라서 “( )”는 “p” 바로 앞의 두 값과 +의 결과를 고려하여 사용합니다. 마찬가지로 "/"는 곱셈 표현식과 "s"의 결과를 사용합니다.

3. 후위 표기법

주로 피연산자인 후위 표기법이 작성되고 그 뒤에 연산자가 옵니다. 역 폴란드 표기법이라고도 합니다(예: pq+).

<피연산자> <피연산자> <연산자>
Postfix의 경우 Prefix와 동일하게 표현식의 연산이 왼쪽에서 오른쪽으로 이루어지며 “( )”는 불필요합니다. 여기에서 연산자는 오른쪽에서 가장 가까운 두 값에 대해 수행합니다. 아래 예에서는 평가에 영향이 없음을 명확히 하기 위해 대괄호를 불필요하게 추가했습니다.
(/ (* p (+ qr) ) s)
여기서 "연산자 평가는 왼쪽에서 오른쪽으로" 작업 값은 오른쪽에 있으며 값 자체에 계산이 포함된 경우 평가 순서가 변경됩니다. 위에 나열된 예에서 "/"는 왼쪽의 기본 연산자입니다.

곱셈 연산이 완료될 때까지 기다립니다. 그리고 우선 나눗셈이 시작되기 전에 곱셈 연산을 수행해야 합니다(위의 예에서 곱셈 연산 전에 덧셈 연산이 완료되어야 함을 알 수 있습니다).
접미사 표기법 연산자는 오른쪽에 있는 값을 사용하기 때문입니다. 계산과 관련된 모든 값은 왼쪽으로 이동할 때 계산이 이미 완료된 것입니다. 따라서 표현식 계산은 Prefix 연산자 연산과 같지 않다는 결론을 내릴 수 있습니다.
세 가지 표기법을 모두 강조 표시하려면 피연산자가 같은 순서로 표시되고 연산자는 계산 중에 올바른 의미를 제공하도록 이동해야 합니다. 비대칭 연산자 "-" 및 "/"를 고려할 때 pq가 동일한 값을 갖지 않는 한 항상 qr임을 분명히 하기 위해 이것은 특히 고려되어야 합니다. 값은 "pq -" 또는 "-pq"와 동일합니다.

p+q ≡ +pq ≡ pq+
예:
중위 - p * q + r / s
접두사 – pq * rs / +
사후 수정 – + * pq / rs
먼저 연산을 수행하려면 p와 q를 곱하고 나중에 r을 s로 나누고 마지막으로 결과를 더합니다.
세 가지 표기법 사이의 표 요약 아래,
중위 표기법 폴란드 표기법 역 폴란드어 표기법
p+q +pq pq+
(p+q)*r ++pq pqr++*
p*(q+r) *p+qr pqr**+ +
p÷q+r÷s +÷pq÷rs pq÷rs÷+
(pq)*(rs) *-pq-rs pq-rs-*
표기법 간의 변환
*명확한 통찰력을 제공하기 위해 식에 괄호를 추가합니다.

중위 접미사 접두사
( (p * q) + (r / s) ) ( (pq *) (rs /) +) (+ (* pq) (/ rs) )
((p * (q + r) ) / s) ( (p (qr +) *) s /) (/ (* p (+ qr) ) s)
(p * (q + (r / s) ) ) (p (q (rs /) +) *) (* 피 (+ q (/ rs) ) )
괄호 안의 연산자(예: (m + n) 또는 (mn +) 또는 (+ mn))를 사용하여 괄호 안의 형식에서 직접 변환을 시작할 수 있습니다. 이제 원하지 않는 대괄호를 제거하여 모든 연산자에서 이 작업을 반복합니다.
이제 위에 표시된 이 트릭을 사용하여 트리를 변환하고 구문 분석합니다. 각 노드에 해당하는 구문 분석 트리는 다음과 같습니다.
체크아웃: Python의 데이터 구조 및 알고리즘
결론
데이터 구조의 식 구문 분석 , 중위, 접미사 및 산술 식의 접두사 표기법은 상당히 다르지만 식을 작성하는 방법은 같습니다. 이에 대한 지식은 프로그램 작성에 필수적입니다.
컴퓨터 프로그래밍 언어에서 표현식은 문자열에서 고려되고 구문 분석됩니다. 연관성 및 우선 순위 규칙은 다른 언어에서 상당히 변경됩니다.
upGrad와 함께 데이터 과학 과정을 선택하는 이유는 무엇입니까?
데이터 과학은 컴퓨터 과학에서 급성장하는 분야 중 하나입니다. 기업은 코딩 언어와 상관없이 프로그래밍의 기본이 되는 기본을 잘 아는 프로그래머가 필요합니다.
upGrad는 데이터 과학자가 되기 위한 모든 기본 요구 사항을 다루는 통찰력 있고 유익한 수업을 제공하는 데 중점을 둡니다. 데이터 과학에서 upGrad의 12개월 경영자 PG 프로그램. , IIIT Bangalore에서 제공하는 인도 최초의 NASSCOM 인증 과정으로, 모든 필수 프로그래밍 언어, 도구 및 라이브러리를 다루는 데이터 과학 산업 전문가의 1:1 맞춤형 멘토링이 제공됩니다. 고임금 데이터 과학 작업을 시작할 수 있는 최고의 기반을 제공합니다.
데이터 구조란 무엇입니까?
데이터 구조는 메모리의 데이터를 구성하는 데 사용됩니다. 배열, 목록, 스택, 대기열 및 기타 여러 가지를 포함하여 메모리에 데이터를 정렬하는 몇 가지 방법이 있습니다. 데이터 구조는 C, C++ 또는 Java와 같은 프로그래밍 언어가 아닙니다. 대신 모든 프로그래밍 언어에서 메모리의 데이터를 정렬하는 데 사용되는 일련의 기술입니다. 데이터 구조는 데이터를 효율적으로 구성, 처리 및 저장하는 방법입니다. 데이터 항목은 데이터 구조의 도움으로 간단히 탐색할 수 있습니다. 프로그램의 주요 작업은 가능한 한 빨리 사용자 데이터를 저장하고 검색하는 것이기 때문에 프로그램의 속도를 향상시키는 데 중요합니다.
데이터 구문 분석의 실제 용도는 무엇입니까?
데이터를 한 형식에서 다른 형식으로 변환하는 프로세스를 데이터 구문 분석이라고 합니다. 컴퓨터 코드를 구문 분석하고 기계어 코드를 생성하기 위해 컴파일러에서 광범위하게 사용됩니다. 데이터를 한 형식에서 다른 형식으로 변환하는 프로세스를 데이터 구문 분석이라고 합니다. 우리가 받는 원시 HTML은 이해하기 어렵기 때문에 파서는 종종 온라인 스크래핑에 사용됩니다. 데이터를 사람이 읽을 수 있는 형식으로 변환해야 합니다. 이것은 HTML 문자열이나 표를 사용하여 보고서를 작성하여 가장 관련성이 높은 정보를 제공함을 의미할 수 있습니다.
연관성 및 우선 순위는 데이터 구조화에 어떻게 도움이 됩니까?
표현식의 평가 순서는 연산자의 두 가지 속성인 우선 순위와 연관성에 의해 결정됩니다. 우선 순위는 식의 용어를 그룹화하고 식을 평가하는 방법을 설정하는 데 도움이 됩니다. 대부분의 표현식은 BODMA 프레임워크를 사용하기 때문에 특정 연산자가 다른 연산자보다 우선합니다. 표현식에서 두 연산자의 우선 순위가 같으면 연관성 규칙이 적용됩니다. 컴파일러의 기본 설정에 따라 연관성은 왼쪽에서 오른쪽 또는 오른쪽에서 왼쪽일 수 있습니다.