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。原因如下可靠性STL的std::vector,std::stack经过千锤百炼几乎没有bug。便捷性丰富的成员函数如top(),pop()能极大简化代码。性能STL的实现通常经过高度优化。因此我们的实现将基于std::vectorstd::string和std::stackstd::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.333333333310个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。忽略空格。初步分割后对于“-12”我们会得到[-, 1, , 2]。这里的第一个“-”是负号而不是减号。3.2 负号识别与转换规则我们需要编写一个函数processNegativeSign在基础分割后对Token序列进行二次扫描识别并转换负号。规则如下表达式开头的负号如果“-”是第一个Token且下一个Token是数字或左括号则它是负号。下一个是数字将负号与数字合并。[-, 1.5]-[-1.5]。下一个是左括号在它前面插入一个数字“0”。[-, (]-[0, -, (]。这意味着“-(34)”被处理为“0-(34)”。括号后的负号如果“-”的前一个Token是“(”且后一个Token是数字则它是负号与后一个数字合并。[(, -, 5]-[(, -5]。运算符后的负号如果“-”的前一个Token是运算符 - * / ^且后一个Token是数字或左括号则它是负号。处理方式同规则1。实操心得 处理负号时务必在修改Token序列后重新判断当前索引位置。因为合并操作会改变序列长度和后续元素的索引。我常用的技巧是当识别出负号并合并后不增加循环索引i让下一轮循环继续处理当前的新位置或者使用while循环配合条件判断比简单的for循环更稳妥。std::vectorstd::string tokenize(const std::string expr) { std::vectorstd::string tokens; // ... 基础分割逻辑 ... processNegativeSign(tokens); // 调用负号处理函数 return tokens; }4. 中缀转后缀调度场算法精讲这是算法的核心经典方法称为调度场算法Shunting-yard Algorithm。我们需要两个栈一个操作符栈opStack一个用于输出后缀表达式的栈或队列outputQueue。这里我们用std::vector作为输出队列。4.1 算法步骤与优先级定义我们定义操作符的优先级数值越小优先级越高(: 优先级 0 (特殊处理不入优先级比较),-: 优先级 1*,/: 优先级 2^(乘方) : 优先级 3 (我们这里作为扩展支持)算法流程遍历中缀Token序列遇到操作数数字直接加入输出队列。遇到左括号(直接压入操作符栈。遇到右括号)不断将操作符栈顶的运算符弹出加入输出队列直到遇到左括号。弹出左括号丢弃不加入输出队列。遇到运算符记为opwhile(操作符栈非空且栈顶不是左括号且栈顶运算符的优先级大于等于op的优先级)将栈顶运算符弹出加入输出队列。将op压入操作符栈。遍历结束后将操作符栈中剩余的所有运算符依次弹出加入输出队列。4.2 关键细节与C实现std::vectorstd::string infixToPostfix(const std::vectorstd::string tokens) { std::vectorstd::string output; std::stackstd::string opStack; std::unordered_mapstd::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 求值算法初始化一个操作数栈numStack存储Fraction对象。遍历后缀表达式遇到操作数将其构造为Fraction对象压入numStack。遇到运算符从numStack中弹出两个操作数注意顺序先弹出的是右操作数后弹出的是左操作数。根据运算符进行计算将结果一个新的Fraction对象压回numStack。遍历结束后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)); // C17 起 std::gcd 在 numeric 中 // 如果编译器不支持C17需要自己实现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_castlong 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 问题排查清单问题现象可能原因排查方法程序崩溃段错误1. 栈空时执行top()或pop()。2. 访问vector越界。1. 在所有stack.top()和stack.pop()前检查stack.empty()。2. 使用vector.at(i)替代[i]它会进行边界检查。计算结果完全错误1. 负号处理逻辑有误导致运算符和操作数对应关系错乱。2. 中缀转后缀时运算符优先级或结合性弄错。3. 分数运算时加减法未通分或约分函数有bug。1. 打印出词法分析后的Token序列检查负号是否正确转换。2. 打印中缀转后缀后的表达式手动演算对比。3. 为Fraction类添加调试输出查看每一步运算后的分数值。小数转换结果不对1. 小数转分数时pow函数精度丢失。2. 字符串转整数时未处理可能的异常如非法字符。1. 使用自定义的pow10函数。2. 使用try-catch捕获std::invalid_argument等异常。对于复杂嵌套表达式结果错误括号匹配检查遗漏或转后缀时括号处理逻辑有误。在词法分析后增加一个独立的括号匹配检查函数。遍历Tokens遇(则栈压入遇)则栈弹出最后栈应为空。输出分数未化简reduce()函数未被调用或GCD计算有误。检查所有构造Fraction和进行算术运算的地方是否都调用了reduce()。单步调试reduce()函数。7.2 调试与测试策略单元测试不要一下子写完整个程序再测试。应该先独立测试Fraction类。// 简单的测试用例 Fraction a(“0.5”); // 1/2 Fraction b(“0.25”); // 1/4 Fraction c a b; // 应为 3/4 assert(c.toString() “3/4”);分阶段验证阶段一验证tokenize(“-1 2.5 * (3 - -4)”)的输出是否正确。阶段二将上一步的Tokens输入infixToPostfix验证输出的后缀表达式是否与手动转换的一致。阶段三将后缀表达式输入求值函数验证结果。打印中间结果在关键函数入口和出口打印输入和输出。这是最朴素的调试方法但极其有效。使用边界用例空字符串或纯空格。单个数字或运算符。多层嵌套括号((((1))))。连续的运算符和负号1—21*-2。除零操作1/0。8. 功能扩展与性能考量一个“终极版”计算器可以考虑以下扩展方向这能让你的项目在面试或作品中更加出彩。8.1 支持更多运算符和函数乘方^已在优先级表中预留。注意它是右结合的即2^3^2应计算为2^(3^2)512而非(2^3)^264。在中缀转后缀时对于右结合运算符当遇到优先级相等的栈顶运算符时不应弹出而是直接压入新运算符。取模%整数运算需要判断操作数是否为整数。数学函数如sqrt(),sin(),log()等。这需要扩展Token类型将函数名如“sqrt也作为操作符处理并在求值阶段调用对应的数学库函数。注意函数参数可能是表达式需要处理好括号。8.2 错误处理与健壮性输入验证除了括号匹配还应检查是否有连续的操作符如”12“、非法字符等。表达式语法检查可以在词法分析或转后缀过程中检查操作数与运算符的数量关系是否合法。自定义异常定义ExpressionError,DivisionByZeroError等异常类在出错时抛出清晰的异常信息而不是让程序崩溃。8.3 性能优化浅谈对于教学项目当前的实现已足够。但如果追求极致避免字符串拷贝在Token处理时可以使用string_view(C17) 来避免不必要的字符串复制。对象池频繁创建和销毁Fraction对象可能产生开销。对于固定大小的表达式可以预估所需分数对象数量提前分配。多精度整数如果担心long long溢出可以使用像GMP这样的多精度数学库或者自己实现基于字符串的大整数运算。这将使你的计算器真正具备“任意精度”的能力。实现这个“终极版”表达式计算器的过程就像在搭建一个微型的解释器。它强迫你严谨地处理边界情况深入地理解数据结构和算法并认真对待数值精度问题。当你看到“1/3 1/3 1/3”稳稳地输出“1”而不是“0.999999”时那种对程序完全掌控的满足感是直接用eval类函数无法比拟的。代码的每个部分——从负号处理的繁琐判断到分数约分时辗转相除的优雅再到栈操作时“先弹出的是右操作数”的微妙细节——都凝结着对“精确”二字的追求。