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 语言的完整实现：
#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. 关键细节与易错点
多位数解析：
- 不能只读一个字符就认为是数字。必须使用
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)。因为乘法优先级高，后面的*应该先算，所以不弹栈，直接把*压进去。
括号的处理：
- 左括号
(在栈内时，它的优先级被视为最低（或者说是一个特殊的边界），任何运算符都可以压在它上面。 - 只有遇到右括号
)时，才会强制清空括号内的所有运算。
- 左括号