C语言学习学习笔记20260704-中缀表达式求值（双栈法）

C语言学习学习笔记20260704-中缀表达式求值（双栈法）

1. 题目概述

• 目标：计算包含+、-、*和()的整数算术表达式的值。
• 输入：字符串s（长度≤ \le≤100），可能包含空格。
• 输出：计算结果（整型）。
• 难点：
  • 需要处理运算符优先级（先乘除后加减）。
  • 需要处理括号改变优先级。
  • 需要解析多位数字（如 “123”）。

2. 核心算法：双栈模拟

这是解决此类问题的经典O ( n ) O(n)O(n)算法。我们需要维护两个栈：

算法流程图

1. 扫描字符：从左向右遍历字符串。
2. 数字处理：遇到数字则连续读取，拼接成完整整数压入nums。
3. 左括号(：直接压入ops，作为优先级的“屏障”。
4. 右括号)：触发计算，不断弹出ops中的运算符进行计算，直到遇到匹配的(为止。
5. 运算符 (+,-,*)：
   • 比较当前运算符与ops栈顶运算符的优先级。
   • 若栈顶优先级 高于 当前优先级，说明栈顶的运算应该先执行（例如栈顶是*，当前是+；或者栈顶是*，当前也是*）。此时弹出并计算。
   • 重复上述过程直到栈空或栈顶是(或栈顶优先级更低。
   • 将当前运算符压入ops。
6. 收尾：遍历结束后，依次弹出ops中剩余运算符计算，nums栈顶即为最终结果。

3. 代码实现详解

以下是基于 C 语言的完整实现：

#include<stdio.h>#include<string.h>#include<ctype.h>// 定义栈最大容量，根据题目约束预留空间#defineMAXN1005/** * @brief 计算带括号、加减乘的中缀整数表达式 */intsolve(char*s){intnums[MAXN];// 操作数栈charops[MAXN];// 运算符栈inttop_num=0;// 数字栈指针inttop_op=0;// 运算符栈指针intlen=strlen(s);inti=0;while(i<len){charc=s[i];// 1. 跳过空格if(c==' '){i++;continue;}// 2. 解析数字（处理多位数）if(isdigit(c)){intnum=0;while(i<len&&isdigit(s[i])){num=num*10+(s[i]-'0');i++;}nums[top_num++]=num;continue;// 注意：这里已经移动了 i，不需要再 i++}// 3. 左括号直接入栈if(c=='('){ops[top_op++]=c;}// 4. 右括号：触发括号内计算elseif(c==')'){while(top_op>0&&ops[top_op-1]!='('){// 执行一次计算逻辑charop=ops[--top_op];intb=nums[--top_num];inta=nums[--top_num];intres=(op=='+')?a+b:((op=='-')?a-b:a*b);nums[top_num++]=res;}// 弹出对应的左括号if(top_op>0)top_op--;}// 5. 处理普通运算符else{// 定义优先级：* 为 2，+ - 为 1intcurr_pri=(c=='*')?2:1;// 当栈非空且栈顶不是左括号时while(top_op>0&&ops[top_op-1]!='('){chartop_c=ops[top_op-1];inttop_pri=(top_c=='*')?2:1;// 如果栈顶优先级 >= 当前优先级，先算栈顶的if(top_pri>=curr_pri){charop=ops[--top_op];intb=nums[--top_num];inta=nums[--top_num];intres=(op=='+')?a+b:((op=='-')?a-b:a*b);nums[top_num++]=res;}else{break;// 栈顶优先级低，停止循环}}// 当前运算符入栈ops[top_op++]=c;}i++;}// 6. 处理栈中剩余的运算符while(top_op>0){charop=ops[--top_op];intb=nums[--top_num];inta=nums[--top_num];intres=(op=='+')?a+b:((op=='-')?a-b:a*b);nums[top_num++]=res;}returnnums[0];}

4. 关键细节与易错点

1. 多位数解析：

   • 不能只读一个字符就认为是数字。必须使用while(isdigit(...))循环读取，并通过num = num * 10 + ...拼接。

2. 运算顺序（减法/除法）：

   • 栈是后进先出（LIFO）。
   • 对于表达式a - b，入栈顺序是先a后b。
   • 出栈计算时，先弹出的是b（右操作数），后弹出的是a（左操作数）。
   • 代码体现：int b = nums[--top_num]; int a = nums[--top_num]; res = a - b;。

3. 优先级判断：

   • 只有当栈顶优先级高于当前优先级时才弹栈计算。
   • 例如：栈顶是*(2)，当前是*(2)。因为乘法是从左往右算的，所以先算前面的*，条件成立。
   • 例如：栈顶是+(1)，当前是*(2)。因为乘法优先级高，后面的*应该先算，所以不弹栈，直接把*压进去。

4. 括号的处理：

   • 左括号(在栈内时，它的优先级被视为最低（或者说是一个特殊的边界），任何运算符都可以压在它上面。
   • 只有遇到右括号)时，才会强制清空括号内的所有运算。