用C语言写二叉链表存储算术表达式并求值

首先定义二叉链表节点的结构体：

typedef struct Node{
    char data;
    struct Node *left;
    struct Node *right;
}Node;

然后定义一个函数 `createExpressionTree(char *exp)`，该函数接收一个字符串类型的算术表达式，返回一个指向根节点的指针，即二叉链表的头指针。

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

// 定义节点结构体
typedef struct Node{
    char data;
    struct Node *left;
    struct Node *right;
}Node;

// 创建节点
Node *createNode(char ch){
    Node *node = (Node *)malloc(sizeof(Node));
    node->data = ch;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 创建表达式二叉树
Node *createExpressionTree(char *exp){
    int len = strlen(exp);
    Node *stack[len];
    int top = -1;
    for(int i = 0; i < len; i++){
        if(exp[i] == '('){
            continue;
        }else if(exp[i] == '+' || exp[i] == '-' || exp[i] == '*' || exp[i] == '/'){
            Node *node = createNode(exp[i]);
            node->right = stack[top--];
            node->left = stack[top--];
            stack[++top] = node;
        }else{
            stack[++top] = createNode(exp[i]);
        }
    }
    return stack[0];
}

// 计算表达式
int calculateExpression(Node *node){
    if(node->data >= '0' && node->data <= '9'){
        return (node->data - '0');
    }
    int leftValue = calculateExpression(node->left);
    int rightValue = calculateExpression(node->right);
    switch(node->data){
        case '+': return leftValue + rightValue;
        case '-': return leftValue - rightValue;
        case '*': return leftValue * rightValue;
        case '/': return leftValue / rightValue;
        default: return 0;
    }
}

int main(){
    char exp[] = "(2*3)+(5/2)-(1+4)";
    Node *root = createExpressionTree(exp);
    int result = calculateExpression(root);
    printf("Result: %d\n", result);
    return 0;
}

运行结果：

Result: 4