【GESP】C++三级、四级练习 luogu-P1597 语句解析-系列题目4

一、前文回顾

已完成的工作：

• 【GESP】C++三级练习 luogu-P1597 语句解析-系列题目1
• 【GESP】C++三级、四级练习 luogu-P1597 语句解析-系列题目2
• 【GESP】C++三级、四级练习 luogu-P1597 语句解析-系列题目3

截至目前，我们在完成P1597题目本身要求的基础上，又拓展支持了以下情况：

• 变量仍然只有3个a、b、c
• 变量值可以是多位整数（int范围内）或者变量名
• 支持更多的变量名，且变量名的长度可以是多位。

上次留的作业是：

利用std::map和std::unordered_map，来改进我们的实现代码，让孩子真正熟悉、掌握该数据结构。

针对上述问题，实现代码应如何调整？今天分享下我和孩子的“答卷”。

---

二、原题回顾(luogu-P1597 语句解析)

2.1 题目要求

2.1.1 题目描述

一串长度不超过 $255$ 的 PASCAL 语言代码，只有 $a,b,c$ 三个变量，而且只有赋值语句，赋值只能是一个一位的数字或一个变量，每条赋值语句的格式是 [变量]:=[变量或一位整数];。未赋值的变量值为 $0$ 输出 $a,b,c$ 的值。

2.1.2 输入格式

一串符合语法的 PASCAL 语言，只有 $a,b,c$ 三个变量，而且只有赋值语句，赋值只能是一个一位的数字或一个变量，未赋值的变量值为 $0$。

2.1.3 输出格式

输出 $a,b,c$ 最终的值。

2.2 输入输出样例 #1

2.2.1 输入 #1

a:=3;b:=4;c:=5;

2.2.2 输出 #1

3 4 5

2.3 说明/提示

输入的 PASCAL 语言长度不超过 $255$。

---

三、本次题目分析

首先简要介绍下本次题目重点要使用和掌握的的map和unordered_map数据结构。

3.1 map和unordered_map数据结构简介

3.1.1 std::map

功能:

• 以 键值对 (key-value) 形式存储数据。
• key 唯一（不能重复），会自动按照 < 比较结果排序。
• 支持根据 key 快速查找、插入、删除。
• 提供有序遍历（中序遍历，升序）。
• 提供范围操作：
  • lower_bound(key)：返回第一个大于等于指定key的迭代器，调用方式: map.lower_bound(key)，
  • upper_bound(key)：返回第一个大于指定key的迭代器，调用方式: map.upper_bound(key)，
  • equal_range(key)：返回一个pair，包含等于指定key的范围（即上述两个迭代器），调用方式: map.equal_range(key)，

特性：

• 底层实现：红黑树（平衡二叉搜索树）。
• 时间复杂度：
  • 查找、插入、删除：$O(\log n)$。
  • 遍历：$O(n)$，且有序。
• 迭代器：双向迭代器（bidirectional iterator）。
• 适合场景：需要 顺序存储、范围查询、稳定性能。

---

3.1.2 std::unordered_map

功能:

• 以 键值对 (key-value) 形式存储数据。
• key 唯一（不能重复）。
• 查找、插入、删除比 map 更快（均摊 $O(1)$）。
• 遍历元素时 无序，顺序不可预测。
• 不支持 lower_bound、upper_bound 这种范围操作。

特性：

• 底层实现：哈希表。
• 时间复杂度：
  • 平均情况：查找、插入、删除 $O(1)$。
  • 最坏情况（哈希冲突严重）：$O(n)$。
• 迭代器：前向迭代器（forward iterator）。
• 适合场景：需要 高性能查找/插入，不关心顺序。

---

3.1.3 对比总结表

特性	map（有序映射）	unordered_map（无序映射）
底层结构	红黑树（平衡二叉搜索树）	哈希表
key 排序	自动升序排序	无序
查找复杂度	$O(\log n)$	平均 $O(1)$，最坏 $O(n)$
插入/删除复杂度	$O(\log n)$	平均 $O(1)$，最坏 $O(n)$
迭代器类型	双向迭代器	前向迭代器
是否支持范围查询	✅ 支持	❌ 不支持
遍历顺序	有序	无序（不可预测）
内存开销	较小	较大（因为哈希表需要空间）

