關於樹和前綴（波蘭語）符號？

我的MIPS Assembly類需要我將未知大小的表達式讀入分析樹。我從來沒有對付樹木，所以我這是怎麼繞到存儲值：關於樹和前綴（波蘭語）符號？

比方說，用戶輸入表達式1 + 3 - 4（每個操作數只能是數字1-9）

我最左邊的子節點將是起點，包含2個數據

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

的我這是怎麼構建的樹。我會從操作數指向運算符，直到下一個運算符指向下一個運算符，直到沒有更多值要讀入爲止。

我的下一個任務是遞歸遍歷樹並以infix/prefix/postfix表示法輸出值。

考慮到我如何構建樹，Infix遍歷不成問題。

我被困在前綴上。首先，我不完全理解它。

當我輸出我們的表達式（1 + 3 - 4）在前綴應該出來 - + 1 3 4？遵循在線示例我遇到了麻煩。

你也認爲我的樹構建正確嗎？我的意思是，我無法前往當前節點的前一個節點，這意味着我總是必須從最左側的子節點開始遍歷，即使我的TA說這是一條路，本能地聽起來不正確。

謝謝你的幫助。

來源

2009-02-07 VeePee

您解析樹應該是這個樣子：

 
     '-' 
     | 
    +---+---+ 
    |  | 
    '+'  '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彙編程序中編寫了一個blocks world模擬。

來源

2009-02-07 15:51:54 gclj5

一般而言，您應該構建一棵樹，使得所有葉節點（沒有子節點的）都是操作數，內部節點（其他所有節點）都是操作符。這應該是這樣的，一個運算符節點的孩子是它的操作數，或者是它們自己的操作符。如果你可以用這種方式構造一棵樹，形成各種符號（前綴，後綴，中綴）是相當簡單的 - 你只需按照前序，後序和樹的順序遍歷，這裏有衆所周知的算法。

據我所知，你不是構建一棵樹，而是一個鏈表，而這不會爲你服務。你有兩個不同的實體 - 操作數和操作符 - 你必須以不同的方式對待它們。

來源

2009-02-07 15:43:34 sykora

這就是我正要給的答案。謝謝sykora！ – Niyaz 2009-02-07 15:46:39

我同意sykora說的。我想補充一點，在這種情況下你也可以使用堆棧。如果你的任務需要你專門使用一棵樹，那麼sykora的建議將效果最好。但是，對於簡單表達式評估，堆棧可能更易於編程。

來源

2009-02-07 15:51:13 batbrat

這是編譯的一般問題的一個實例，這是一個解決的問題。如果你在編譯技術上做了谷歌搜索，你會發現有關你的問題的各種信息。

您的圖書館應該有一份Aho，Sethi和Ullman的編譯器：原理，技術和工具。如果沒有，請申請購買（這是該領域的標準工作）。它的第一部分應該可以幫到你。

Third edition link

來源

2009-02-07 15:59:35

關於樹和前綴（波蘭語）符號？

回答

相關問題