c - 如何评估二叉树(中序)？

Question

我正在尝试评估二叉树(中序)。结果始终保持不变相同或给出意想不到的答案。不知道问题出在哪里，可以有人帮助我吗？首先，我将后缀表达式转换为表达式树，然后评估表达式树。我将非常感激。

当我运行这个程序时，结果是出乎意料的。这是头文件。

#define POST2EXPTREE_H_INCLUDED
#define MAX 100

struct node
{
    char ch;
    struct node *left;
    struct node *right;
}  *stack[MAX];
typedef struct node node;
void push(node *str);
node *pop();
void convert(char exp[]);
void display(node *temp);

#endif

#include <stdio.h>
#include <stdlib.h>
#include"post2expTree.h"
#define SIZE 100

int top = -1;
void push(node *str)
{
    if (top >= MAX-1)
    printf("Stack is Full ");
    else
    {
        stack[top] = str;
        top++;
    }
}

node *pop()
{
    node *exp;
    if (top < 0)
        printf("Stack is Empty ");
    else
        exp = stack[--top];
    return exp;
}
void convert(char exp[])
{
    node *op1,  *op2;
    node *temp;
    int i;
    for (i=0;exp[i]!='\0';i++)
    if (exp[i] >= 'a'&& exp[i] <= 'z'|| exp[i] >= 'A' && exp[i] <= 'Z' ||isalnum(exp[i]))
    {
        temp = (node*)malloc(sizeof(node));
        temp->ch = exp[i];
        temp->right = NULL;
        temp->left = NULL;
        push(temp);
    }
    else if (exp[i] == '+' || exp[i] == '-' || exp[i] == '*' || exp[i] == '/' || exp[i] == '%'
|| exp[i] == '^')
    {
        op1 = pop();
        op2 = pop();
        temp = (node*)malloc(sizeof(node));
        temp->ch = exp[i];
        temp->right = op1;
        temp->left = op2;
        push(temp);
    }
}

void display(node *temp)
{
    if (temp != NULL)
    {
        display(temp->left);
        printf("%c", temp->ch);
        display(temp->right);
    }
}
int evaluate(node *temp)
{
    int left,right,value;
    if ((temp->ch) >= 0 || (temp->ch <=9))
    {
        return temp->ch;
    }
    else
    {
        left = evaluate(temp -> left);
        right = evaluate(temp -> right);

        switch(temp->ch)

        {

            case '+':
                value = left + right;
                break;

            case '-':
                 value = left - right;
                 break;


            case '*':
                 value = left * right;
                break;


            case '/':
                 value = left / right;
                break;


            case '%':
                 value = left % right;
                break;


            case '^':
                 value = left ^ right;
                break;


        }
        temp->ch = value;
    }
    return value;

}

Answer 1

    int top = -1;
    void push(node *str)
    {
        if (top >= MAX-1)
        printf("Stack is Full ");
        else
        {
            stack[top] = str;
            top++;
        }
    }

• 此处 top 初始化为 -1，第一个 push() 错误地访问了 stack[-1];通过将 else block 更改为 stack[++top] = str; 来更正该问题。

    node *pop()
    {
        node *exp;
        if (top < 0)
            printf("Stack is Empty ");
        else
            exp = stack[--top];
        return exp;
    }

• 此处，top 在访问stack 之前减一；通过将 else block 更改为 exp = stack[top--]; 来更正该问题。

    int evaluate(node *temp)
    {
        int left,right,value;
        if ((temp->ch) >= 0 || (temp->ch <=9))
        {
            return temp->ch;

• 这里您忘记了将操作数存储为单个数字 '0' 到 '9'，而不是值 0到9。通过更改为更正该问题:

      int left, right, value = temp->ch-'0';
      if (value >= 0 && value <= 9)
      {
          return value;