从堆栈创建抽象语法树

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。