用C++写一个中缀表达式转换抽象语法树代码

以下是用C++实现中缀表达式转换抽象语法树的代码：

#include <iostream>
#include <stack>
#include <vector>
#include <string>

// 定义节点类型
struct Node {
    char op; // 操作符
    int val; // 操作数
    Node* left; // 左子节点
    Node* right; // 右子节点
    Node(char c) : op(c), val(0), left(nullptr), right(nullptr) {}
    Node(int v) : op('\0'), val(v), left(nullptr), right(nullptr) {}
};

// 判断字符是否为操作符
bool isOperator(char c) {
    return (c == '+' || c == '-' || c == '*' || c == '/');
}

// 判断操作符优先级
int precedence(char op) {
    if (op == '+' || op == '-') {
        return 1;
    } else if (op == '*' || op == '/') {
        return 2;
    } else {
        return 0;
    }
}

// 将中缀表达式转换为后缀表达式
std::vector<std::string> infixToPostfix(const std::string& infix) {
    std::vector<std::string> postfix; // 存储后缀表达式
    std::stack<char> opStack; // 存储操作符
    int num = 0; // 记录当前操作数
    bool numFlag = false; // 标记是否正在读取操作数
    for (char c : infix) {
        if (c >= '0' && c <= '9') {
            num = num * 10 + c - '0';
            numFlag = true;
        } else {
            if (numFlag) {
                postfix.push_back(std::to_string(num));
                num = 0;
                numFlag = false;
            }
            if (c == '(') {
                opStack.push(c);
            } else if (c == ')') {
                while (!opStack.empty() && opStack.top() != '(') {
                    postfix.push_back(std::string(1, opStack.top()));
                    opStack.pop();
                }
                opStack.pop(); // 弹出左括号
            } else if (isOperator(c)) {
                while (!opStack.empty() && precedence(opStack.top()) >= precedence(c)) {
                    postfix.push_back(std::string(1, opStack.top()));
                    opStack.pop();
                }
                opStack.push(c);
            }
        }
    }
    if (numFlag) {
        postfix.push_back(std::to_string(num));
    }
    while (!opStack.empty()) {
        postfix.push_back(std::string(1, opStack.top()));
        opStack.pop();
    }
    return postfix;
}

// 从后缀表达式构造抽象语法树
Node* postfixToAST(const std::vector<std::string>& postfix) {
    std::stack<Node*> nodeStack;
    for (const std::string& s : postfix) {
        if (isOperator(s[0])) {
            Node* right = nodeStack.top();
            nodeStack.pop();
            Node* left = nodeStack.top();
            nodeStack.pop();
            Node* node = new Node(s[0]);
            node->left = left;
            node->right = right;
            nodeStack.push(node);
        } else {
            Node* node = new Node(std::stoi(s));
            nodeStack.push(node);
        }
    }
    return nodeStack.top();
}

// 打印抽象语法树
void printAST(Node* node, int depth = 0) {
    if (node == nullptr) {
        return;
    }
    for (int i = 0; i < depth; i++) {
        std::cout << "  ";
    }
    if (node->op == '\0') {
        std::cout << node->val << std::endl;
    } else {
        std::cout << node->op << std::endl;
    }
    printAST(node->left, depth + 1);
    printAST(node->right, depth + 1);
}

int main() {
    std::string infix = "3 + 4 * (2 - 1) / 5";
    std::vector<std::string> postfix = infixToPostfix(infix);
    Node* root = postfixToAST(postfix);
    printAST(root);
    return 0;
}

该程序将中缀表达式转换为后缀表达式，然后使用后缀表达式构造抽象语法树，并打印该树。例如，对于中缀表达式`3 + 4 * (2 - 1) / 5`，输出如下抽象语法树：

+
  3
  /
    *
    4
    -
      2
      1
    5

这个抽象语法树表示了该表达式的结构，可以用于计算表达式的值等操作。