C语言学习学习笔记20260704-中缀表达式求值双栈法1. 题目概述目标计算包含、-、*和()的整数算术表达式的值。输入字符串s长度≤ \le≤100可能包含空格。输出计算结果整型。难点需要处理运算符优先级先乘除后加减。需要处理括号改变优先级。需要解析多位数字如 “123”。2. 核心算法双栈模拟这是解决此类问题的经典O ( n ) O(n)O(n)算法。我们需要维护两个栈栈名称作用存储内容nums(操作数栈)暂存等待计算的数字int类型的数值ops(运算符栈)暂存等待执行的运算符号char类型的,-,*,(算法流程图扫描字符从左向右遍历字符串。数字处理遇到数字则连续读取拼接成完整整数压入nums。左括号(直接压入ops作为优先级的“屏障”。右括号)触发计算不断弹出ops中的运算符进行计算直到遇到匹配的(为止。运算符 (,-,*)比较当前运算符与ops栈顶运算符的优先级。若栈顶优先级 高于 当前优先级说明栈顶的运算应该先执行例如栈顶是*当前是或者栈顶是*当前也是*。此时弹出并计算。重复上述过程直到栈空或栈顶是(或栈顶优先级更低。将当前运算符压入ops。收尾遍历结束后依次弹出ops中剩余运算符计算nums栈顶即为最终结果。3. 代码实现详解以下是基于 C 语言的完整实现#includestdio.h#includestring.h#includectype.h// 定义栈最大容量根据题目约束预留空间#defineMAXN1005/** * brief 计算带括号、加减乘的中缀整数表达式 */intsolve(char*s){intnums[MAXN];// 操作数栈charops[MAXN];// 运算符栈inttop_num0;// 数字栈指针inttop_op0;// 运算符栈指针intlenstrlen(s);inti0;while(ilen){charcs[i];// 1. 跳过空格if(c ){i;continue;}// 2. 解析数字处理多位数if(isdigit(c)){intnum0;while(ilenisdigit(s[i])){numnum*10(s[i]-0);i;}nums[top_num]num;continue;// 注意这里已经移动了 i不需要再 i}// 3. 左括号直接入栈if(c(){ops[top_op]c;}// 4. 右括号触发括号内计算elseif(c)){while(top_op0ops[top_op-1]!(){// 执行一次计算逻辑charopops[--top_op];intbnums[--top_num];intanums[--top_num];intres(op)?ab:((op-)?a-b:a*b);nums[top_num]res;}// 弹出对应的左括号if(top_op0)top_op--;}// 5. 处理普通运算符else{// 定义优先级* 为 2 - 为 1intcurr_pri(c*)?2:1;// 当栈非空且栈顶不是左括号时while(top_op0ops[top_op-1]!(){chartop_cops[top_op-1];inttop_pri(top_c*)?2:1;// 如果栈顶优先级 当前优先级先算栈顶的if(top_pricurr_pri){charopops[--top_op];intbnums[--top_num];intanums[--top_num];intres(op)?ab:((op-)?a-b:a*b);nums[top_num]res;}else{break;// 栈顶优先级低停止循环}}// 当前运算符入栈ops[top_op]c;}i;}// 6. 处理栈中剩余的运算符while(top_op0){charopops[--top_op];intbnums[--top_num];intanums[--top_num];intres(op)?ab:((op-)?a-b:a*b);nums[top_num]res;}returnnums[0];}4. 关键细节与易错点多位数解析不能只读一个字符就认为是数字。必须使用while(isdigit(...))循环读取并通过num num * 10 ...拼接。运算顺序减法/除法栈是后进先出LIFO。对于表达式a - b入栈顺序是先a后b。出栈计算时先弹出的是b右操作数后弹出的是a左操作数。代码体现int b nums[--top_num]; int a nums[--top_num]; res a - b;。优先级判断只有当栈顶优先级高于当前优先级时才弹栈计算。例如栈顶是*(2)当前是*(2)。因为乘法是从左往右算的所以先算前面的*条件成立。例如栈顶是(1)当前是*(2)。因为乘法优先级高后面的*应该先算所以不弹栈直接把*压进去。括号的处理左括号(在栈内时它的优先级被视为最低或者说是一个特殊的边界任何运算符都可以压在它上面。只有遇到右括号)时才会强制清空括号内的所有运算。
C语言学习学习笔记20260704-中缀表达式求值（双栈法）
C语言学习学习笔记20260704-中缀表达式求值双栈法1. 题目概述目标计算包含、-、*和()的整数算术表达式的值。输入字符串s长度≤ \le≤100可能包含空格。输出计算结果整型。难点需要处理运算符优先级先乘除后加减。需要处理括号改变优先级。需要解析多位数字如 “123”。2. 核心算法双栈模拟这是解决此类问题的经典O ( n ) O(n)O(n)算法。我们需要维护两个栈栈名称作用存储内容nums(操作数栈)暂存等待计算的数字int类型的数值ops(运算符栈)暂存等待执行的运算符号char类型的,-,*,(算法流程图扫描字符从左向右遍历字符串。数字处理遇到数字则连续读取拼接成完整整数压入nums。左括号(直接压入ops作为优先级的“屏障”。右括号)触发计算不断弹出ops中的运算符进行计算直到遇到匹配的(为止。运算符 (,-,*)比较当前运算符与ops栈顶运算符的优先级。若栈顶优先级 高于 当前优先级说明栈顶的运算应该先执行例如栈顶是*当前是或者栈顶是*当前也是*。此时弹出并计算。重复上述过程直到栈空或栈顶是(或栈顶优先级更低。将当前运算符压入ops。收尾遍历结束后依次弹出ops中剩余运算符计算nums栈顶即为最终结果。3. 代码实现详解以下是基于 C 语言的完整实现#includestdio.h#includestring.h#includectype.h// 定义栈最大容量根据题目约束预留空间#defineMAXN1005/** * brief 计算带括号、加减乘的中缀整数表达式 */intsolve(char*s){intnums[MAXN];// 操作数栈charops[MAXN];// 运算符栈inttop_num0;// 数字栈指针inttop_op0;// 运算符栈指针intlenstrlen(s);inti0;while(ilen){charcs[i];// 1. 跳过空格if(c ){i;continue;}// 2. 解析数字处理多位数if(isdigit(c)){intnum0;while(ilenisdigit(s[i])){numnum*10(s[i]-0);i;}nums[top_num]num;continue;// 注意这里已经移动了 i不需要再 i}// 3. 左括号直接入栈if(c(){ops[top_op]c;}// 4. 右括号触发括号内计算elseif(c)){while(top_op0ops[top_op-1]!(){// 执行一次计算逻辑charopops[--top_op];intbnums[--top_num];intanums[--top_num];intres(op)?ab:((op-)?a-b:a*b);nums[top_num]res;}// 弹出对应的左括号if(top_op0)top_op--;}// 5. 处理普通运算符else{// 定义优先级* 为 2 - 为 1intcurr_pri(c*)?2:1;// 当栈非空且栈顶不是左括号时while(top_op0ops[top_op-1]!(){chartop_cops[top_op-1];inttop_pri(top_c*)?2:1;// 如果栈顶优先级 当前优先级先算栈顶的if(top_pricurr_pri){charopops[--top_op];intbnums[--top_num];intanums[--top_num];intres(op)?ab:((op-)?a-b:a*b);nums[top_num]res;}else{break;// 栈顶优先级低停止循环}}// 当前运算符入栈ops[top_op]c;}i;}// 6. 处理栈中剩余的运算符while(top_op0){charopops[--top_op];intbnums[--top_num];intanums[--top_num];intres(op)?ab:((op-)?a-b:a*b);nums[top_num]res;}returnnums[0];}4. 关键细节与易错点多位数解析不能只读一个字符就认为是数字。必须使用while(isdigit(...))循环读取并通过num num * 10 ...拼接。运算顺序减法/除法栈是后进先出LIFO。对于表达式a - b入栈顺序是先a后b。出栈计算时先弹出的是b右操作数后弹出的是a左操作数。代码体现int b nums[--top_num]; int a nums[--top_num]; res a - b;。优先级判断只有当栈顶优先级高于当前优先级时才弹栈计算。例如栈顶是*(2)当前是*(2)。因为乘法是从左往右算的所以先算前面的*条件成立。例如栈顶是(1)当前是*(2)。因为乘法优先级高后面的*应该先算所以不弹栈直接把*压进去。括号的处理左括号(在栈内时它的优先级被视为最低或者说是一个特殊的边界任何运算符都可以压在它上面。只有遇到右括号)时才会强制清空括号内的所有运算。
