C语言入门四题精讲：表达式求值到二分查找

刚接触C语言的大一新生，常常上课听得懂语法，一到独立写题就无从下手。本文挑选四道最具代表性的入门题——表达式求值、数位求和、九九乘法表、二分查找，逐一拆解思路、给出可落地的代码框架，并解释每一步“为什么这么写”。读完之后，你收获的不只是四道题的答案，而是一套可迁移的分析方法。

一、表达式求值：双栈算法的完整推导

1.1 先补齐前置知识：什么是栈

栈（Stack）是一种“后进先出”（LIFO）的线性数据结构：只允许在一端（栈顶）插入（push）和删除（pop）元素。可以把它想象成一摞盘子——放盘子放在最上面，拿盘子也从最上面拿。栈在表达式求值、函数调用、括号匹配等场景中都是核心工具。如果对栈还不熟悉，建议先查阅任意一本经典的数据结构教材或权威的算法学习资料，把 push、pop、top 三个基本操作弄清楚，再回到本题，会顺畅得多。

1.2 输入处理：把字符串解析成数字与符号

题目给的输入通常是一个表达式字符串，而不是现成的数字。很多新手卡在“我不会输入”。思路其实很直接：

1. 先把整行读入一个字符数组；
2. 逐个字符扫描，判断当前字符是运算符还是数字；
3. 如果是数字，继续向后找小数点：小数点左边按整数规则转换，右边按小数规则转换；若没有小数点，只转换整数部分。

数字字符转数值的通用技巧是利用字符编码的连续性：c - '0' 即得到该字符对应的 0~9 数值。整数部分按“高位累乘”的方式构造，例如 “123” 依次执行 val = val*10 + 1、val = val*10 + 2、val = val*10 + 3。小数部分则每多一位就把除数扩大 10 倍。

1.3 中缀与后缀：符号放的位置决定一切

生活中最常见的是中缀表达式，如 (1 + 1) * 2，运算符写在两个操作数中间；而后缀表达式（也称逆波兰式）把运算符放在操作数之后，如 1 1 + 2 *，两者完全等价。

后缀表达式最大的特点是：不需要括号。因为扫描到运算符时，它作用的对象就是“最近出现的两个操作数”，含义天然无歧义。这一特性使得后缀表达式非常适合用栈求值，也解释了为什么编译器内部常把中缀转成后缀再处理。

1.4 双栈求值流程

要在中缀表达式上直接求值，经典做法是“运算符优先级 + 双栈”：

• 开一个数字栈存操作数，一个符号栈存运算符；
• 在表达式头尾各加入一个特殊哨兵符号（如 #），并把它的优先级设为最低，目的是让扫描结束时能强制清空符号栈、让开头能统一处理；
• 遇到数字：直接压入数字栈；
• 遇到运算符：只要符号栈顶的优先级不低于当前运算符，就弹出数字栈顶两个数、弹出符号栈顶一个运算符，计算后把结果压回数字栈；重复这一步，直到栈顶优先级低于当前运算符，再把当前运算符入栈。

这里有一个细节必须强调：对于同优先级的连续运算（如 8-3-2 或 8/4/2），要按“栈顶优先级 ≥ 当前优先级就先算”处理，才能保证左结合的正确性，否则 8-3-2 会被错误地算成 8-(3-2)=7。

整个算法的直觉是：优先级高的运算“等不起”，必须先算；优先级低的运算先“压栈等待”，等右边的操作数齐了再回头算。理解了这一点，中缀转后缀和直接求值其实是同一套逻辑的两种输出形式。

二、数位求和：枚举 + 拆位

第二题要求统计某范围内满足“各位数字之和等于 15”的三位数个数。思路分两步：枚举和拆位。

2.1 枚举

数据范围只有三位数，直接从 100 枚举到 x，对每个数逐一判断即可。范围小的时候，“暴力枚举”不是偷懒，而是最稳妥的策略——代码短、不易错、边界好验证。

2.2 拆位

判断“各位数字之和”需要把每一位取出来。三位数可以直接硬拆：

int ans = 0;
for (int i = 100; i <= x; ++i) {
    // i % 10        -> 个位
    // i / 10 % 10   -> 十位（先除以10去掉个位，再对10取余）
    // i / 100       -> 百位（三位数直接除以100即可）
    if (i % 10 + i / 10 % 10 + i / 100 == 15)
        ans++;   // 满足条件，答案加一
}

