나무와 접두사 (광택) 표기법에 대해?

StackOverflow https://stackoverflow.com/questions/523957

문제

MIPS 어셈블리 클래스는 알려지지 않은 크기의 표현으로 구문 분석 트리에 읽어야했습니다. 나는 나무를 다룰 필요가 없었기 때문에 이것이 내가 가치를 저장하는 방법입니다.

사용자가 표현 1 + 3-4를 입력했다고 가정 해 봅시다 (각 피연산자는 1-9 자리 일 수 있습니다).

내 왼쪽 자식 노드는 출발점이며 2 개의 데이터를 포함합니다.

1. The operand
2. Pointer to the next node (operator)

이것이 내가 나무를 만들어 낸 방법입니다. 더 이상 읽을 수없는 값이 없을 때까지 오페라에서 연산자, 다음 오페라로 다음 오퍼레이터로 향합니다.

다음 과제는 트리를 재귀 적으로 통과하고 값을 Infix/Prefix/PostFix 표기법으로 출력하는 것이 었습니다.

INFIX TRAVERSAL은 내가 나무를 어떻게 만들 었는지 고려할 때 아무런 문제가 없었습니다.

나는 접두사에 붙어 있습니다. 첫째, 나는 그것을 완전히 이해하지 못한다.

접두사에서 표현식 (1 + 3-4)을 출력 할 때 - + 1 3 4? 온라인 예제를 따르는 데 어려움이 있습니다.

또한 내 나무가 제대로 구성되었다고 생각하십니까? 내 말은, 나는 현재 노드에서 이전 노드로 갈 수있는 방법이 없다. 즉, TA가 갈 길이라고 말했지만 본능적으로 왼쪽 하위 노드에서 횡단을 시작해야한다는 것을 의미한다.

도움을 주셔서 감사합니다.

도움이 되었습니까?

해결책

구문 분석 트리는 다음과 같이 보일 것입니다.

        '-'
         |
     +---+---+
     |       |
    '+'     '4'
     |
 +---+---+
 |       |
'1'     '3'

각 노드에는 두 개의 포인터가 있습니다. 하나는 왼쪽 자녀와 하나는 오른쪽 자녀입니다. 재귀 횡단을 사용할 때는 부모 노드에 대한 포인터가 필요하지 않습니다.

여기 몇 가지 의사 코드가 있습니다.

트래버스 디스 픽스 표기법:

void traverse(Node *node) {
    if (node->leftChild != 0) {
        traverse(node->leftChild);
    }

    print(node->value);

    if (node->rightChild != 0) {
        traverse(node->rightChild);
    }
}

트래버스 접두사 표기법:

void traverse(Node *node) {
    print(node->value);

    if (node->leftChild != 0) {
        traverse(node->leftChild);
    }

    if (node->rightChild != 0) {
        traverse(node->rightChild);
    }
}

트래버스 포스트 픽스 표기법:

void traverse(Node *node) {
    if (node->leftChild != 0) {
        traverse(node->leftChild);
    }

    if (node->rightChild != 0) {
        traverse(node->rightChild);
    }

    print(node->value);
}

당신은 전화 할 것입니다 traverse 트리의 루트 노드가있는 메소드.

당신의 Node 데이터 구조에는 세 명의 구성원이 필요합니다.

struct Node {
    char value;
    Node *leftChild;
    Node *rightChild;
}

나무의 잎에는 널 포인터가 들어 있습니다. leftChild 그리고 rightChild.

때로는 문제를 이해 한 다음이 코드를 어셈블러로 "번역"하기 위해이 내용을 더 높은 수준의 언어 (편안하게 느끼는 것)로 작성하는 데 도움이됩니다. 나는 프로그래밍을 기억한다 세계를 차단합니다 이와 같은 MIPS 어셈블러의 시뮬레이션.

다른 팁

일반적으로 모든 잎 노드 (어린이가없는 사람)가 피연산자이고 내부 노드 (다른 모든)가 연산자가되는 방식으로 트리를 구성해야합니다. 이는 운영자 노드의 어린이가 오페라 또는 피연산자가있는 운영자가되도록해야합니다. 이런 식으로 트리를 구성 할 수 있다면 다양한 표기법 (접두사, Postfix, Infix)을 형성하는 것이 상당히 간단합니다. 잘 알려진 알고리즘이있는 트리의 선주문, 우편 주문형 및 interder 트래버스를 따릅니다.

내가 알 수있는 한, 당신은 나무를 만들지 않고 링크 된 목록을 만들지 않으며, 이것은 당신을 잘 섬기지 않을 것입니다. 피연산자와 운영자의 2 가지 엔티티가 있습니다. 다르게 취급해야합니다.

나는 Sykora가 말하는 것에 동의합니다. 이 경우 스택을 사용할 수도 있다고 덧붙이고 싶습니다. 과제에 트리를 구체적으로 사용하도록 요구하는 경우 Sykora의 제안이 가장 잘 작동합니다. 그러나 간단한 표현 평가를 위해 스택이 더 쉬울 수 있습니다.

이것은 컴파일의 일반적인 문제의 사례이며, 이는 해결 된 문제입니다. 컴파일 기술에 대한 Google을 수행하는 경우 문제와 관련된 모든 종류의 정보를 찾을 수 있습니다.

도서관에는 사본이 있어야합니다 컴파일러 : 원리, 기술 및 도구 Aho, Sethi 및 Ullman. 가지고 있지 않은 경우 구매를 요청하십시오 (현장의 표준 작업입니다). 그것의 첫 번째 부분이 당신을 도울 것입니다.

세 번째 판 링크

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top