中序表达式建立表达式树 ，并计算出结果，c++

可以通过递归地建立表达式树，并在遍历树的过程中计算出结果。

首先定义一个表达式树节点的结构体：

struct ExpressionTreeNode {
    char value; // 节点存储的值，可以是操作符或操作数
    ExpressionTreeNode* left; // 左子节点
    ExpressionTreeNode* right; // 右子节点
    ExpressionTreeNode(char v) : value(v), left(nullptr), right(nullptr) {}
};

然后可以定义一个递归函数，用于建立表达式树：

ExpressionTreeNode* buildExpressionTree(string& s, int start, int end) {
    if (start > end) {
        return nullptr;
    }
    // 查找优先级最低的操作符
    int lowestPriority = INT_MAX;
    int lowestIndex = -1;
    int priority = 0;
    for (int i = start; i <= end; i++) {
        if (s[i] == '(') {
            priority += 3; // 括号的优先级最高
        } else if (s[i] == ')') {
            priority -= 3;
        } else if (s[i] == '+' || s[i] == '-') {
            if (priority <= lowestPriority) {
                lowestPriority = priority;
                lowestIndex = i;
            }
        } else if (s[i] == '*' || s[i] == '/') {
            if (priority + 1 <= lowestPriority) {
                lowestPriority = priority + 1; // 乘除的优先级比加减高
                lowestIndex = i;
            }
        }
    }
    if (lowestIndex == -1) { // 未找到操作符，说明当前表达式是一个数字
        return new ExpressionTreeNode(s[start]);
    }
    auto node = new ExpressionTreeNode(s[lowestIndex]);
    node->left = buildExpressionTree(s, start, lowestIndex - 1); // 递归建立左子树
    node->right = buildExpressionTree(s, lowestIndex + 1, end); // 递归建立右子树
    return node;
}

该函数接收一个字符串 `s`、一个起始位置 `start` 和一个结束位置 `end`，返回建立的表达式树的根节点。它首先查找优先级最低的操作符，并以此为根节点，递归地建立左子树和右子树。

最后，可以定义一个计算表达式树的函数：

int evaluateExpressionTree(ExpressionTreeNode* root) {
    if (!root->left && !root->right) { // 叶子节点，即数字
        return root->value - '0';
    }
    int leftValue = evaluateExpressionTree(root->left);
    int rightValue = evaluateExpressionTree(root->right);
    switch (root->value) {
        case '+':
            return leftValue + rightValue;
        case '-':
            return leftValue - rightValue;
        case '*':
            return leftValue * rightValue;
        case '/':
            return leftValue / rightValue;
        default:
            return 0;
    }
}

该函数接收一个表达式树的根节点 `root`，返回计算的结果。它递归地计算左子树和右子树的结果，并根据根节点存储的操作符计算出最终结果。

完整代码如下：

#include <iostream>
#include <string>
#include <climits>
using namespace std;

struct ExpressionTreeNode {
    char value;
    ExpressionTreeNode* left;
    ExpressionTreeNode* right;
    ExpressionTreeNode(char v) : value(v), left(nullptr), right(nullptr) {}
};

ExpressionTreeNode* buildExpressionTree(string& s, int start, int end) {
    if (start > end) {
        return nullptr;
    }
    int lowestPriority = INT_MAX;
    int lowestIndex = -1;
    int priority = 0;
    for (int i = start; i <= end; i++) {
        if (s[i] == '(') {
            priority += 3;
        } else if (s[i] == ')') {
            priority -= 3;
        } else if (s[i] == '+' || s[i] == '-') {
            if (priority <= lowestPriority) {
                lowestPriority = priority;
                lowestIndex = i;
            }
        } else if (s[i] == '*' || s[i] == '/') {
            if (priority + 1 <= lowestPriority) {
                lowestPriority = priority + 1;
                lowestIndex = i;
            }
        }
    }
    if (lowestIndex == -1) {
        return new ExpressionTreeNode(s[start]);
    }
    auto node = new ExpressionTreeNode(s[lowestIndex]);
    node->left = buildExpressionTree(s, start, lowestIndex - 1);
    node->right = buildExpressionTree(s, lowestIndex + 1, end);
    return node;
}

int evaluateExpressionTree(ExpressionTreeNode* root) {
    if (!root->left && !root->right) {
        return root->value - '0';
    }
    int leftValue = evaluateExpressionTree(root->left);
    int rightValue = evaluateExpressionTree(root->right);
    switch (root->value) {
        case '+':
            return leftValue + rightValue;
        case '-':
            return leftValue - rightValue;
        case '*':
            return leftValue * rightValue;
        case '/':
            return leftValue / rightValue;
        default:
            return 0;
    }
}

int main() {
    string s = "5+3*6-4/2";
    auto root = buildExpressionTree(s, 0, s.length() - 1);
    cout << evaluateExpressionTree(root) << endl; // 输出 23
    return 0;
}