时间戳

首页 > 解决方案 > 用函数解析表达式

algorithm - 用函数解析表达式

问题描述

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

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

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

标签： algorithmfunctionparsingexpression

解决方案

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

新堆栈遵循以下规则：

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

这将发现您的示例中的最后一个参数（仅包含 a +）会将堆栈顶部递减为-1，从而自动引发错误。

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

推荐阅读