從堆棧創建抽象語法樹

Question

我正在研究一個項目，我需要評估一個反向波蘭表示法或將rpn表達式轉換爲中綴表示法。我通過將表達式的所有元素推入堆棧然後從堆棧中彈出每個元素並將其插入到抽象語法樹中來完成此操作。從那裏我將遍歷樹來完成評估和轉換操作。這是我到目前爲止

#include <stdlib.h> 
#include <ctype.h> 
#include <stdio.h> 
#include <string.h> 

struct snode 
{ 
    char datum; 
    struct snode* bottom; 
}; 

struct tnode 
{ 
    char datum; 
    struct tnode* left; 
    struct tnode*right; 
}; 

struct snode* 
push(struct snode* stack, char x) { 
    struct snode *S = (struct snode*)malloc(sizeof(struct snode)); 
    S->datum = x; 
    S->bottom = stack; 
    return S; 
} 

struct snode* 
pop(struct snode* stack) { 
    struct snode *S; 
    if (stack == NULL) 
    return NULL; 
    S = stack->bottom; 
    free(stack); 
    return S; 
} 

char 
peek(struct snode* stack){ 
    return stack->datum; 
} 


struct tnode* 
create_node(char x){ 
    struct tnode* tmp; 
    tmp = (struct tnode*)malloc(sizeof(struct tnode)); 
    tmp->datum = x; 
    tmp->right = NULL; 
    tmp->left = NULL; 
    return tmp; 
} 

void 
print_table(struct tnode *AST){ 
    if(AST !=NULL){ 
    print_table(AST->left); 
    printf("%c ", AST->datum); 
    print_table(AST->right); 
    } 
} 



struct tnode* 
build_tree(struct snode *S) 
{ 

    struct tnode* root; 
    if (S == NULL) 
    return NULL; 

    char top = peek(S); 

    if (top == 'A' || top == 'S' || top == 'X' || top == 'D' || top == 'M') 
    { 
     root = create_node(top); 
     S = pop(S); 
     root->right = build_tree(S); 
     S = pop(S); 
     root->left = build_tree(S); 
     return root; 
    } 

    root= create_node(top); 

    return root; 
} 


int 
main(int argc, const char *argv[]) 
{ 

    int i = 1; 
    struct tnode *tree = NULL; 
    struct snode *stack = NULL; 

    char value; 
    while (argv[i]!= NULL) 
    { 
     value = argv[i][0]; 
     stack = push(stack, value); 
     i++; 
    } 


    tree = build_tree(stack); 
    print_table(tree); 
    printf("\n"); 

    return EXIT_SUCCESS; 
} 

我的問題是，此代碼只對每個rpn表達式不起作用。例如：

./project 7 4 A 3 S 

輸出

7 A 4 S 3 

這是正確的。但

./project 1 2 X 3 4 X A 

輸出

A 3 X 4 

這顯然是不正確的。林肯定我的問題是在我的build_tree函數，但我不知道如何以不同的方式做一個build_tree。 此外，當我有作爲

./project 12 3 D 2 D 

這樣的表達式的輸出是怎麼來的

1 D 3 D 2 

，而不是

12 D 3 D 2 

謝謝所有幫助。任何有關如何更改我的代碼以使項目的其餘部分更簡單的輸入也值得讚賞！

Answer 1

主要問題是當您在build_tree()函數中下降多個級別時，堆棧的「更新」不會被記住。例如，當您執行root->right = build_tree(S);並且在與build_tree()調用的上下文中彈出堆棧時，堆棧實際上並未在調用者的上下文中彈出。

我建議你根據這樣的改變您的功能：

void 
pop(struct snode **stack) { 
    struct snode *S; 
    if (*stack == NULL) 
    return; 

    S = (*stack)->bottom; 
    free(*stack); 
    *stack = S; 
} 


struct tnode* 
build_tree(struct snode **S) 
{ 

    struct tnode* root; 
    if (*S == NULL) 
    return NULL; 

    char top = peek(*S); 

    if (top == 'A' || top == 'S' || top == 'X' || top == 'D' || top == 'M') 
    { 
     root = create_node(top); 
     pop(S); 
     root->right = build_tree(S); 
     pop(S); 
     root->left = build_tree(S); 
     return root; 
    } 

    root = create_node(top); 

    return root; 
} 

int 
main(int argc, const char *argv[]) 
{ 
    ... 

    tree = build_tree(&stack); 

    ... 
} 

的差別變得更加明顯，如果你添加一個printf()調用peek()，你輸出的訪問協議棧節點的數據。

爲其他錯誤，其中./project 12 3 D 2 D不工作，並12被替換爲1，我會建議你使用atoi()函數將字符串轉換爲整數，而不是僅僅value = argv[i][0]。你可以測試value是否是一個數字，如果是的話，之後是value = atoi(argv[i])。

另外，正如Nikolai所述，您需要定義運算符優先級規則，並根據需要添加括號。最簡單的方法是在每次離開前添加一個左括號，並在每次從右側返回後添加右括號。

編輯

還要注意的是1 2 X 3 4 X A *無效RPN，而1 2 X 3 4 X A是（因爲額外*沒有匹配的右操作符）。

編輯2

一種用於支持多位數可能是代替使用的字符的字符串來表示所有令牌溶液。你需要改變的char所有出現與char *在：

• 和該的struct snode定義struct tnode
• 的參數push()和create_node()
• 從peek()的返回值。
• 變量value in main() and top in build_tree()。

此外，你需要改變value = argv[i][0]簡單value = argv[i]（我也建議刪除從argv參數的const預選賽main()，除非你想成爲常量，正確的）。您還需要更改運算符相等性檢查。例如，你可以這樣做：

int 
is_operator(char *tok) 
{ 
    return !strcmp(tok, "A") || !strcmp(tok, "S") || !strcmp(tok, "X") || !strcmp(tok, "D") || !strcmp(tok, "M"); 
} 

，然後簡單地寫在if (is_operator(top))build_tree()。

最後，您需要將printf()格式的字符串從%c更改爲%s。