ARTICLE DETAIL

建站实战干货

来自一线的建站与推广经验沉淀，每一条都经过真实交付验证。

首页 / 资讯中心 / 正文

C语言实现波兰表达式求值器：栈数据结构与算法实践

2026/8/26 11:05:21 拓冰建站 浏览量
C语言实现波兰表达式求值器：栈数据结构与算法实践 1. 项目概述从“波兰表达式”说起最近在整理一些老项目的代码翻到了一个当年让我挠头很久的“波兰表达式求值器”。这玩意儿听起来挺学术但说白了就是一种不需要括号就能明确运算顺序的表达式写法。比如我们熟悉的(1 2) * 3写成波兰表达式也叫前缀表达式就是* 1 2 3。你可能会问这有什么用在编译器设计、计算器逻辑、甚至一些配置文件解析里这种结构清晰、无二义性的表达式处理方式非常关键。用C语言来实现它不仅能帮你深入理解栈Stack这个数据结构更是对字符串处理、递归思维的一次绝佳训练。无论你是正在啃《数据结构》的学生还是想巩固C语言功底的开发者跟着我一起把这个小项目走一遍绝对能让你对“表达式求值”这件事有脱胎换骨的认识。2. 核心思路与数据结构选型2.1 为什么是栈处理任何表达式求值核心都在于管理操作数和运算符的“时序”。对于中缀表达式我们日常写的a b需要处理括号和优先级复杂度较高。而波兰表达式前缀或逆波兰表达式后缀巧妙地避开了这个麻烦它们的运算符位置决定了运算顺序使得求值过程可以线性扫描完成。对于前缀表达式* 1 2 3求值算法是从右向左扫描表达式。遇到操作数如3,2,1就将其压入栈。遇到运算符如,*就从栈顶弹出两个操作数进行运算然后将结果压回栈。扫描结束后栈中剩下的唯一元素就是最终结果。这个过程天然契合栈的“后进先出”LIFO特性。你不需要记住之前遇到了什么只需要关心最近遇到的两个操作数。因此栈是我们实现求值器的唯一核心数据结构。2.2 栈的实现数组还是链表在C语言里实现栈通常有两种选择基于数组的静态/动态栈和基于链表的栈。数组栈实现简单内存连续访问速度快。但需要预先确定大小或者涉及动态扩容realloc处理不当容易造成内存浪费或溢出。链表栈动态增长理论上没有容量限制受制于内存但每个节点需要额外的指针空间且访问速度稍慢。对于这个表达式求值项目表达式的长度通常是已知或可控的。我个人的选择是使用动态数组栈。原因如下性能求值过程涉及频繁的入栈、出栈操作数组的连续内存访问在缓存层面更友好。简单性管理一个动态数组比管理链表节点更直观出错概率低。实用性我们可以预设一个合理的初始大小如64如果表达式异常复杂导致栈满再进行一次扩容操作这在绝大多数情况下都够用且高效。注意如果你在嵌入式等内存极度受限的环境可能需要精确计算最大栈深度使用静态数组。但对于通用学习目的动态数组栈在易用性和性能上取得了很好的平衡。2.3 整体算法流程图文字描述为了让思路更清晰我们把算法步骤拆解如下初始化创建一个空栈用于存放操作数double类型。分割表达式将输入的字符串表达式如“* 1 2 3”按照空格分割成一个个令牌token如[“*”, “”, “1”, “2”, “3”]。逆序扫描从令牌数组的最后一个元素开始向前遍历。如果是操作数将其转换为double类型压入栈。如果是运算符从栈中连续弹出两个操作数注意顺序先弹出的是右操作数后弹出的是左操作数根据运算符进行计算将结果压回栈。获取结果遍历结束后栈中应只剩下一个元素即为表达式的值。弹出并返回它。清理销毁栈释放内存。3. 关键实现细节与代码剖析接下来我们进入具体的代码实现环节。我会把核心代码拆开逐一解释。3.1 栈结构的定义与操作首先我们定义栈的数据结构。这里我选择用动态数组实现。// stack.h #ifndef STACK_H #define STACK_H typedef struct { double* data; // 指向栈元素数组的指针 int capacity; // 栈的总容量 int top; // 栈顶索引指向下一个空闲位置 } Stack; // 栈操作函数声明 Stack* create_stack(int initial_capacity); void destroy_stack(Stack* s); int is_empty(Stack* s); void push(Stack* s, double value); double pop(Stack* s); double peek(Stack* s); // 查看栈顶元素但不弹出 #endif// stack.c #include stdio.h #include stdlib.h #include stack.h Stack* create_stack(int initial_capacity) { Stack* s (Stack*)malloc(sizeof(Stack)); if (!s) return NULL; s-data (double*)malloc(sizeof(double) * initial_capacity); if (!s-data) { free(s); return NULL; } s-capacity initial_capacity; s-top 0; // 栈空时top为0 return s; } void destroy_stack(Stack* s) { if (s) { free(s-data); free(s); } } int is_empty(Stack* s) { return s-top 0; } void push(Stack* s, double value) { // 检查栈是否已满满则扩容简单翻倍策略 if (s-top s-capacity) { int new_capacity s-capacity * 2; double* new_data (double*)realloc(s-data, sizeof(double) * new_capacity); if (!new_data) { fprintf(stderr, 栈扩容失败\n); exit(EXIT_FAILURE); } s-data new_data; s-capacity new_capacity; } s-data[s-top] value; // 存入数据top加1 } double pop(Stack* s) { if (is_empty(s)) { fprintf(stderr, 错误尝试从空栈弹出元素\n); exit(EXIT_FAILURE); } return s-data[--s-top]; // top减1然后返回该位置的值 } double peek(Stack* s) { if (is_empty(s)) { fprintf(stderr, 错误尝试查看空栈的栈顶\n); exit(EXIT_FAILURE); } return s-data[s-top - 1]; }关键点解析top的设计这里我让top指向下一个可用的空闲位置。push时存入data[top]然后toppop时先top--再返回data[top]。这种设计非常直观判断栈空就是top 0。动态扩容在push函数中我们检查top capacity。如果栈满了使用realloc将容量翻倍。这是一种简单有效的策略。在生产环境中你可能需要更复杂的策略或错误处理。错误处理pop和peek在栈空时直接报错退出。在更健壮的程序中应该返回一个错误码或使用断言但为了示例清晰这里简化了。3.2 表达式令牌化Tokenization输入的表达式是一个字符串我们需要将其分割成操作数和运算符。我们约定用空格分隔各个令牌。// 一个简单的字符串分割函数用于将表达式拆分成令牌数组。 // 注意这个函数会修改原始字符串并为令牌数组分配内存。 // 返回令牌的数量。 int tokenize_expression(char* expr, char*** tokens) { int count 0; int capacity 10; *tokens (char**)malloc(sizeof(char*) * capacity); if (!*tokens) return -1; char* token strtok(expr, ); // 使用空格分割 while (token ! NULL) { // 如果数组满了扩容 if (count capacity) { capacity * 2; char** new_tokens (char**)realloc(*tokens, sizeof(char*) * capacity); if (!new_tokens) { // 内存分配失败清理已分配的资源 for (int i 0; i count; i) free((*tokens)[i]); free(*tokens); return -1; } *tokens new_tokens; } // 复制令牌字符串 (*tokens)[count] (char*)malloc(strlen(token) 1); if (!(*tokens)[count]) { // 内存分配失败清理 for (int i 0; i count; i) free((*tokens)[i]); free(*tokens); return -1; } strcpy((*tokens)[count], token); count; token strtok(NULL, ); } return count; // 返回令牌个数 }实操心得strtok函数会修改原始字符串用\0替换分隔符。如果你需要保留原始表达式务必先使用strdup复制一份。这个小函数里包含了动态数组扩容的经典模式和栈的扩容逻辑类似值得仔细体会。记得最后要释放tokens数组及其中的每个字符串避免内存泄漏。3.3 核心求值函数这是整个项目的大脑它串联起栈操作和令牌处理。#include stdio.h #include stdlib.h #include string.h #include ctype.h #include stack.h // 判断字符串是否为运算符 int is_operator(const char* token) { return (strlen(token) 1 strchr(-*/, token[0]) ! NULL); } // 执行运算 double apply_operator(char op, double a, double b) { switch (op) { case : return a b; case -: return a - b; case *: return a * b; case /: if (b 0.0) { fprintf(stderr, 错误除零错误\n); exit(EXIT_FAILURE); } return a / b; default: fprintf(stderr, 错误未知运算符 %c\n, op); exit(EXIT_FAILURE); } } // 波兰表达式求值主函数 double evaluate_prefix_expression(char* expression) { char** tokens NULL; int token_count tokenize_expression(expression, tokens); if (token_count 0) { fprintf(stderr, 表达式为空或令牌化失败。\n); if (tokens) free(tokens); exit(EXIT_FAILURE); } Stack* stack create_stack(16); // 初始容量设为16 if (!stack) { fprintf(stderr, 栈创建失败。\n); // 清理tokens for (int i 0; i token_count; i) free(tokens[i]); free(tokens); exit(EXIT_FAILURE); } // **关键步骤从右向左扫描** for (int i token_count - 1; i 0; --i) { if (is_operator(tokens[i])) { // 是运算符弹出两个操作数 if (is_empty(stack)) { fprintf(stderr, 错误表达式不合法运算符缺少操作数。\n); destroy_stack(stack); for (int j 0; j token_count; j) free(tokens[j]); free(tokens); exit(EXIT_FAILURE); } double right_operand pop(stack); // 先弹出的是右操作数 if (is_empty(stack)) { fprintf(stderr, 错误表达式不合法运算符缺少操作数。\n); destroy_stack(stack); for (int j 0; j token_count; j) free(tokens[j]); free(tokens); exit(EXIT_FAILURE); } double left_operand pop(stack); // 后弹出的是左操作数 double result apply_operator(tokens[i][0], left_operand, right_operand); push(stack, result); } else { // 尝试解析为操作数 char* endptr; double num strtod(tokens[i], endptr); if (endptr tokens[i]) { // 转换失败 fprintf(stderr, 错误无法识别的令牌 %s\n, tokens[i]); destroy_stack(stack); for (int j 0; j token_count; j) free(tokens[j]); free(tokens); exit(EXIT_FAILURE); } push(stack, num); } } // 求值结束栈中应只剩一个元素 double final_result pop(stack); if (!is_empty(stack)) { fprintf(stderr, 警告求值结束后栈非空表达式可能有多余的操作数。\n); // 清空栈 while (!is_empty(stack)) pop(stack); } // 清理资源 destroy_stack(stack); for (int i 0; i token_count; i) free(tokens[i]); free(tokens); return final_result; }为什么从右向左扫描这是理解前缀表达式求值的关键。以* 1 2 3为例从左向右看第一个是*但此时我们不知道它的两个操作数是谁。从右向左看先看到3入栈看到2入栈看到1入栈。此时栈顶从上到下是[1, 2, 3]栈顶是1。接着看到弹出栈顶两个元素1和2计算123结果3入栈。现在栈是[3, 3]。最后看到*弹出3和3计算3*39入栈。栈中只剩[9]。 从右向左扫描保证了当遇到运算符时它的操作数已经在栈中准备好了。4. 功能扩展与边界处理一个基础的求值器完成了但要让它更健壮、更实用我们还需要考虑更多。4.1 支持更多运算符和函数目前只支持四则运算。我们可以轻松扩展比如支持乘方^、取模%甚至一元运算符如负号-和数学函数如sin,cos,sqrt。修改思路扩展is_operator和apply_operator增加对新运算符的判断和计算逻辑。对于乘方可能需要pow函数。处理一元运算符一元运算符如负号只消耗一个操作数。在扫描时需要判断当前运算符是一元的还是二元的。这可以通过检查运算符后的令牌或定义不同的符号如用_表示一元负号来实现。支持函数将sin、sqrt这类字符串视为特殊的“运算符”在apply_operator函数中调用对应的数学库函数。注意它们也只需要一个操作数。// 扩展的运算符判断 int is_operator(const char* token) { if (strlen(token) 1) { return strchr(-*/%^, token[0]) ! NULL; } // 检查是否是函数名 return (strcmp(token, sin) 0 || strcmp(token, cos) 0 || strcmp(token, sqrt) 0); } // 扩展的运算应用 double apply_operator(const char* op, double a, double b) { if (strcmp(op, ) 0) return a b; else if (strcmp(op, -) 0) return a - b; else if (strcmp(op, *) 0) return a * b; else if (strcmp(op, /) 0) { if (b 0.0) { /* 错误处理 */ } return a / b; } else if (strcmp(op, %) 0) return fmod(a, b); // 浮点数取模 else if (strcmp(op, ^) 0) return pow(a, b); else if (strcmp(op, sin) 0) return sin(b); // 假设sin是一元运算符用b作为参数 else if (strcmp(op, cos) 0) return cos(b); else if (strcmp(op, sqrt) 0) { if (b 0) { /* 错误处理 */ } return sqrt(b); } else { /* 未知运算符错误 */ } }在求值循环中对于函数类运算符只需要弹出一个操作数。4.2 健壮的错误处理上面的示例代码在出错时直接exit这不利于集成。更好的做法是让函数返回一个状态码并通过指针参数返回结果。typedef enum { EVAL_OK, EVAL_ERR_EMPTY_EXPR, EVAL_ERR_INVALID_TOKEN, EVAL_ERR_DIV_BY_ZERO, EVAL_ERR_STACK_UNDERFLOW, EVAL_ERR_STACK_OVERFLOW, EVAL_ERR_MEMORY } EvalStatus; EvalStatus evaluate_prefix_expr_safe(const char* expr, double* result) { if (!expr || !result) return EVAL_ERR_EMPTY_EXPR; // ... 复制表达式字符串令牌化等操作 ... // 所有原来的 exit(EXIT_FAILURE) 都改为返回相应的 EvalStatus // 在函数最后如果成功设置 *result final_result; 并返回 EVAL_OK; // 在任何失败的地方都要记得释放已分配的内存。 }这样调用者可以根据返回的错误码进行更精细的处理。4.3 处理复杂操作数负数、小数、科学计数法我们使用了strtod函数它本身已经非常强大可以完美解析-3.14、2.5e-2这样的字符串。这省去了我们自己解析数字的麻烦。只需要注意strtod的第二个参数endptr它指向转换结束后的下一个字符。如果endptr等于输入的字符串指针说明一个数字都没转换成功那就是无效令牌。5. 测试用例与常见问题排查写代码不测试等于闭着眼睛开车。我们来设计一些测试用例并看看可能会遇到哪些坑。5.1 测试用例设计一个好的测试集应该覆盖正常情况和各种边界、错误情况。测试用例表达式预期结果测试目的基础运算1 1 23测试基本加法基础运算2* 1 2 39测试复合表达式除法与优先级/ * 2 3 41.5测试除法验证前缀表达式无优先级困扰复杂嵌套- * / 15 - 7 1 1 3 2 1 15测试复杂嵌套表达式对应中缀(15/(7-(11)))*3 - (2(11))浮点数 3.14 -2.50.64测试浮点数运算单操作数55测试只有操作数的表达式错误用例缺少操作数 1应报错测试运算符缺少操作数的错误处理错误用例多余操作数 1 2 3应报错或警告测试表达式结束后栈非空的情况错误用例非法令牌 1 2应报错测试无法识别的运算符或操作数错误用例除零/ 1 0应报错测试除零保护5.2 常见问题与调试技巧在实际编码和测试中你几乎一定会遇到下面这些问题栈操作顺序错误症状计算结果完全不对尤其是减法和除法。原因从栈中弹出两个操作数时顺序弄反了。对于表达式- 5 3即5-3从右向左扫描3先入栈5后入栈。栈顶是5。遇到-时先弹出的是5作为右操作数后弹出的是3作为左操作数如果直接计算op1 - op2就会得到3-5-2错误。解决记住先弹出的是右操作数后弹出的是左操作数。在apply_operator中确保参数顺序正确apply_operator(-, left, right)。内存泄漏症状程序短期运行正常长期运行或多次调用后内存占用不断增长。原因malloc或strdup分配的内存没有在所有函数退出路径上被free。特别是在错误处理时容易忘记释放已分配的资源。解决为每个malloc立刻想好它的free在哪里。在函数中如果有多处错误返回使用goto cleanup跳转到统一的资源清理段落这是一种清晰且安全的做法在C语言中用于错误处理是公认的合理用法。EvalStatus func() { char* buf malloc(100); if (!buf) return EVAL_ERR_MEMORY; FILE* f fopen(file.txt, r); if (!f) { free(buf); // 每个错误点都要记得清理 return EVAL_ERR_FILE; } // ... 更多可能失败的操作 ... // 成功路径 fclose(f); free(buf); return EVAL_OK; }使用goto的版本更清晰EvalStatus func() { char* buf NULL; FILE* f NULL; EvalStatus status EVAL_OK; buf malloc(100); if (!buf) { status EVAL_ERR_MEMORY; goto cleanup; } f fopen(file.txt, r); if (!f) { status EVAL_ERR_FILE; goto cleanup; } // ... 业务逻辑 ... cleanup: if (f) fclose(f); if (buf) free(buf); return status; }令牌化失败或异常症状程序崩溃或输出乱码尤其在输入表达式没有用空格分隔时。原因strtok依赖分隔符。如果输入是*1 2 3它会被当成一个令牌*1无法识别。解决输入预处理可以写一个简单的函数在令牌化前确保运算符和操作数之间有空格。或者实现一个更强大的词法分析器逐个字符读取直接识别数字和运算符。增强令牌化不使用strtok而是自己遍历字符串。遇到数字或小数点持续读取直到遇到非数字字符这能更好地处理-3.14e2这样的科学计数法。遇到,-,*,/,^等单个字符视为运算符。遇到字母持续读取直到遇到非字母数字视为函数名如sin。浮点数精度问题症状0.1 0.2的结果不是精确的0.3而是0.30000000000000004。原因这是二进制浮点数的固有特性并非程序错误。解决对于需要精确比较的场景比如在测试中判断结果是否正确不要直接用而是判断两数之差的绝对值是否小于一个极小的数epsilon。#include math.h #define EPSILON 1e-12 if (fabs(actual_result - expected_result) EPSILON) { printf(测试通过\n); }6. 项目进阶与扩展思考实现基础版本后你可以尝试以下挑战让这个项目成为你简历上的亮点逆波兰表达式后缀表达式求值算法更简单从左向右扫描遇到操作数入栈遇到运算符弹出两个操作数计算即可。尝试修改代码支持它甚至可以写一个中缀转后缀的函数。支持变量例如表达式可以是 x 5同时传入一个变量绑定表{“x”: 10}。求值时遇到变量就从表中查找其值。交互式解释器实现一个简单的REPLRead-Eval-Print Loop循环让用户可以持续输入表达式并看到结果就像一个小计算器。性能分析与优化对于超长的表达式当前的实现每处理一个令牌都可能涉及malloc/free令牌数组。可以优化为使用静态缓冲区或更高效的内存池。使用valgrind工具检查是否有内存泄漏。单元测试框架不要再用printf手动测试了。集成一个如Unity或CMocka这样的轻量级C单元测试框架将上面的测试用例自动化。这个“波兰表达式求值”项目虽小却串联了C语言的核心指针、内存管理、字符串处理、数据结构。把它吃透你收获的绝不仅仅是一个可运行的程序而是一套解决复杂问题的思维方法和工程实践能力。我在第一次实现时就在操作数弹出顺序和内存释放上栽了跟头调试了大半天。希望我踩过的这些坑能帮你铺平一点学习的路。