---

3.2 map和unordered_map使用方式简介

3.2.1 std::map 使用示例

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> mp;

    // 1. 插入元素
    mp[3] = "C";                   // 用下标插入，如果 key=3 不存在，会新建并赋值
    mp.insert({1, "A"});           // insert 插入
    mp.insert(std::make_pair(2,"B"));

    // 2. 遍历元素（有序，按 key 从小到大）
    std::cout << "map（有序）：\n";
    for (auto &p : mp) {
        std::cout << p.first << " -> " << p.second << "\n";
    }

    // 3. 查找元素
    // ❌ mp[2] = ... 如果 key=2 不存在，会自动插入一个空 value
    // ✅ 用 find 查找更安全
    auto it = mp.find(2);
    if (it != mp.end()) {
        std::cout << "找到 key=2，value=" << it->second << "\n";
    }

    // 4. 删除元素
    mp.erase(3);
    std::cout << "删除 key=3 后，map 大小: " << mp.size() << "\n\n";
}

输出:

map（有序）：
1 -> A
2 -> B
3 -> C
找到 key=2，value=B
删除 key=3 后，map 大小: 2

---

3.2.2 std::unordered_map 使用示例

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> ump;

    // 1. 插入元素
    ump[3] = "C";   // 下标插入
    ump.insert({1, "A"});           // 使用初始化列表插入
    ump.insert(std::make_pair(2, "B")); // 使用make_pair插入

    // 2. 遍历元素（无序，顺序不可预测）
    std::cout << "unordered_map（无序）：\n";
    for (auto &p : ump) {
        std::cout << p.first << " -> " << p.second << "\n";
    }

    // 3. 查找元素
    auto it = ump.find(2);
    if (it != ump.end()) {
        std::cout << "找到 key=2，value=" << it->second << "\n";
    }

    // 4. 删除元素
    ump.erase(3);
    std::cout << "删除 key=3 后，unordered_map 大小: " << ump.size() << "\n";
}

输出:（顺序可能不同）

unordered_map（无序）：
2 -> B
1 -> A
3 -> C
找到 key=2，value=B
删除 key=3 后，unordered_map 大小: 2

---

注意：为什么查找时建议用 find() 而不是 operator[]？

• map[key] 或 unordered_map[key]：
  • 如果 key 存在 → 返回对应 value 的引用。
  • 如果 key 不存在 → 会 自动插入一个新元素（value 是默认构造的值，如 "" 或 0）。
  • 这在查询时可能导致 误插入数据，破坏原有逻辑。
• find(key)：
  • 如果 key 存在 → 返回指向该元素的迭代器。
  • 如果 key 不存在 → 返回 end()，不会插入新元素。
  • 查找时 安全，不会改变容器。

---

3.3 本题思路改造思路介绍

将承载的数据结构从数组改成map/unordered_map后，代码的主要调整逻辑如下：

3.3.1 数据结构定义的变化

// 定义全局变量map，用于存储变量名和对应的值
std::map<std::string, std::string> v_map;

3.3.2 变量查找函数的简化

std::string find_v_value(std::string v_name) {
    if (v_map.find(v_name) == v_map.end()) {
        return "0";
    }
    return v_map[v_name];
}

3.3.3 变量赋值函数的简化

void set_v_value(std::string v_name, std::string v_val) {
    v_map[v_name] = v_val;
}

3.3.4 变量输出函数的变化

void print_v_values(std::string v_name = "") {
    if (v_name.empty()) {
        // 如果未指定变量名，打印所有变量的值
        for (auto it = v_map.begin(); it != v_map.end(); it++) {
            std::cout << it->second << " ";
        }
    } else {
        // 打印指定变量的值
        std::cout << v_map[v_name] << " ";
    }
}

3.3.5 主函数中索引管理的简化

