语法分析问题分类汇总

摘要: 语法分析题目汇总

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

本文总结了力扣上 2000 题以内的关于语法解析问题的 32 道题。将场景相同的放到了一起，场景上主要涉及嵌套列表解析、字符串解析、表达式解析、括号解析、计算式解析、化学式解析。算法上主要涉及DFS、递归下降、下推自动机，其中 DFS 是主流算法，递归下降和下推自动机比较偏，是计算机基础课编译原理的内容。

解决这类的问题一般的代码框架是先进行词法分析，然后进行语法分析，然后进行递归下降算法。

词法分析每次只需要改变正则表达式部分即可，语法分析代码只需要实现语法对应的函数。

递归下降分析法的原理是利用函数之间的递归调用模拟语法树自上而下的构造过程，相关理论知识参考编译原理中的语法分析部分。

括号解析

• 1087. 字母切换
• 1096. 花括号展开 II
• 856. 括号的分数
• 1021. 删除最外层的括号
• 1190. 反转每对括号间的子串
• 761. 特殊的二进制序列

计算式解析(计算器系列)

• 150. 逆波兰表达式求值 后缀表达式求值
• 282. 给表达式添加运算符
• 241. 为运算表达式设计优先级 分治 + 记忆化
• 224. 基本计算器
• 227. 基本计算器 II
• 772. 基本计算器 III
• 770. 基本计算器 IV

化学式解析

• 726. 原子的数量

表达式解析

• 439. 三元表达式解析器
• 385. 迷你语法分析器
• 736. Lisp 语法解析
• 722. 删除注释
• 254. 因子的组合
• 591. 标签验证器
• 1410. HTML 实体解析器
• 1106. 解析布尔表达式

字符串解析

• 394. 字符串解码
• 271. 字符串的编码与解码
• 471. 编码最短长度的字符串

嵌套列表解析

• 251. 展开二维向量

• 341. 扁平化嵌套列表迭代器

• 565. 数组嵌套

• 339. 嵌套列表权重和
• 364. 加权嵌套序列和 II

• 690. 员工的重要性

• 430. 扁平化多级双向链表

---