面试题：C++ 类运算符重载之自定义流运算符重载及链式调用

设计思路：
- 可以使用二叉表达式树来存储表达式。每个节点存储一个操作数或运算符，操作数节点没有子节点，运算符节点有左右子节点分别代表左右操作数。
- 为了处理运算符优先级和括号，在构建表达式树时，使用类似编译器的词法分析和语法分析过程。例如，利用栈来辅助构建表达式树，先将输入的表达式进行词法分析，分解为一个个的词法单元（操作数、运算符、括号），然后根据运算符优先级和括号规则构建表达式树。
关键成员函数：
- 构造函数：可以有默认构造函数初始化空的表达式树，也可以有带参数的构造函数用于初始化单个操作数节点。
- 辅助构建树的函数：如根据词法单元构建表达式树的函数，该函数内部可能会使用栈来处理运算符优先级和括号。
- 求值函数：用于计算表达式树的值。
运算符重载函数实现框架：

#include <iostream>
#include <sstream>
#include <stack>
#include <string>

// 表达式树节点类
class TreeNode {
public:
    std::string val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(const std::string& v) : val(v), left(nullptr), right(nullptr) {}
};

class Expression {
private:
    TreeNode* root;

    // 辅助函数：用于构建表达式树
    TreeNode* buildTree(const std::string& expression) {
        std::stack<TreeNode*> numStack;
        std::stack<char> opStack;
        std::istringstream iss(expression);
        std::string token;
        while (iss >> token) {
            if (isdigit(token[0])) {
                numStack.push(new TreeNode(token));
            } else if (token == "(") {
                opStack.push('(');
            } else if (token == ")") {
                while (opStack.top() != '(') {
                    TreeNode* right = numStack.top(); numStack.pop();
                    TreeNode* left = numStack.top(); numStack.pop();
                    char op = opStack.top(); opStack.pop();
                    TreeNode* newNode = new TreeNode(std::string(1, op));
                    newNode->left = left;
                    newNode->right = right;
                    numStack.push(newNode);
                }
                opStack.pop(); // 弹出 '('
            } else {
                while (!opStack.empty() && precedence(opStack.top()) >= precedence(token[0])) {
                    TreeNode* right = numStack.top(); numStack.pop();
                    TreeNode* left = numStack.top(); numStack.pop();
                    char op = opStack.top(); opStack.pop();
                    TreeNode* newNode = new TreeNode(std::string(1, op));
                    newNode->left = left;
                    newNode->right = right;
                    numStack.push(newNode);
                }
                opStack.push(token[0]);
            }
        }
        while (!opStack.empty()) {
            TreeNode* right = numStack.top(); numStack.pop();
            TreeNode* left = numStack.top(); numStack.pop();
            char op = opStack.top(); opStack.pop();
            TreeNode* newNode = new TreeNode(std::string(1, op));
            newNode->left = left;
            newNode->right = right;
            numStack.push(newNode);
        }
        return numStack.top();
    }

    // 辅助函数：获取运算符优先级
    int precedence(char op) {
        if (op == '+' || op == '-') return 1;
        if (op == '*' || op == '/') return 2;
        return 0;
    }

    // 辅助函数：中序遍历输出表达式
    void inorderTraversal(TreeNode* node, std::ostream& os) const {
        if (node) {
            if (node->left) {
                os << '(';
                inorderTraversal(node->left, os);
            }
            os << node->val;
            if (node->right) {
                inorderTraversal(node->right, os);
                os << ')';
            }
        }
    }

public:
    Expression() : root(nullptr) {}
    Expression(const std::string& value) {
        root = buildTree(value);
    }
    ~Expression() {
        // 释放表达式树内存
        if (root) {
            std::stack<TreeNode*> stack;
            stack.push(root);
            while (!stack.empty()) {
                TreeNode* node = stack.top(); stack.pop();
                if (node->left) stack.push(node->left);
                if (node->right) stack.push(node->right);
                delete node;
            }
        }
    }

    // 重载 << 运算符
    friend std::ostream& operator<<(std::ostream& os, const Expression& e) {
        e.inorderTraversal(e.root, os);
        return os;
    }

    // 重载 + 运算符
    Expression operator+(const Expression& other) {
        std::string newExpression = "(" + std::string(*this) + " + " + std::string(other) + ")";
        return Expression(newExpression);
    }

    // 重载 * 运算符
    Expression operator*(const Expression& other) {
        std::string newExpression = "(" + std::string(*this) + " * " + std::string(other) + ")";
        return Expression(newExpression);
    }
};

星途面试题库

面试题：C++ 类运算符重载之自定义流运算符重载及链式调用

知识考点

面试题答案