int main() {
    // ...
    int v_name_idx = 0;  // 变量名位置
    int val_idx = 0;     // 变量值位置
    // 不再需要数组索引
    
    // 解析所有赋值语句
    while (v_name_idx < str.length() && val_idx < str.length()) {
        // ...
        set_v_value(v_name, v_val); // 不需要传递数组索引
        // ...
    }
    // ...
}

3.4 本题主要改进点总结

1. 数据结构简化：从两个平行数组改为单一的键值对容器，更符合问题本质
2. 查找效率提升：
   • 数组实现：$O(n)$线性查找
   • map实现：$O(\log n)$查找
   • unordered_map实现：平均$O(1)$查找
3. 代码简洁性：
   • 不再需要手动管理数组索引
   • 变量查找和赋值操作大幅简化
   • 不需要手动检查变量是否存在
4. 内存管理：
   • 数组实现：固定大小（30个变量），可能浪费空间
   • map/unordered_map实现：动态分配，按需使用内存
5. 功能扩展：
   • 理论上支持无限多的变量（受内存限制）
   • 不需要修改代码即可支持更多变量

总的来说，使用map/unordered_map不仅简化了代码实现，还提高了程序的效率和可扩展性，是一次很好的代码优化。

---

3.5 示例代码

3.5.1 map 示例代码

#include <cctype>
#include <iostream>
#include <string>
#include <map>

// 定义全局变量map，用于存储变量名和对应的值
std::map<std::string, std::string> v_map;

/**
 * 查找变量的值
 * @param v_name 变量名
 * @return 如果变量存在返回其值，否则返回"0"
 */
std::string find_v_value(std::string v_name) {
    if (v_map.find(v_name) == v_map.end()) {
        return "0";
    }
    return v_map[v_name];
}

/**
 * 从字符串中获取等号右边的数值
 * @param str 输入的PASCAL代码字符串
 * @param start 等号的位置
 * @return 等号右边的数值
 */
std::string get_value(std::string str, int& start) {
    // 从start位置开始查找分号的位置
    int end = (int)str.find(';', start);
    // 截取等号到分号之间的子串并转换为整数返回
    std::string r_val = str.substr(start, end - start);
    start = end;
    // 如果是数字直接返回，否则查找变量值
    if (isdigit(r_val[0])) {
        return r_val;
    } else {
        return find_v_value(r_val);
    }
}

/**
 * 获取变量名
 * @param str 输入的PASCAL代码字符串
 * @param start 开始位置
 * @return 变量名
 */
std::string get_v_name(std::string str, int& start) {
    // 查找冒号位置
    int end = (int)str.find(':', start);
    // 截取变量名
    std::string result = str.substr(start, end - start);
    start = end;
    return result;
}

/**
 * 设置变量值
 * @param v_name 变量名
 * @param v_val 变量值
 */
void set_v_value(std::string v_name, std::string v_val) {
    v_map[v_name] = v_val;
}

/**
 * 打印变量值
 * @param v_name 变量名，默认为空字符串
 */
void print_v_values(std::string v_name = "") {
    if (v_name.empty()) {
        // 如果未指定变量名，打印所有变量的值
        for (auto it = v_map.begin(); it != v_map.end(); it++) {
            std::cout << it->second << " ";
        }
    } else {
        // 打印指定变量的值
        std::cout << v_map[v_name] << " ";
    }
}

int main() {
    // 读取输入字符串
    std::string str;
    std::cin >> str;
    
    // 定义变量名和值的索引
    int v_name_idx = 0;
    int val_idx = 0;
    
    // 解析输入字符串
    while (v_name_idx < str.length() && val_idx < str.length()) {
        // 获取变量名
        std::string v_name = get_v_name(str, v_name_idx);
        // 跳过":="
        val_idx = v_name_idx + 2;
        // 获取变量值
        std::string v_val = get_value(str, val_idx);
        // 设置变量值
        set_v_value(v_name, v_val);
        // 移动到下一个语句
        v_name_idx = val_idx + 1;
    }
    
    // 打印所有变量的值, 利用map的有序性
    print_v_values();
    return 0;
}

3.5.2 unordered_map 示例代码

