用c语言实现基于二叉树的表达式求值算法

实现基于二叉树的表达式求值算法，需要先将表达式转化为二叉树，再对二叉树进行遍历求值。以下是一个简单的实现示例：

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

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

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

// 将表达式转化为二叉树
Node* buildTree(char* expr, int start, int end) {
    if (start > end) {
        return NULL;
    }

    Node* node = createNode(expr[start]);

    if (start == end) {
        return node;
    }

    int opIndex = -1;
    int bracketCount = 0;

    // 从左往右扫描表达式，找到优先级最低的运算符
    for (int i = start; i <= end; i++) {
        if (expr[i] == '(') {
            bracketCount++;
        } else if (expr[i] == ')') {
            bracketCount--;
        } else if (bracketCount == 0 && (expr[i] == '+' || expr[i] == '-'
                || expr[i] == '*' || expr[i] == '/')) {
            opIndex = i;
            break;
        }
    }

    if (opIndex == -1) {
        return node;
    }

    // 递归构建左右子树
    node->left = buildTree(expr, start + 1, opIndex - 1);
    node->right = buildTree(expr, opIndex + 1, end);

    return node;
}

// 计算二叉树节点的值
int calculateNode(Node* node) {
    if (isdigit(node->data)) {
        return node->data - '0';
    }

    int leftValue = calculateNode(node->left);
    int rightValue = calculateNode(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 calculate(char* expr) {
    Node* root = buildTree(expr, 0, strlen(expr) - 1);
    return calculateNode(root);
}

int main() {
    char expr[] = "3+(4*5)-(6/2)";
    int result = calculate(expr);
    printf("Result: %d\n", result);
    return 0;
}

在以上代码中，`buildTree` 函数接收一个表达式字符串和起始和终止索引，返回一个二叉树节点。函数会在表达式中找到优先级最低的运算符，然后递归构建左右子树。`calculateNode` 函数接收一个二叉树节点，返回其值。函数会根据节点数据判断是数字还是运算符，如果是数字则直接返回，否则递归计算左右子树的值并返回计算结果。`calculate` 函数接收一个表达式字符串，调用 `buildTree` 函数构建二叉树，并调用 `calculateNode` 函数计算表达式的值。最后在 `main` 函数中调用 `calculate` 函数并输出结果。