在编写简单的计算器时我们经常会遇到一个问题如何解析并计算一个由数字和、-、*、/组成的表达式且不包含括号这类问题非常适合用栈这种数据结构来解决。本文将详细介绍一种基于两个栈操作数栈和操作符栈的算法并给出完整的 C 语言实现。一、算法原理我们使用双栈法来直接计算中缀表达式即我们习惯的书写方式如35*2-8/4。核心思想是维护两个栈操作数栈pnum_stack存储已经解析出的数字。操作符栈popt_stack存储等待计算的操作符。从左到右扫描表达式遇到数字则完整读取整个整数压入操作数栈。遇到操作符 - * /如果操作符栈为空直接压栈。否则比较当前操作符与栈顶操作符的优先级若当前操作符优先级高于栈顶则压栈因为高优先级需要先计算。若当前操作符优先级低于或等于栈顶则弹出栈顶操作符并从操作数栈弹出两个数进行计算将结果压回操作数栈重复比较直到当前操作符可以压栈。当表达式扫描完毕依次弹出操作符栈中的操作符并计算直到栈为空。最终操作数栈的栈顶元素即为表达式的结果。这种算法的本质是利用栈的先进后出特性模拟了操作符优先级和计算顺序无需显式转换为后缀表达式。二、数据结构设计我们使用链式栈动态链表实现具体定义如下见stack.hctypedef int Data_t; typedef struct node { Data_t data; struct node *pnext; } Node_s; typedef struct stack { Node_s *ptop; // 栈顶指针 int clen; // 栈中元素个数 } Stack_s;提供的基本操作包括create_stack()创建空栈push_stack()压栈pop_stack()弹出栈顶元素get_stack_top()获取栈顶元素不弹出is_empty_stack()判断栈是否为空destroy_stack()销毁栈三、核心计算逻辑核心函数是int get_result(char *press, int *result)它接收一个字符串表达式并将计算结果写入result。下面逐步分析其实现。1. 辅助函数is_num_char(char ch)判断字符是否为数字0~9。get_opt_lever(int opt)返回操作符的优先级和-为 1*和/为 2。get_num(int num1, int num2, int opt)根据操作符计算num1 opt num2的结果注意顺序。2. 主循环流程cchar *p press; int num 0; int opt 0; int num1 0, num2 0; int ret 0; while (1) { // 退出条件扫描完且操作符栈为空 if (\0 *p is_empty_stack(popt_stack)) { break; } // 处理连续数字字符拼成整数 while (is_num_char(*p)) { num num * 10 (*p - 0); p; if (!is_num_char(*p)) { // 数字结束压栈 push_stack(pnum_stack, num); num 0; } } // 如果操作符栈为空直接压入当前操作符 if (is_empty_stack(popt_stack)) { push_stack(popt_stack, *p); p; continue; } // 获取栈顶操作符 get_stack_top(popt_stack, opt); // 如果当前操作符优先级更高则压栈注意处理表达式结束 \0 if (\0 ! *p get_opt_lever(*p) get_opt_lever(opt)) { push_stack(popt_stack, *p); p; } // 否则当前优先级 栈顶 或 表达式结束弹出栈顶并计算 else if (\0 *p || get_opt_lever(*p) get_opt_lever(opt)) { pop_stack(popt_stack, opt); pop_stack(pnum_stack, num2); pop_stack(pnum_stack, num1); ret get_num(num1, num2, opt); push_stack(pnum_stack, ret); // 注意此时不移动 p因为当前字符还未处理或已结束 } }3. 特殊处理细节数字读取当遇到数字时一直累加直到非数字然后立即压栈。这保证了多位数如123被正确识别。操作符比较当表达式未结束且当前操作符优先级高于栈顶时直接压栈否则先计算栈顶操作符。这确保了*和/优先于和-计算。表达式结束当*p \0时强制弹出栈顶操作符并计算直到栈空。最终操作数栈中只剩一个结果。四、主函数与运行示例cint main(void) { int result 0; char press[128] {0}; gets(press); // 注意gets 不安全推荐使用 fgets int ret get_result(press, result); if (0 ret) { printf(%s %d\n, press, result); } return 0; }编译并运行假设源文件为calculate.c和stack.cbashgcc -o calculator calculate.c stack.c ./calculator输入示例text35*2-8/4输出text35*2-8/4 11计算过程5*210310138/4213-211#include stdio.h #include stack.h int is_num_char(char ch) { if(0chch9) { return 1; } return 0; } int get_opt_lever(int opt) { switch(opt) { case : case -: return 1; case *: case /: return 2; } } int get_num(int num1,int num2,int opt) { switch(opt) { case : return num1num2; case -: return num1-num2; case *: return num1*num2; case /: return num1/num2; } } int get_result(char *press,int *result) { Stack_s *pnum_stackcreate_stack(); Stack_s *popt_stackcreate_stack(); if(NULLpnum_stack||NULLpop_stack) { return -1; } char *ppress; int num0; int opt0; int num10,num20; int ret0; while(1) { if(\0*p is_empty_stack(popt_stack)) { break; } while(is_num_char(*p)) { //int num0; numnum*10(*p-0); p; if(!is_num_char(*p)) { push_stack(pnum_stack,num); num0; } } if(is_empty_stack(popt_stack)) { push_stack(popt_stack,*p); p; continue; } get_stack_top(popt_stack,opt); if(\0!*p get_opt_lever(*p)get_opt_lever(opt)) { push_stack(popt_stack,*p); p; } else if(\0*p || get_opt_lever(*p)get_opt_lever(opt)) { pop_stack(popt_stack,opt); //int num10,num20; pop_stack(pnum_stack,num2); pop_stack(pnum_stack,num1); //int ret0; ret get_num(num1,num2,opt); push_stack(pnum_stack,ret); } } get_stack_top(pnum_stack,result); destroy_stack(pnum_stack); destroy_stack(popt_stack); return 0; } int main(void) { int result0; char press[128]{0}; gets(press); int retget_result(press,result); if(0ret) { printf(%s %d\n, press, result); } return 0; }#include stdio.h #include stdlib.h #include stack.h Stack_s *create_stack() { Stack_s *pstackmalloc(sizeof(Stack_s)); if(NULLpstack) { printf(malloc error\n); return NULL; } pstack-ptopNULL; pstack-clen0; return pstack; } int is_empty_stack(Stack_s *pstack) { return NULLpstack-ptop; } int push_stack(Stack_s *pstack, Data_t data) { Node_s *pinsertmalloc(sizeof(Node_s)); if(pinsertNULL) { printf(malloc error\n); return -1; } pinsert-datadata; pinsert-pnextNULL; pinsert-pnextpstack-ptop; pstack-ptoppinsert; pstack-clen; return 0; } int pop_stack(Stack_s *pstack, Data_t *pdata) { if(is_empty_stack(pstack)) { return -1; } Node_s *pfreepstack-ptop; pstack-ptoppfree-pnext; if(pdata!NULL) { *pdatapfree-data; } free(pfree); pstack-clen--; return 0; } int get_stack_top(Stack_s *pstack,Data_t *ptopdata) { if(is_empty_stack(pstack)) { return -1; } else { *ptopdatapstack-ptop-data; return 0; } } void show_stack(Stack_s *pstack) { Node_s *ptmppstack-ptop; while(ptmp) { printf(%d ,ptmp-data); ptmpptmp-pnext; } printf(\n); } void clear_stack(Stack_s *pstack) { while(!is_empty_stack(pstack)) { pop_stack(pstack,NULL); } } void destroy_stack(Stack_s *pstack) { clear_stack(pstack); free(pstack); }#ifndef __STACK_H__ #define __STACK_H__ typedef int Data_t; typedef struct node { Data_t data; struct node *pnext; }Node_s; typedef struct stack { Node_s *ptop; int clen; }Stack_s; Stack_s *create_stack(); int is_empty_stack(Stack_s *pstack); int push_stack(Stack_s *pstack, Data_t data); int pop_stack(Stack_s *pstack, Data_t *pdata); int get_stack_top(Stack_s *pstack,Data_t *ptop); void show_stack(Stack_s *pstack); void clear_stack(Stack_s *pstack); void destroy_stack(Stack_s *pstack); #endif五、代码中的注意事项整型除法本实现中除法为整数除法/直接截断小数部分。输入安全性gets()存在缓冲区溢出风险实际使用建议改用fgets(press, sizeof(press), stdin)。错误处理若栈创建失败或出现非法字符函数返回-1但主函数未做完整错误提示读者可自行扩展。操作符优先级仅支持 - * /若输入其他字符未定义行为。六、总结通过双栈法我们能够高效地计算不含括号的四则运算表达式。该算法的时间复杂度为 O(n)空间复杂度为 O(n)n 为表达式长度。其核心思想是根据操作符优先级动态决定何时计算而不是简单地从左到右依次计算。这种实现方式也便于扩展例如增加取模%或幂运算^只需在优先级表和计算函数中添加相应逻辑即可。希望这篇博客能帮助你理解栈在表达式求值中的应用并为你编写自己的计算器提供参考。