时间戳

首页 > 解决方案 > 如何以编程方式获得公式的派生形式？

algorithm - 如何以编程方式获得公式的派生形式？

问题描述

例如，如果我有 I = V / R 作为输入，我希望 V = I * R 和 R = V / I 作为输出。我知道这可能是一个广泛的问题，但我应该如何开始呢？我应该在构建后缀符号/解释器时使用堆栈/树吗？

标签： algorithmparsingtreestack

解决方案

您需要能够以符号方式表示公式，并应用代数规则来操作这些公式。

最简单的方法是定义一个接受公式的语法；最好明确定义为 BNF。有了它，您可以为此类公式构建解析器；适当地完成您的解析器可以构建表示公式的抽象语法树。您可以使用 lex 和 yacc 或 ANTLR 等工具。以下是我对如何使用自定义递归下降解析器执行此操作的建议：是否有可用于 8 位嵌入式系统的 flex/bison 替代方案？.

一旦有了对公式进行编码的树，您就可以实施根据代数定律修改树的过程，例如：

 X=Y/Z => X*Z = Y if Z ~= 0

现在您可以通过编写爬过树的过程代码来实现这样的规则，找到与模式的匹配，然后破坏树以产生结果。这是非常简单的编译器技术。如果您有热情，您可能可以相当快地编写半打代数定律。您会发现执行此操作的代码非常糟糕，爬上爬下树、匹配节点以及破坏节点之间的链接以产生结果。

另一种方法是使用程序转换系统，它可以让你

  • 直接为您的公式定义语法，
  • 根据您的语法直接定义（树）重写规则（例如，基本上您直接提供上面的代数规则），
  • 按需为您应用重写规则
  • 从 AST 重新生成符号公式

我公司的DMS Software Reengineering Toolkit可以做到这一点。您可以在由转换规则定义的代数中看到代数和微积分的完整示例（此处无法复制）

推荐阅读