Day 2 讲义：表达式解析、栈、括号序列与溢出处理

今天的主线是：字符串一旦有嵌套、分段或格式规则，就不要只靠一个计数器乱扫。先找出结构，再维护对应状态。

学习顺序：先回答“当前字符会改变什么状态”，再决定用栈、数组还是指针。每段扫描结束时，都要明确“何时结算”。

1. 栈：保存还没有结束的结构

栈是后进先出（LIFO）：最后打开的结构，必须最先结束。

([{}])
  { } 先配对
 [   ] 再配对
(     ) 最后配对

因此，多种括号的标准规则是：

左括号：入栈。
右括号：必须与栈顶左括号匹配，然后弹栈。
结束时：栈必须为空。

1.1 单种括号与多种括号的区别

只有 (、) 时，可用余额 bal：

'(' -> bal++
')' -> bal--
任意时刻 bal < 0：右括号没有可匹配的左括号
最后 bal != 0：还有左括号未关闭

但多种括号不能只数数量。例如 ([)] 中，左右括号数量都对，顺序却错了。此时必须保存类型，使用栈。

1.2 最小模板：判断合法括号序列

#include<bits/stdc++.h>
using namespace std;

bool match(char l, char r){
    return (l == '(' && r == ')') ||
           (l == '[' && r == ']') ||
           (l == '{' && r == '}') ||
           (l == '<' && r == '>');
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;
    stack<char> st;

    for(char c: s){
        if(c == '(' || c == '[' || c == '{' || c == '<'){
            st.push(c);
        }else{
            if(st.empty() || !match(st.top(), c)){
                cout << "NO\n";
                return 0;
            }
            st.pop();
        }
    }

    cout << (st.empty() ? "YES" : "NO") << '\n';
    return 0;
}

复杂度： O(n)，每个字符最多入栈、出栈一次。

1.3 612C：类型错可以替换，结构错不能补救

612C 允许把一个右括号替换成另一种右括号，求最少替换次数。

扫描时：

1. 遇左括号，入栈；
2. 遇右括号，若栈空，说明前面没有左括号可以匹配，直接无解；
3. 栈不空时，弹出一个左括号；若类型不配对，答案加一，因为把当前右括号改成正确类型即可；
4. 扫描结束后，栈非空说明左括号太多，无法靠替换解决，无解。

关键区别：

类型不对：可以替换右括号。
位置不对：没有左括号可配，不能替换出一个过去的左括号。

2. 位置栈：匹配后得到一个合法区间

223A 不只要求判断合法，还要求找到某类合法括号子串。此时栈中不要只存字符，改存下标。

当 s[i] 与栈顶 s[top] 匹配时：

[top, i] 是一个完整的合法括号区间。

如果题目还要求统计区间内 [ 的数量，可以先预处理：

pre[i] = 前 i 个字符中 '[' 的个数。

那么区间 [l,r] 内的 [ 数量是：

pre[r] - pre[l-1]

2.1 手动理解

s = [([])]

扫描到最后一个 ] 时，能从栈里找到与它匹配的最左位置。此时不要重新扫描整段，只要用前缀和立刻得到该区间里 [ 的个数。

这是一种常见组合：

栈负责找边界；前缀和负责统计边界内的贡献。

3. 倍数栈：模拟嵌套循环

1175B 的程序由 for x、add、end 构成。每层循环都会让内部的 add 被执行更多次。

设：

st.top() = 当前位置的一次 add 会给总答案增加多少

初始没有循环，因此：

st.push(1);

操作规则：

3.1 为什么必须截断

题目上限是 2^32-1。如果先让 long long 无限制相乘，深层循环仍可能溢出。

解决办法：定义一个更大的安全哨兵：

const long long LIM = (1LL << 32);

任何倍数或答案达到 LIM，都只记录为 LIM。之后不必知道真实值，因为最终一定输出 OVERFLOW!!!。

3.2 参考代码

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    const long long LIM = (1LL << 32);
    stack<long long> st;
    st.push(1);
    long long ans = 0;

    while(n--){
        string op;
        cin >> op;

        if(op == "for"){
            long long x;
            cin >> x;
            st.push(min(LIM, st.top() * x));
        }else if(op == "add"){
            ans = min(LIM, ans + st.top());
        }else{
            st.pop();
        }
    }

    if(ans >= LIM) cout << "OVERFLOW!!!\n";
    else cout << ans << '\n';
    return 0;
}

复杂度： O(n)。

4. 解析题：先切字段，再处理字段

解析题最常见的错误，是一边扫描一边急着拼答案，结果边界全乱。推荐统一流程：

字符流 -> 字段 -> 数值或区间 -> 排序/合并/输出

4.1 34C：页码压缩

输入是逗号分隔的页码，可能有重复且无序。目标是把连续页码压成区间。

步骤：

1. 扫描字符串，读出所有整数；
2. 排序、去重；
3. 用两个指针维护当前连续段 [l,r]；
4. 下一个数不是 r+1 时，输出当前段并开始新段。

1,2,3,5,7,8,10
-> 1-3,5,7-8,10

关键结算条件：

if(a[i] != a[i - 1] + 1){
    // 上一段在 i-1 结束，先输出它
}

4.2 727B：金额字段

这类题要先明确：哪些字符属于数字、逗号或句点到底是分隔符还是小数点、末尾数字什么时候结算。

通用扫描骨架：

long long cur = 0;
bool inNumber = false;

for(char c: s){
    if(isdigit(c)){
        cur = cur * 10 + (c - '0');
        inNumber = true;
    }else{
        if(inNumber){
            // 结算 cur
            cur = 0;
            inNumber = false;
        }
    }
}
if(inNumber){
    // 别忘了结算最后一个字段
}

题面如果把小数部分按两位处理，可以统一换算为“分”再相加，避免浮点数误差。

4.3 41C：构造前先判断格式

邮箱还原题不是“试很多字符串”，而是先找固定标记（如 @、dot），再判断每一段是否仍然合法。

构造题的习惯：

先列出合法串必须满足的条件；
再枚举少量可能的切分点；
每个切分点只做 O(n) 校验。

不要在递归或回溯里枚举所有分割方式，绝大多数格式题只需要枚举很少的关键位置。

5. 今日易错点

6. 训练与复盘

建议顺序：612C -> 1175B -> 223A -> 34C -> 727B -> 41C。

每题完成后写下：

题目：
结构：嵌套、分段还是格式？
维护状态：
什么时候结算或匹配：
复杂度：
最容易错的边界：

7. 今日口诀

嵌套结构想到栈，右边一定看栈顶。
匹配位置能定区间，区间统计交给前缀和。
循环层数乘倍数，超上限就提前截断。
解析字符串先分段，分隔和结尾都结算。