用 C++ 处理字符串形式的数学表达式时，不能像解释型语言那样直接把字符串交给求值函数，而需要把原始输入逐步转换成更容易计算的结构。逆波兰表达式就是一个很合适的中间表示：它把操作符放在操作数之后，括号完全消失，扫描一遍就能确定求值顺序。如果再把逆波兰序列构造成语法树，表达式的层级关系会更加直观，后续求值、变换和输出都建立在同一棵二叉树上。下面围绕字符串解析、后缀转换和语法树构建三个核心环节展开。

一、字符串到 Token 流的拆分

原始字符串 3 + 4 * 2 / ( 1 - 5 ) ^ 2 对程序来说只是一段文本，必须先识别出哪些子串是数字、哪些字符是运算符，哪些括号需要保留。这个步骤通常称为词法分析或 Token 化。C++ 里可以用 string 配合下标扫描完成。

扫描时，空格和制表符可以直接跳过；遇到数字或小数点就连续读取，直到遇到非数字字符，这样可以支持 123.45 这种多位小数。加、减、乘、除、幂、左括号和右括号各自作为一个单字符 Token。若碰到字母或其他非法字符，应当抛出异常，而不是静默忽略，否则错误表达式可能被算成另一个结果。

需要注意，这里实现的是二元运算符版本。对于负数，例如 -3，由于负号与减号位置重叠，简单扫描会把 - 识别为操作符。因此在这个基础上扩展负数字面量，需要判断 - 是否出现在表达式开头或左括号之后，如果是则把负号合并到数字 Token 中。这篇文章先聚焦核心链路的正确性，负数可以在这个 Token 化函数上继续修改。

vector<string> tokenize(const string& expr) {
    vector<string> tokens;
    int i = 0;
    while (i < expr.size()) {
        char c = expr[i];
        if (isspace(c)) {
            ++i;
            continue;
        }
        if (isdigit(c) || c == '.') {
            string num;
            while (i < expr.size() && (isdigit(expr[i]) || expr[i] == '.')) {
                num += expr[i];
                ++i;
            }
            tokens.push_back(num);
        } else if (c == '+' || c == '-' || c == '*' || c == '/' || c == '^' || c == '(' || c == ')') {
            tokens.push_back(string(1, c));
            ++i;
        } else {
            throw invalid_argument("输入包含无法识别的字符");
        }
    }
    return tokens;
}

二、调度场算法：把中缀变成逆波兰

有了 Token 序列之后，中缀表达式仍然包含括号，运算符优先级不能直接从左到右推导。例如 A + B * C 需要先算乘法，但扫描到 A 和 + 时并不确定 B * C 是否已完成。调度场算法的思路是：操作数直接输出到结果队列，操作符暂存到栈中，当栈顶操作符优先级更高或同优先级且当前操作符左结合时，先把栈顶弹出输出，再把当前操作符压栈。

括号的处理更直接：左括号无条件入栈，表示一个新的优先级边界；右括号则触发连续弹栈，直到遇到最近的左括号。这样任何嵌套括号都能在输出队列中自然展开。对于幂运算 ^，它是右结合操作符，也就是 2 ^ 3 ^ 2 应当理解为 2 ^ (3 ^ 2)，所以比较优先级时遇到相同优先级不弹栈，而加减乘除这些左结合操作符遇到同优先级要弹栈。

下面给出完整的转换函数。时间复杂度是 O(n)，因为每个 Token 最多入栈一次、出栈一次。空间复杂度受括号嵌套深度和操作符栈影响，最坏也为 O(n)。转换后得到的序列就是逆波兰表达式，例如 3 4 2 * 1 5 - 2 ^ / +，它完全没有括号，但计算顺序已经固定。

bool isOperator(const string& s) {
    return s == "+" || s == "-" || s == "*" || s == "/" || s == "^";
}
int precedence(const string& op) {
    if (op == "+" || op == "-") return 1;
    if (op == "*" || op == "/") return 2;
    if (op == "^") return 3;
    return 0;
}
vector<string> toRPN(const vector<string>& tokens) {
    vector<string> output;
    stack<string> ops;
    for (const string& token : tokens) {
        if (isdigit(token[0])) {
            output.push_back(token);
        } else if (isOperator(token)) {
            while (!ops.empty() && ops.top() != "(") {
                string top = ops.top();
                if (precedence(top) > precedence(token) ||
                    (precedence(top) == precedence(token) && token != "^")) {
                    output.push_back(top);
                    ops.pop();
                } else {
                    break;
                }
            }
            ops.push(token);
        } else if (token == "(") {
            ops.push(token);
        } else if (token == ")") {
            while (!ops.empty() && ops.top() != "(") {
                output.push_back(ops.top());
                ops.pop();
            }
            if (ops.empty()) {
                throw invalid_argument("括号不匹配");
            }
            ops.pop();
        }
    }
    while (!ops.empty()) {
        if (ops.top() == "(") {
            throw invalid_argument("括号不匹配");
        }
        output.push_back(ops.top());
        ops.pop();
    }
    return output;
}

