algorithm - 用函数解析表达式

Question

这是我的情况:输入是一个包含普通数学运算的字符串，如 5+3*4。函数也是可能的，即 min(5,A*2)。这个字符串已经被标记化了，现在我想使用堆栈来解析它(所以没有 AST)。我首先使用调车场算法，但这里出现了我的主要问题:

假设您有这个(标记化的)字符串:min(1,2,3,+)，这显然是无效语法。但是，SYA 将其转换为输出堆栈 1 2 3 + min(，希望您能看到问题的到来。从左到右解析时，它首先看到 + ，计算 2+3=5，然后计算 min(1,5)，结果为 1。因此，我的算法说这个表达式完全没问题，而它应该抛出语法错误(或类似的错误)。

防止此类事情发生的最佳方法是什么？添加一个特殊的分隔符(例如逗号)，使用不同的算法，还是什么？

Answer 1

为了防止出现此问题，您可能必须跟踪堆栈深度。我这样做的方式(我不确定这是“最佳”方式)是使用另一个堆栈。

新堆栈遵循以下规则:

• 当解析一个左括号、( 或函数时，压入一个 0。
  • 在嵌套函数的情况下执行此操作
• 当右括号 ) 被解析时，弹出最后一项并将其添加到堆栈中新的最后一个值。
  • 刚刚弹出的数字是函数返回了多少个值。您可能希望它始终为 1。
• 解析逗号或类似分隔符时，从堆栈中弹出，将该数字添加到新的最后一个元素，然后压入 0。
  • 重置以便我们可以开始验证函数的下一个参数
  • 刚刚弹出的值是语句返回了多少个值。您可能希望它始终为 1。
• 当一个数字被推送到输出时，递增这个堆栈的顶部元素。
  • 这是输出中可用值的数量。数字增加了值的数量。二元运算符需要至少有 2 个。
• 当一个二元运算符被推送到输出时，递减顶部元素
  • 二元运算符取 2 个值并输出 1，从而将输出中剩余的值总数减少 1。
  • 一般来说，一个 n 元运算符接受 n 值并返回 m 值应该添加 (m-n) 到顶部元素。
  • 如果此值变为负数，则抛出错误!

这会发现您示例中的最后一个参数(仅包含一个 +)会将堆栈顶部递减为 -1，并自动抛出错误。

但是你可能会注意到你的例子中的最后一个参数，比如 3+ 会返回一个零，这不是负数。在这种情况下，您会在“您可能希望它始终为 1”的步骤之一中抛出错误。