#include <cctype>
#include <iostream>
#include <string>
#include <unordered_map>

// 定义全局变量map，用于存储变量名和对应的值
std::unordered_map<std::string, std::string> v_map;

/**
 * 查找变量的值
 * @param v_name 变量名
 * @return 如果变量存在返回其值，否则返回"0"
 */
std::string find_v_value(std::string v_name) {
    // 如果变量不存在，返回默认值"0"
    if (v_map.find(v_name) == v_map.end()) {
        return "0";
    }
    // 返回变量对应的值
    return v_map[v_name];
}

/**
 * 从字符串中获取等号右边的数值
 * @param str 输入的PASCAL代码字符串
 * @param start 等号的位置
 * @return 等号右边的数值
 */
std::string get_value(std::string str, int& start) {
    // 从start位置开始查找分号的位置
    int end = (int)str.find(';', start);
    // 截取等号到分号之间的子串并转换为整数返回
    std::string r_val = str.substr(start, end - start);
    start = end;
    // 如果是数字直接返回，否则查找变量值
    if (isdigit(r_val[0])) {
        return r_val;
    } else {
        return find_v_value(r_val);
    }
}

/**
 * 获取变量名
 * @param str 输入的PASCAL代码字符串
 * @param start 开始位置
 * @return 变量名
 */
std::string get_v_name(std::string str, int& start) {
    // 查找冒号位置
    int end = (int)str.find(':', start);
    // 截取变量名部分
    std::string result = str.substr(start, end - start);
    start = end;
    return result;
}

/**
 * 设置变量值
 * @param v_name 变量名
 * @param v_val 变量值
 */
void set_v_value(std::string v_name, std::string v_val) {
    // 将变量名和值存入map中
    v_map[v_name] = v_val;
}

/**
 * 打印变量值
 * @param v_name 变量名，默认为空字符串
 */
void print_v_values(std::string v_name = "") {
    if (v_name.empty()) {
        // 如果未指定变量名，打印所有变量的值
        for (auto it = v_map.begin(); it != v_map.end(); it++) {
            std::cout << it->second << " ";
        }
    } else {
        // 打印指定变量的值
        std::cout << v_map[v_name] << " ";
    }
}

int main() {
    // 读取输入字符串
    std::string str;
    std::cin >> str;
    
    // 定义变量名和值的索引
    int v_name_idx = 0;
    int val_idx = 0;
    
    // 解析输入字符串
    while (v_name_idx < str.length() && val_idx < str.length()) {
        // 获取变量名
        std::string v_name = get_v_name(str, v_name_idx);
        // 跳过":="
        val_idx = v_name_idx + 2;
        // 获取变量值
        std::string v_val = get_value(str, val_idx);
        // 设置变量值
        set_v_value(v_name, v_val);
        // 移动到下一个语句
        v_name_idx = val_idx + 1;
    }
    
    // 按顺序打印a、b、c的值
    print_v_values("a");
    print_v_values("b");
    print_v_values("c");
    return 0;
}

两种实现其实本质只是替换了使用的数据结果，其他代码逻辑都是一样的。只是在输出的时候，为了通过原题P1597的检查，需要按照变量名的顺序输出，而std::map是有序的，所以直接输出即可。而std::unordered_map是无序的，所以需要先排序，再输出。

---

四、系列总结

至此，我们已经原题从只支持a、b、c三个变量且值只支持1位数字，拓展成了：

• 变量值可以是 多位整数（int范围内） 或者变量名
• 支持多个、多字符变量名，如a1、b2、c3等，不再局限于a、b、c三个变量

并在这个过程中，我们也学习了:

• C++标准库中的std::map和std::unordered_map两个关联容器的使用。
• 函数化模块化的编程思想
• 函数参数引用传递的使用

一道题涉及的覆盖三级到四级的考纲内容，甚至七级考纲的unordered_map哈希表等内容。掌握此系列编程题目的学习方法和知识内容，对于孩子编程能力的提升是大有裨益的。一起继续加油吧。

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

“luogu-”系列题目可在洛谷题库进行在线评测。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号