三、从逆波兰序列构建语法树

逆波兰序列虽然适合机器直接计算，但如果要理解表达式的结构，线性序列还不够直观。语法树可以明确展示谁是谁的子表达式。构建语法树时，节点分成两类：数字节点作为叶子，操作符节点作为内部节点。每个操作符节点有两个孩子，左孩子对应左操作数，右孩子对应右操作数。

由于逆波兰表达式的顺序正好是后序遍历，所以构建过程可以用栈完成。扫描到数字就创建一个叶子节点并压栈；扫描到操作符时，说明它的左右子表达式已经按顺序在栈顶，于是先弹出右孩子，再弹出左孩子，把这两个节点挂在操作符节点下面，然后把这个新子树压回栈。先弹右再弹左是不能颠倒的，否则减法和除法这类不可交换的操作会得到错误结构。

当所有 Token 处理完，栈中应该恰好剩下一个节点，它就是整棵语法树的根。如果栈空或剩余多个节点，说明逆波兰序列不合法。下面代码中 Node 使用 string value 保存原始内容，左右指针初始化为 nullptr，后续扩展求值和打印都围绕这个结构。

struct Node {
    string value;
    Node* left;
    Node* right;
    Node(string v) : value(v), left(nullptr), right(nullptr) {}
};
Node* buildTree(const vector<string>& rpn) {
    stack<Node*> st;
    for (const string& token : rpn) {
        Node* node = new Node(token);
        if (isOperator(token)) {
            if (st.size() < 2) {
                throw invalid_argument("逆波兰表达式无效");
            }
            node->right = st.top();
            st.pop();
            node->left = st.top();
            st.pop();
        }
        st.push(node);
    }
    if (st.size() != 1) {
        throw invalid_argument("逆波兰表达式无效");
    }
    return st.top();
}

四、递归求值、遍历与边界处理

语法树建立之后，求值就是对树做一次后序遍历。叶子节点把字符串转换成浮点数；内部节点先递归计算左子树和右子树，再根据操作符执行加法、减法、乘法、除法或幂运算。这个递归过程天然符合表达式优先级，因为优先级已经在构建树时固化到层级里了。

实际使用中不能忽略错误。除数为零、括号不匹配、非法字符、逆波兰序列缺少操作数等情况都应该尽早抛出异常。输入 ()、1 +、/ 2 这类错误写法不能被允许悄悄输出中间结果。上面的 toRPN 和 buildTree 都带有基础校验，求值阶段增加的除零检查避免程序崩溃。

需要特别关注内存释放。手动 new 出来的 Node 不会被自动回收，如果程序频繁处理多个表达式，会造成内存泄漏。可以写一个 deleteTree 函数，后序释放左右子树再删除当前节点。下面同时给出求值和主函数示例，完整展示从字符串到最终数值的调用关系。

double evaluate(Node* root) {
    if (root->left == nullptr && root->right == nullptr) {
        return stod(root->value);
    }
    double leftValue = evaluate(root->left);
    double rightValue = evaluate(root->right);
    string op = root->value;
    if (op == "+") return leftValue + rightValue;
    if (op == "-") return leftValue - rightValue;
    if (op == "*") return leftValue * rightValue;
    if (op == "/") {
        if (rightValue == 0) throw invalid_argument("除数为零");
        return leftValue / rightValue;
    }
    if (op == "^") return pow(leftValue, rightValue);
    throw invalid_argument("未知运算符");
}
void deleteTree(Node* root) {
    if (root == nullptr) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

int main() {
    string expr = "3 + 4 * 2 / ( 1 - 5 ) ^ 2";
    vector<string> tokens = tokenize(expr);
    vector<string> rpn = toRPN(tokens);
    cout << "RPN:";
    for (const string& t : rpn) cout << " " << t;
    cout << endl;
    Node* tree = buildTree(rpn);
    cout << "Result: " << evaluate(tree) << endl;
    deleteTree(tree);
    return 0;
}

逆波兰表达式和语法树的组合，把一个看似复杂的字符串求值问题拆成了三个独立且可测试的阶段。Token 化负责把字符变成符号，调度场算法负责消除括号和固化优先级，建树则把线性序列还原为结构化表示。这种分层处理方式不仅适合写计算器，也能迁移到表达式引擎、规则系统和编译器前端等场景中。掌握这套流程之后，再扩展函数调用、变量绑定或逻辑运算，都可以在现有节点类型和遍历框架上继续演进。