c - 使用 C 中的表达式树计算后缀表达式

Question

我似乎无法让这个程序工作，它是表达式树的双向链表表示。创建树后，我需要评估结果，但我似乎不知道如何评估。

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
typedef struct node
{
    char item;
    struct node * left;
    struct node * right;
}*Btree;

Btree root;
void operandFunc(char);
void operatorFunc(char);
void push(Btree);
Btree pop();
void infix(Btree);
void postfix(Btree);
void prefix(Btree);
int solve(Btree);
int calculate(char,int,int);
int isOperand(char); 
char expression[25];
Btree stack[25];
int stackPtr = -1;

int main()
{
    int count = 0;
    printf("Please enter a postfix expression\n");
    while((expression[count++]=getchar())!='\n');
    expression[--count] = '\0';
    //puts(expression);

    for(count = 0;expression[count]!='\0';count++)
    {
        switch(expression[count])
        {
            case '+':
            case '-':
            case '*':
            case '/':
            case '^':
            case '%':
            case '$':
                operatorFunc(expression[count]);
                break;
            default:
                operandFunc(expression[count]);
        }
    }
    if(stackPtr != 0)
    {
        printf("Incomplete / Incorrect postfix expression given!\n");
    }
    else
    {
        printf("\n\nThe result = %d",solve(stack[stackPtr])+'0');
        printf("\n\n");
        return 0;
    }
}

void prefix(Btree root)
{
    Btree temp = root;
    if(temp)
    {
        printf("%c ",temp->item);
        prefix(temp->left);
        prefix(temp->right);        
    }
}

void infix(Btree root)
{
    Btree temp = root;
    if(temp != NULL)
    {
        infix(temp->left);
        printf("%c ",temp->item);       
        infix(temp->right);     
    }
}

void postfix(Btree root)
{
    Btree temp = root;
    if(temp)
    {
        postfix(temp->left);
        postfix(temp->right);       
        printf("%c ",temp->item);       
    }
}

void push(Btree root)
{
    stack[++stackPtr] = root;
}

Btree pop()
{
    return (stack[stackPtr--]);
}

void operandFunc(char var)
{
    Btree root = (Btree)malloc(sizeof(struct node));
    root->item= var;
    root->left= NULL;
    root->right= NULL;
    push(root);
}

void operatorFunc(char var)
{
    Btree root = (Btree)malloc(sizeof(struct node));
    root->item = var;
    root->right = pop();
    root->left = pop();
    push(root);
}

int solve(Btree root)
{
    Btree temp = root;
    char num1,num2;
    char operator;
    int result;
    if(temp)
    {
        Btree LEFTP = temp->left;
        Btree RIGHTP = temp->right; 

        if(LEFTP)
        {
            if(isOperand(LEFTP->item))
            {
                num1 = LEFTP->item;
            }   
            else
            {
                num1 = solve(LEFTP);
            }
        }

        if(RIGHTP)
        {
            if(isOperand(RIGHTP->item))
            {
                num2 = RIGHTP->item;
            }   
            else
            {
                num2 = solve(RIGHTP);
            }
        }

        operator = temp->item;
        printf("Test 1 = %c, num1 = %c, num2 = %c\n",operator,num1,num2);
        result = calculate(operator,num1-'0',num2-'0');
        printf("Test Result = %d\n",result);
        temp->item = (result+'0');
        printf("Root Item = %c and %d\n",temp->item,temp->item);
        return result;
    }

    return NULL;
}

int calculate(char operator,int op1,int op2)
{
    printf("Operator = %c , num1 = %d, num2 = %d\n",operator,op1,op2);
    switch(operator)
    {
        case '+':   return(op1+op2);
                    break;
        case '-':   return(op1-op2);
                    break;
        case '*':   return(op1*op2);
                    break;
        case '/':   return(op1/op2);
                    break;
        case '%':   return(op1%op2);
                    break;
        case '$':   return pow(op1,op2);
                    break;
        default:    printf("\n illegal operation.");
                    exit;
    }
}

int isOperand(char var)
{
    switch(var)
    {
        case '+': 
        case '-':
        case '*':
        case '/':
        case '$':
        case '%':
                    return 0;
        default:
                    return 1;
    }
}

我在转换字符并将其返回为整数时遇到问题。

更新1:我能够让它解决单位数字输入以接收多位数字结果。我仍在研究一种新的数据结构来计算多位数。下面是更新后的代码。

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
typedef struct node
{
    char item;
    struct node * left;
    struct node * right;
}*Btree;

Btree root;
void operandFunc(char);
void operatorFunc(char);
void push(Btree);
Btree pop();
void infix(Btree);
void postfix(Btree);
void prefix(Btree);
int solve(Btree);
int calculate(char,int,int);
int isOperand(char); 
char expression[25];
Btree stack[25];
int stackPtr = -1;

