C++实现高精度表达式计算器：分数运算与调度场算法详解

1. 项目概述：从“能算”到“算得准”的表达式求值

做算法练习，表达式计算是个绕不开的经典题目。很多朋友可能都写过那种只能处理整数、单层括号的“玩具级”计算器。但今天我们要聊的，是它的“终极版”：一个用C++实现的、能处理任意嵌套括号、支持小数运算，并且最关键的是——结果能以分数形式精确保留的表达式计算器。

为什么强调“分数保留”？这恰恰是区分“玩具”和“工具”的关键。在金融、科学计算甚至游戏开发中，浮点数的精度丢失是致命的。比如计算(1/3) * 3，用double直接算，结果可能是0.9999999999，而不是我们期望的1。我们的目标，就是让1/3 + 1/3 + 1/3的结果严格等于1，而不是一个近似值。

这个项目综合了数据结构（栈的应用）、算法设计（调度场算法）、以及数学（分数运算）等多个知识点。它不只是一个练习题，更是一个能体现工程思维和严谨性的小型项目。无论你是准备面试，还是想深入理解编译器前端处理表达式的原理，这个实现过程都会让你受益匪浅。

2. 核心思路与架构设计：为什么选择“中缀转后缀”？

实现表达式计算，主流思路有两种：递归下降解析和中缀表达式转后缀表达式（逆波兰表达式）。我们选择后者，原因很实际：逻辑清晰，易于实现括号嵌套和优先级处理，并且计算过程直观，非常适合用栈这种数据结构来操作。

2.1 整体流程拆解

我们的计算器将遵循一个经典的处理流水线：

原始中缀表达式 -> 词法分析（分割与负号处理） -> 中缀转后缀 -> 后缀表达式求值 -> 分数结果化简与输出

这个流程中，每一个环节都有其需要特别注意的“坑”。

2.2 核心数据结构选型：自己造轮子还是用STL？

在参考的博客中，作者使用了自实现的Array和ArrayStack。这对于理解底层原理很有帮助，但在实际项目和追求稳健的练习中，我强烈建议直接使用C++标准模板库（STL）。原因如下：

1. 可靠性：STL的std::vector,std::stack经过千锤百炼，几乎没有bug。
2. 便捷性：丰富的成员函数（如top(),pop()）能极大简化代码。
3. 性能：STL的实现通常经过高度优化。

因此，我们的实现将基于std::vector<std::string>和std::stack<std::string>。唯一需要自己实现的核心数据结构，是用来表示分数的Fraction类。

2.3 分数表示：工程精度的基石

这是本项目的灵魂。我们不能直接用double进行中间计算，否则精度丢失会污染最终结果。我们需要一个Fraction类来精确表示分数a/b。

