给定一个字符串,如下所示
A + B * C / (D + E)
该算法会将字符串分解为二进制操作列表:
- 添加 D 和 E(结果 #1(
- 将 B 和 C 相乘(结果 #2( 将结果 #
- 1 除以结果 #2(结果 #3(
- 将结果 #3 添加到 A
基本上,像Java这样的编程语言执行表达式的顺序。
解决此类问题的最佳方法是什么?
">
最佳"方法在旁观者的眼中。一个相当常见且易于实现的方法是按照以下步骤构建一个简单的递归下降解析器:
- 编写一个"标记化"表达式的方法(即将其转换为运算符、操作数和括号的集合,例如
"A"
,"+"
,"B"
,"*"
,"C"
,"/"
,"("
,"D"
,"+"
,"E"
,")"
- 将处理顶级表达式的方法定义为零个或多个加法或减法序列
- 定义将加法或减法处理为零次或多次乘法或除法序列的方法
- 将乘法或除法处理为零个或多个主表达式序列的方法定义
- 定义用于将主表达式处理为变量或括在括号中的顶级表达式的方法
最后一点是理解递归下降分析的关键:每当遇到左括号时,都会回调用于处理顶级表达式的方法,然后验证处理后的下一个标记是否为右括号。