int main()
{
    int count = 0;
    printf("Please enter a postfix expression\n");
    while((expression[count++]=getchar())!='\n');
    expression[--count] = '\0';
    //puts(expression);

    for(count = 0;expression[count]!='\0';count++)
    {
        switch(expression[count])
        {
            case '+':
            case '-':
            case '*':
            case '/':
            case '^':
            case '%':
            case '$':
                operatorFunc(expression[count]);
                break;
            default:
                operandFunc(expression[count]);
        }
    }
    if(stackPtr != 0)
    {
        printf("Incomplete / Incorrect postfix expression given!\n");
    }
    else
    {
        printf("\n\nThe result = %d",solve(stack[stackPtr])-'0');
        printf("\n\n");
        return 0;
    }
}

void prefix(Btree root)
{
    Btree temp = root;
    if(temp)
    {
        printf("%c ",temp->item);
        prefix(temp->left);
        prefix(temp->right);        
    }
}

void infix(Btree root)
{
    Btree temp = root;
    if(temp != NULL)
    {
        infix(temp->left);
        printf("%c ",temp->item);       
        infix(temp->right);     
    }
}

void postfix(Btree root)
{
    Btree temp = root;
    if(temp)
    {
        postfix(temp->left);
        postfix(temp->right);       
        printf("%c ",temp->item);       
    }
}

void push(Btree root)
{
    stack[++stackPtr] = root;
}

Btree pop()
{
    return (stack[stackPtr--]);
}

void operandFunc(char var)
{
    Btree root = (Btree)malloc(sizeof(struct node));
    root->item= var;
    root->left= NULL;
    root->right= NULL;
    push(root);
}

void operatorFunc(char var)
{
    Btree root = (Btree)malloc(sizeof(struct node));
    root->item = var;
    root->right = pop();
    root->left = pop();
    push(root);
}

int solve(Btree root)
{
    Btree temp = root;
    char num1,num2;
    char operator;
    int result;
    if(temp)
    {
        Btree LEFTP = temp->left;
        Btree RIGHTP = temp->right; 

        if(LEFTP)
        {
            if(isOperand(LEFTP->item))
            {
                num1 = LEFTP->item;
            }   
            else
            {
                num1 = solve(LEFTP);
            }
        }

        if(RIGHTP)
        {
            if(isOperand(RIGHTP->item))
            {
                num2 = RIGHTP->item;
            }   
            else
            {
                num2 = solve(RIGHTP);
            }
        }

        operator = temp->item;
        printf("Test 1 = %c, num1 = %c, num2 = %c\n",operator,num1,num2);
        result = calculate(operator,num1-'0',num2-'0');
        printf("Test Result = %d\n",result);
        temp->item = (result+'0');
        printf("Root Item = %c and %d\n",temp->item,temp->item);
        return root->item;
    }

    return NULL;
}

int calculate(char operator,int op1,int op2)
{
    printf("Operator = %c , num1 = %d, num2 = %d\n",operator,op1,op2);
    switch(operator)
    {
        case '+':   return(op1+op2);
                    break;
        case '-':   return(op1-op2);
                    break;
        case '*':   return(op1*op2);
                    break;
        case '/':   return(op1/op2);
                    break;
        case '%':   return(op1%op2);
                    break;
        case '$':   return pow(op1,op2);
                    break;
        default:    printf("\n illegal operation.");
                    exit;
    }
}

int isOperand(char var)
{
    switch(var)
    {
        case '+': 
        case '-':
        case '*':
        case '/':
        case '$':
        case '%':
                    return 0;
        default:
                    return 1;
    }
}

Answer 1

在 operandFunc(expression[count]); 中，您仅处理一个字符。这意味着您无法使用 10 或 123 等多字符操作数。如果发生这种情况，请分别按下每个数字。因此，您的语言仅限于单位数字(好的；您的决定)。

在solve中，你说printf("Root Item = %c and %d\n",temp->item,temp->item);
。这里，第二个参数必须转换为 int:temp->item-'0'。每当您在 printf 格式中使用 %d 时都必须这样做。

您的其余代码看起来不错。也许在编译时设置更高的警告级别以发现更多错误？

编辑/添加:如何处理多位数字？

以下代码片段处理多位数字。您必须调整结构以区分字符和整数，并更改 operandFunc 来处理这些数字:

while((c=getchar())!='\n')
{
    switch(c)
    {
        case '+':
        case '-':
        case '*':
        case '/':
        case '^':
        case '%':
        case '$':
            operatorFunc(c);
            break;
        default:    // assume digit(s)
            num= c-'0';
            while ((c=getchar())!='\n' && isdigit(c)) num= num*10+c-'0';
            operandFunc(num);
            ungetc(c,stdin);
    }
}