class Fraction { private: long long numerator; // 分子 long long denominator; // 分母 void reduce(); // 核心：约分函数，用于化简分数 public: Fraction(long long n = 0, long long d = 1); // 重载算术运算符 Fraction operator+(const Fraction& other) const; Fraction operator-(const Fraction& other) const; Fraction operator*(const Fraction& other) const; Fraction operator/(const Fraction& other) const; // 从字符串构造，支持小数和整数 Fraction(const std::string& str); // 输出为字符串，可指定小数或分数形式 std::string toString(bool asDecimal = false) const; };

关键点解析：

• 数据类型：使用long long而非int，防止大数运算溢出。
• 约分（reduce）：每次运算后都必须调用。通过计算分子分母的最大公约数（GCD）来实现。这是保证分数始终处于最简形式的关键。
• 字符串构造：需要能解析"3.25"这样的字符串，将其转换为13/4。这涉及到小数转分数的算法。

注意：小数转分数时，例如0.333...，我们无法处理无限循环小数。我们的策略是，将输入的小数视为一个精确值，例如"0.33"会被处理为33/100。如果用户输入"0.3333333333"（10个3），我们就会得到3333333333/10000000000。这虽然不等于1/3，但它是用户输入的确切值。

3. 词法分析与负号处理：第一个拦路虎

词法分析的任务是把像“-1.5 + 2 * (3.14 - -4)”这样的字符串，切分成一个个有意义的单元（Token），例如：["-1.5", "+", "2", "*", "(", "3.14", "-", "-4", ")"]。这里最大的难点就是区分减号“-”和负号“-”。

3.1 基础分割策略

我们遍历表达式字符串，根据字符类型进行分割：

• 遇到数字（0-9）或小数点（.），持续读取，直到遇到非数字非小数点字符，将这段字符串作为一个数字Token。
• 遇到运算符（+ - * / ^）或括号（( )），直接作为一个Token。
• 忽略空格。

初步分割后，对于“-1+2”，我们会得到["-", "1", "+", "2"]。这里的第一个“-”是负号，而不是减号。

3.2 负号识别与转换规则

我们需要编写一个函数processNegativeSign，在基础分割后，对Token序列进行二次扫描，识别并转换负号。规则如下：

1. 表达式开头的负号：如果“-”是第一个Token，且下一个Token是数字或左括号，则它是负号。
   • 下一个是数字：将负号与数字合并。["-", "1.5"]->["-1.5"]。
   • 下一个是左括号：在它前面插入一个数字“0”。["-", "("]->["0", "-", "("]。这意味着“-(3+4)”被处理为“0-(3+4)”。
2. 括号后的负号：如果“-”的前一个Token是“(”，且后一个Token是数字，则它是负号，与后一个数字合并。["(", "-", "5"]->["(", "-5"]。
3. 运算符后的负号：如果“-”的前一个Token是运算符（+ - * / ^），且后一个Token是数字或左括号，则它是负号。处理方式同规则1。

实操心得： 处理负号时，务必在修改Token序列后，重新判断当前索引位置。因为合并操作会改变序列长度和后续元素的索引。我常用的技巧是：当识别出负号并合并后，不增加循环索引i，让下一轮循环继续处理当前的新位置，或者使用while循环配合条件判断，比简单的for循环更稳妥。

std::vector<std::string> tokenize(const std::string& expr) { std::vector<std::string> tokens; // ... 基础分割逻辑 ... processNegativeSign(tokens); // 调用负号处理函数 return tokens; }

4. 中缀转后缀：调度场算法精讲

这是算法的核心，经典方法称为调度场算法（Shunting-yard Algorithm）。我们需要两个栈：一个操作符栈opStack，一个用于输出后缀表达式的栈（或队列）outputQueue。这里我们用std::vector作为输出队列。

4.1 算法步骤与优先级定义

我们定义操作符的优先级（数值越小，优先级越高）：

• (: 优先级 0 (特殊处理，不入优先级比较)
• +,-: 优先级 1
• *,/: 优先级 2
• ^(乘方) : 优先级 3 (我们这里作为扩展支持)

算法流程（遍历中缀Token序列）：

1. 遇到操作数（数字）：直接加入输出队列。
2. 遇到左括号(：直接压入操作符栈。
3. 遇到右括号)：
   • 不断将操作符栈顶的运算符弹出，加入输出队列，直到遇到左括号。
   • 弹出左括号（丢弃，不加入输出队列）。
4. 遇到运算符（记为op）：
   • while(操作符栈非空且栈顶不是左括号且栈顶运算符的优先级大于等于op的优先级)：
     • 将栈顶运算符弹出，加入输出队列。
   • 将op压入操作符栈。
5. 遍历结束后：将操作符栈中剩余的所有运算符依次弹出，加入输出队列。

4.2 关键细节与C++实现

std::vector<std::string> infixToPostfix(const std::vector<std::string>& tokens) { std::vector<std::string> output; std::stack<std::string> opStack; std::unordered_map<std::string, int> priority = { {"+", 1}, {"-", 1}, {"*", 2}, {"/", 2}, {"^", 3} }; for (const auto& token : tokens) { if (isNumber(token)) { // 判断是否为数字（可能包含负号） output.push_back(token); } else if (token == "(") { opStack.push(token); } else if (token == ")") { while (!opStack.empty() && opStack.top() != "(") { output.push_back(opStack.top()); opStack.pop(); } opStack.pop(); // 弹出左括号 } else { // 是运算符 // 注意：左括号在栈中时，其“优先级”被视为最低 while (!opStack.empty() && opStack.top() != "(" && priority[opStack.top()] >= priority[token]) { output.push_back(opStack.top()); opStack.pop(); } opStack.push(token); } } // 处理栈中剩余操作符 while (!opStack.empty()) { output.push_back(opStack.top()); opStack.pop(); } return output; }

为什么是>=？在while条件priority[opStack.top()] >= priority[token]中，>=确保了相同优先级运算符的左结合性。对于+ - * /，我们习惯从左到右计算。例如a - b - c应理解为(a - b) - c。使用>=会让先出现的-先出栈，保证了正确的计算顺序。对于右结合的运算符（如乘方^），则需要特殊处理，将条件改为>。

重要提示：在判断isNumber(token)时，你的函数必须能识别像“-1.5”这样带负号的数字字符串。一个简单的办法是检查字符串首字符，如果是‘-’，则检查剩余部分是否构成一个合法数字。

5. 后缀表达式求值：分数栈的运算

得到后缀表达式（如["3", "4", "2", "*", "1", "5", "-", "/", "+"]对应3 + 4 * 2 / (1 - 5)）后，求值就非常直观了。

5.1 求值算法

1. 初始化一个操作数栈numStack（存储Fraction对象）。
2. 遍历后缀表达式：
   • 遇到操作数：将其构造为Fraction对象，压入numStack。
   • 遇到运算符：从numStack中弹出两个操作数（注意顺序！先弹出的是右操作数，后弹出的是左操作数）。根据运算符进行计算，将结果（一个新的Fraction对象）压回numStack。
3. 遍历结束后，numStack栈顶元素即为最终结果。

5.2 分数运算的实现细节

Fraction类的运算符重载是这里的核心。以加法为例：

Fraction Fraction::operator+(const Fraction& other) const { // 通分后相加 long long new_num = this->numerator * other.denominator + other.numerator * this->denominator; long long new_den = this->denominator * other.denominator; Fraction result(new_num, new_den); result.reduce(); // 切记约分！ return result; }

减法、乘法、除法同理，但需特别注意：

• 减法：注意操作数顺序，a - b在栈中是先弹出b，再弹出a，计算a - b。
• 除法：需要检查除数（第二个操作数）是否为0。
• 约分（reduce）：使用欧几里得算法求最大公约数（GCD）。

  void Fraction::reduce() { if (numerator == 0) { denominator = 1; return; } long long gcd = std::abs(std::gcd(numerator, denominator)); // C++17 起 std::gcd 在 <numeric> 中 // 如果编译器不支持C++17，需要自己实现gcd函数 // long long gcd = myGcd(std::abs(numerator), std::abs(denominator)); numerator /= gcd; denominator /= gcd; // 保证分母为正 if (denominator < 0) { numerator = -numerator; denominator = -denominator; } }

6. 从字符串到分数：处理小数输入

用户输入的是“0.75”这样的字符串，我们需要在构造Fraction时将其转换为分数。

Fraction::Fraction(const std::string& str) { size_t dotPos = str.find('.'); if (dotPos == std::string::npos) { // 整数 numerator = std::stoll(str); denominator = 1; } else { // 小数 std::string intPart = str.substr(0, dotPos); std::string fracPart = str.substr(dotPos + 1); // 例如 “0.75” -> intPart=“0”， fracPart=“75” long long intVal = std::stoll(intPart); // 计算小数部分对应的分数：75 / 10^2 long long fracNumerator = std::stoll(fracPart); long long fracDenominator = static_cast<long long>(std::pow(10, fracPart.length())); // 合并整数和小数部分 numerator = intVal * fracDenominator + (intVal >= 0 ? 1 : -1) * fracNumerator; denominator = fracDenominator; } reduce(); // 构造后立即化简 }

踩坑记录： 这里有个大坑：std::pow(10, n)返回的是double，直接转long long可能会有精度问题。例如std::pow(10, 2)理论上得到100，但浮点运算可能得到99.9999999，转换后就成了99。绝对不要这么用！正确做法是自己实现一个整数幂函数：

long long pow10(int n) { long long result = 1; for (int i = 0; i < n; ++i) result *= 10; return result; } // 使用时： long long fracDenominator = pow10(fracPart.length());

7. 常见问题与调试技巧实录

在实际编码和测试中，你几乎一定会遇到下面这些问题。

7.1 问题排查清单

7.2 调试与测试策略

1. 单元测试：不要一下子写完整个程序再测试。应该先独立测试Fraction类。

   // 简单的测试用例 Fraction a(“0.5”); // 1/2 Fraction b(“0.25”); // 1/4 Fraction c = a + b; // 应为 3/4 assert(c.toString() == “3/4”);

2. 分阶段验证：
   • 阶段一：验证tokenize(“-1 + 2.5 * (3 - -4)”)的输出是否正确。
   • 阶段二：将上一步的Tokens输入infixToPostfix，验证输出的后缀表达式是否与手动转换的一致。
   • 阶段三：将后缀表达式输入求值函数，验证结果。
3. 打印中间结果：在关键函数入口和出口，打印输入和输出。这是最朴素的调试方法，但极其有效。
4. 使用边界用例：
   • 空字符串或纯空格。
   • 单个数字或运算符。
   • 多层嵌套括号：((((1))))。
   • 连续的运算符和负号：1—2，1*-2。
   • 除零操作：1/0。

8. 功能扩展与性能考量

一个“终极版”计算器，可以考虑以下扩展方向，这能让你的项目在面试或作品中更加出彩。

8.1 支持更多运算符和函数

• 乘方^：已在优先级表中预留。注意它是右结合的，即2^3^2应计算为2^(3^2)=512，而非(2^3)^2=64。在中缀转后缀时，对于右结合运算符，当遇到优先级相等的栈顶运算符时，不应弹出，而是直接压入新运算符。
• 取模%：整数运算，需要判断操作数是否为整数。
• 数学函数：如sqrt(),sin(),log()等。这需要扩展Token类型，将函数名（如“sqrt"）也作为操作符处理，并在求值阶段调用对应的数学库函数。注意，函数参数可能是表达式，需要处理好括号。

8.2 错误处理与健壮性

• 输入验证：除了括号匹配，还应检查是否有连续的操作符（如”1++2“）、非法字符等。
• 表达式语法检查：可以在词法分析或转后缀过程中，检查操作数与运算符的数量关系是否合法。
• 自定义异常：定义ExpressionError,DivisionByZeroError等异常类，在出错时抛出清晰的异常信息，而不是让程序崩溃。

8.3 性能优化浅谈

对于教学项目，当前的实现已足够。但如果追求极致：

• 避免字符串拷贝：在Token处理时，可以使用string_view(C++17) 来避免不必要的字符串复制。
• 对象池：频繁创建和销毁Fraction对象可能产生开销。对于固定大小的表达式，可以预估所需分数对象数量，提前分配。
• 多精度整数：如果担心long long溢出，可以使用像GMP这样的多精度数学库，或者自己实现基于字符串的大整数运算。这将使你的计算器真正具备“任意精度”的能力。

实现这个“终极版”表达式计算器的过程，就像在搭建一个微型的解释器。它强迫你严谨地处理边界情况，深入地理解数据结构和算法，并认真对待数值精度问题。当你看到“1/3 + 1/3 + 1/3”稳稳地输出“1”而不是“0.999999”时，那种对程序完全掌控的满足感，是直接用eval类函数无法比拟的。代码的每个部分——从负号处理的繁琐判断，到分数约分时辗转相除的优雅，再到栈操作时“先弹出的是右操作数”的微妙细节——都凝结着对“精确”二字的追求。