手把手教你用C语言实现一个简易计算器：从算符优先分析到表达式求值

从零构建C语言计算器算符优先算法的工程实践当我们第一次接触编程时总会梦想着能亲手打造一个属于自己的计算器。这个看似简单的工具实际上蕴含着编译原理中最精妙的思想——如何让计算机理解并执行人类书写数学表达式的规则。本文将带你用C语言实现一个能处理加减乘除和括号的计算器核心是算符优先分析算法这是编译器中表达式处理的经典方法。1. 理解算符优先分析的基本原理算符优先分析属于自底向上的语法分析方法特别适合处理表达式求值。它的核心思想是通过比较运算符之间的优先级来决定运算顺序就像人类心算时会自然遵循先乘除后加减的规则。关键概念解析FirstVT集合非终结符能推导出的第一个终结符集合LastVT集合非终结符能推导出的最后一个终结符集合优先关系表定义运算符之间的优先级关系, , 让我们用一个简单文法来说明E → E T | E - T | T T → T * F | T / F | F F → (E) | i这个文法中E代表表达式T代表项F代表因子i代表标识符这里可以理解为数字。2. 构建FirstVT和LastVT集合实现算符优先分析的第一步是计算每个非终结符的FirstVT和LastVT集合。这些集合将帮助我们建立运算符之间的优先级关系。2.1 FirstVT集合生成算法void CreatFirstVT() { // 初始化所有FirstVT集合为空 for (int i 0; i lenNTerStr; i) { firstVT[i][0] \0; } // 应用规则直到集合不再变化 while (flagFirstVT) { flagFirstVT 0; for (int i 0; i lenGramStr; i) { char left gramOldSet[i].formula[0]; int leftPos FindPosition(left, nterSymbol); // 规则1若有产生式 A→a... 或 A→Ba...则a∈FirstVT(A) if (IsTerOrNon(gramOldSet[i].formula[3]) 2) { AddElement(firstVT[leftPos], gramOldSet[i].formula[3]); } // 规则2若有产生式 A→B...则FirstVT(B) ⊆ FirstVT(A) if (IsTerOrNon(gramOldSet[i].formula[3]) 1) { int rightPos FindPosition(gramOldSet[i].formula[3], nterSymbol); MergeStr(firstVT[leftPos], firstVT[rightPos]); // 如果B后跟终结符也加入FirstVT(A) if (IsTerOrNon(gramOldSet[i].formula[4]) 2) { AddElement(firstVT[leftPos], gramOldSet[i].formula[4]); } } } } }2.2 LastVT集合生成算法LastVT的生成与FirstVT类似只是从产生式的右侧开始扫描void CreatLastVT() { for (int i 0; i lenNTerStr; i) { lastVT[i][0] \0; } while (flagLastVT) { flagLastVT 0; for (int i 0; i lenGramStr; i) { int length QueryLen(gramOldSet[i].formula); char left gramOldSet[i].formula[0]; int leftPos FindPosition(left, nterSymbol); // 规则1若有产生式 A→...a 或 A→...aB则a∈LastVT(A) if (IsTerOrNon(gramOldSet[i].formula[length-1]) 2) { AddElement(lastVT[leftPos], gramOldSet[i].formula[length-1]); } // 规则2若有产生式 A→...B则LastVT(B) ⊆ LastVT(A) if (IsTerOrNon(gramOldSet[i].formula[length-1]) 1) { int rightPos FindPosition(gramOldSet[i].formula[length-1], nterSymbol); MergeStr(lastVT[leftPos], lastVT[rightPos]); // 如果B前有终结符也加入LastVT(A) if (IsTerOrNon(gramOldSet[i].formula[length-2]) 2) { AddElement(lastVT[leftPos], gramOldSet[i].formula[length-2]); } } } } }3. 构造算符优先关系表有了FirstVT和LastVT集合我们就可以构建优先关系表了。这个表定义了任意两个运算符之间的优先级关系。优先关系规则a b 当且仅当存在产生式...ab...或...aBb...a b 当且仅当存在产生式...aB...且b∈FirstVT(B)a b 当且仅当存在产生式...Bb...且a∈LastVT(B)实现代码int CreatTable() { // 初始化表格 for (int i 0; i N; i) { for (int j 0; j N; j) { table[i][j] ; } } // 添加#的特殊关系 terSymbol[lenTerStr] #; terSymbol[lenTerStr] \0; // # FirstVT(E) int temp 0; while (firstVT[0][temp] ! \0) { int firstPos FindPosition(firstVT[0][temp], terSymbol); int hashPos FindPosition(#, terSymbol); table[hashPos][firstPos] ; temp; } // LastVT(E) # temp 0; while (lastVT[0][temp] ! \0) { int lastPos FindPosition(lastVT[0][temp], terSymbol); int hashPos FindPosition(#, terSymbol); table[lastPos][hashPos] ; temp; } // 处理其他运算符关系 for (int i 0; i lenGramStr; i) { int index 3; while (gramOldSet[i].formula[index] ! \0) { if (IsTerOrNon(gramOldSet[i].formula[index]) 2) { // 规则1a b if b∈FirstVT(B) and A→...aB... if (IsTerOrNon(gramOldSet[i].formula[index-1]) 1) { int nonTerPos FindPosition(gramOldSet[i].formula[index-1], nterSymbol); int firstIndex 0; while (firstVT[nonTerPos][firstIndex] ! \0) { int aPos FindPosition(gramOldSet[i].formula[index], terSymbol); int bPos FindPosition(firstVT[nonTerPos][firstIndex], terSymbol); table[aPos][bPos] ; firstIndex; } } // 规则2a b if a∈LastVT(B) and A→...Bb... if (IsTerOrNon(gramOldSet[i].formula[index1]) 1) { int nonTerPos FindPosition(gramOldSet[i].formula[index1], nterSymbol); int lastIndex 0; while (lastVT[nonTerPos][lastIndex] ! \0) { int aPos FindPosition(gramOldSet[i].formula[index], terSymbol); int bPos FindPosition(lastVT[nonTerPos][lastIndex], terSymbol); table[bPos][aPos] ; lastIndex; } } // 规则3a b if A→...ab... or A→...aBb... if (IsTerOrNon(gramOldSet[i].formula[index1]) 2) { int aPos FindPosition(gramOldSet[i].formula[index], terSymbol); int bPos FindPosition(gramOldSet[i].formula[index1], terSymbol); table[aPos][bPos] ; } } index; } } // 打印优先关系表 printf(\n优先关系表:\n); PrintTable(); return 0; }4. 实现算符优先分析算法有了优先关系表我们就可以实现核心的分析算法了。这个算法使用栈结构来保存运算符和操作数根据优先关系决定何时进行归约。算法步骤初始化栈压入#读取输入串的下一个符号a查找栈顶第一个终结符b比较b和a的优先级如果b a或b a移进a如果b a归约重复直到栈中只剩#和结果关键实现代码void Control(char str[]) { SqStack* stack (SqStack*)malloc(sizeof(SqStack)); InitStack(stack); Push(stack, #); int k 0; // 栈深度 int values[100]; // 值栈用于实际计算 values[k] 0; int pointer 0; // 输入字符串指针 int flag 1; // 循环控制 while (flag) { char topTerm GetTopTerminal(stack, k); int topPos FindPosition(Alt(topTerm), terSymbol); int inputPos FindPosition(Alt(str[pointer]), terSymbol); if (table[topPos][inputPos] ) { printf(错误无效的运算符优先级关系\n); break; } if (table[topPos][inputPos] || table[topPos][inputPos] ) { // 移进 Push(stack, str[pointer]); if (isdigit(str[pointer])) { values[k] str[pointer] - 0; } else { values[k] str[pointer]; } if (topTerm # str[pointer] #) { // 分析成功 printf(\n表达式结果: %d\n, values[1]); flag 0; } pointer; } else if (table[topPos][inputPos] ) { // 归约 int i k; do { char temp GetTerminalAt(stack, i); int tempPos FindPosition(Alt(temp), terSymbol); if (temp ) table[tempPos][topPos] ) { break; } i--; } while (i 0); // 执行计算 int result 0; char op values[i2]; switch(op) { case : result values[i1] values[i3]; break; case -: result values[i1] - values[i3]; break; case *: result values[i1] * values[i3]; break; case /: result values[i1] / values[i3]; break; case (: result values[i2]; break; // 处理括号 } // 弹出归约部分 while (k i) { Pop(stack); k--; } // 压入归约结果 Push(stack, N); values[k] result; } } }5. 工程实践构建完整计算器程序现在我们将所有部分组合起来构建一个完整的计算器程序。这个程序将能够处理带括号的四则运算表达式。5.1 程序架构设计我们采用模块化设计将程序分为以下几个部分文法处理模块读取和存储文法规则集合计算模块计算FirstVT和LastVT集合优先表模块构建和存储优先关系表分析器模块实现算符优先分析算法计算模块执行实际算术运算主控模块协调各模块工作5.2 错误处理机制一个健壮的计算器需要能够处理各种错误输入int ValidateExpression(char* expr) { int parenCount 0; int len strlen(expr); // 检查括号匹配 for (int i 0; i len; i) { if (expr[i] () parenCount; else if (expr[i] )) parenCount--; if (parenCount 0) { printf(错误不匹配的右括号\n); return 0; } } if (parenCount ! 0) { printf(错误不匹配的左括号\n); return 0; } // 检查运算符位置 for (int i 0; i len-1; i) { if (IsOperator(expr[i]) IsOperator(expr[i1])) { printf(错误连续的运算符\n); return 0; } } return 1; }5.3 用户界面实现虽然我们的重点是算法实现但一个友好的用户界面也很重要void RunCalculator() { printf(简易计算器 (输入quit退出)\n); printf(支持运算符: - * / ( )\n); char input[256]; while (1) { printf(\n请输入表达式: ); fgets(input, sizeof(input), stdin); // 处理输入 input[strcspn(input, \n)] 0; if (strcmp(input, quit) 0) break; // 验证并添加结束符# if (!ValidateExpression(input)) continue; char expr[300]; sprintf(expr, %s#, input); // 执行计算 Control(expr); } }5.4 性能优化技巧在实际实现中我们可以采用一些优化策略预计算优先关系表对于固定文法可以预先计算好优先关系表避免每次运行时重新计算使用更高效的数据结构比如用哈希表存储优先关系加快查找速度表达式预处理去除空格统一数字格式等错误恢复机制当发现错误时尝试恢复并继续分析// 优化后的优先关系查找 char GetPriority(char a, char b) { static char priorityTable[7][7] { // - * / ( ) # {,,,,,,}, // {,,,,,,}, // - {,,,,,,}, // * {,,,,,,}, // / {,,,,,, }, // ( {,,,, ,,}, // ) {,,,,, ,} // # }; int row GetOperatorIndex(a); int col GetOperatorIndex(b); if (row -1 || col -1) return ; return priorityTable[row][col]; }6. 扩展功能与进阶方向基础计算器完成后我们可以考虑添加更多功能6.1 支持更多运算符// 添加指数运算支持 case ^: result pow(values[i1], values[i3]); break;6.2 支持变量和赋值// 简单的变量存储 struct Variable { char name; int value; } vars[26]; int GetVariableValue(char name) { return vars[tolower(name)-a].value; }6.3 添加数学函数支持// 处理数学函数 if (strncmp(expri, sin(, 4) 0) { double angle EvaluateSubExpression(expri4); return sin(angle * M_PI / 180); }6.4 图形界面版本虽然本文重点在算法但了解如何将核心算法与GUI结合也很有价值// 伪代码示例 - 按钮回调函数 void onEqualsClicked() { char* expr getTextFromInput(); int result EvaluateExpression(expr); displayResult(result); }实现一个完整的计算器项目需要考虑许多工程细节模块化设计、错误处理、用户交互等。这个项目虽然基础但涵盖了编译器设计中表达式处理的核心理念。当你看到自己亲手打造的计算器正确解析并计算复杂表达式时那种成就感是无与伦比的。