这里依赖两个整型运算的性质：% 是取余；/ 在两个整数之间是整除（直接舍去小数部分），所以完全不用担心出现浮点数。

2.3 一般化拆位公式

如果想取第 j 位（从 0 开始计数，0 是个位），通用写法是：

int digit = i / (int)pow(10, j) % 10;

原理：先除以 10 的 j 次方，把第 j 位“降”到个位，再对 10 取余取出它。注意幂函数返回浮点数，需要强制转换成整型，避免浮点误差带来的边界问题；更稳妥的做法是自己写循环累乘 10 来代替。

三、九九乘法表：找规律 + 格式化输出

3.1 观察结构规律

打印乘法表的关键是先观察图形特征：

• 每行第一个乘数相同，第二个乘数从它开始递增到 9；
• 从第二行起，行首有一段固定宽度的空格需要补齐，用来“占住”被省略的算式位置。

3.2 双层循环骨架

for (int i = 1; i <= 9; ++i) {        // 枚举第一个乘数（行号）
    for (int j = 1; j < i; ++j)
        printf("        ");           // 补齐被跳过算式的占位空格
    for (int j = i; j <= 9; ++j) {
        printf("%dx%d=%2d  ", i, j, i * j);
    }
    printf("\n");                     // 每行结束换行
}

3.3 格式化输出的细节

对齐是本题最容易丢分的地方。printf 的格式控制可以帮我们省去手写对齐逻辑：

• %2d：输出整数，宽度不足两位时用空格在左侧补位；
• %02d：宽度不足两位时用 0 补位；
• 按上述格式输出后，每个算式占固定宽度（例如 8 个字符），因此第 i 行行首需要补 (i−1) × 8 个空格，才能保证上下两列严格对齐。

这类“算宽度”的题，建议先在纸上画出前两三行的样子，数清楚每个字段占几列，再动笔写代码，比反复提交试错高效得多。

四、二分查找：从升序模板到降序变体

4.1 二分的核心思想

二分查找利用数组的有序性，每次把搜索区间缩小一半，时间复杂度为 O(log n)。标准模板针对升序数组：

int lo = 0, hi = n - 1;
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;   // 防溢出写法
    if (a[mid] == target) return mid;
    else if (a[mid] < target) lo = mid + 1;  // 升序：目标在右半边
    else hi = mid - 1;
}
return -1;

4.2 降序数组的改法

本题数组是降序排列，此时“比中间元素大”意味着目标在右半边，比较方向恰好相反：

if (a[mid] == target) return mid;
else if (a[mid] > target) lo = mid + 1;  // 降序：大的在左，目标在右
else hi = mid - 1;

只需交换两个分支的移动方向，其余结构不变。这个练习的价值在于提醒我们：模板不是背下来的，而是理解“每一步为什么往这个方向收缩区间”之后推出来的。

4.3 两个易错点

• mid 的计算建议写成 lo + (hi - lo) / 2，避免 lo 与 hi 直接相加导致整型溢出；
• 区间开闭约定要自始至终一致（上面用的是闭区间 [lo, hi]），循环条件和边界更新必须配套，否则容易死循环或漏判。

另外，不少语言的标准库都提供了现成的有序查找接口，工程中可以直接使用；但作为初学者，手写一遍二分是理解“有序性如何被利用”的必经之路。

五、总结：四道题背后的通用方法论

把这四道题放在一起看，能提炼出几条对初学者普遍适用的经验：

1. 先补前置知识，再动笔：栈、整除与取余、格式化输出、二分思想，都是查一次资料就能补齐的“高性价比”知识点；
2. 小数据范围优先考虑枚举：能暴力就先暴力，正确性有了再谈优化；
3. 把问题拆成“结构规律 + 实现细节”两层：乘法表先找行列规律再处理对齐；表达式求值先想清楚优先级规则再写双栈；
4. 模板要理解着用：二分改降序只需换一个比较方向，说明真正要记的是不变量——“目标一定在当前区间内”，而不是代码本身。

编程入门阶段，“卡住”是常态。把每一道卡住的题彻底讲清楚——为什么这样想、为什么这样写、换个条件还成立吗——比囫囵吞枣刷十道题更有价值。坚持这种复盘方式，语法会内化成直觉，题目会变成套路，入门期自然会平稳度过。