简化表达树 [英] Simplifying expression trees

问题描述

我正在尝试编写一个简化数学表达式的程序.

I am trying to write a program that simplifies mathematical expressions.

我已经写了一个将字符串转换为二叉树的解析器.例如(1 + 2)* x将变为

I have already written a parser that converts a string to a binary tree. For example (1+2)*x will become

    *
   / \
  +   x
 / \
1   2

我简化此类树的想法如下:您存储了一组树及其简化版本例如

The idea I had of simplifying such trees is as follows: You store a set of trees and their simplified version For example

    *                       +
   / \                     / \
  a   +        and        *   *
     / \                 / \ / \
    b   c               a  b a  c

(其中a，b，c可以是任何子树)然后，如果找到与存储的树之一匹配的子树，我将将其替换为简化版本.

(Where a,b,c can be any subtree) Then, If I find a subtree that matches one of the stored trees, I will replace it with its simplified version.

如有必要，我将重复此过程，直到树完全简化为止.

If necessary I will repeat the process until the tree is fully simplified.

这种方法的问题在于它不能组合类似术语".在某些情况下.例如，如果我尝试存储树:

The problem with this approach is that it can't "combine like terms" in some cases. For example, if I try to store the tree:

      +                *
     / \      and     / \
    x   x            2   x

然后，当我尝试使用以下树简化表达式x + y + x时:

Then when I try to simplify the expression x+y+x, with the following tree:

    +
   / \
  x   +
     / \
    y   x  

由于子树，它不会简化为2x + y

It will not be simplified to 2x+y, because the subtree

      +     
     / \     
    x   x      

它不包含在树中，因此不会简化树.

Is not contained in the tree, thus the tree will not be simplified.

我尝试编写一种将类似术语组合在一起的显式算法，但是太多了需要考虑的情况.

I tried writing an explicit algorithm that combine like terms but there are too many cases to consider.

有人可以帮我找到解决这个问题的方法吗?

Can anyone please help me find a solution to this problem?

推荐答案

这是计算机代数系统中使用的基本思想之一.

Here is one of the basic ideas which is used in computer algebra systems.

对于 Plus (+)和 Times (*)之类的运算符，您可以定义诸如 Flat (

For operators like Plus (+) and Times (*) you can define attributes like Flat (associativity) and Orderless (commutativity). Also don't define Plus and Times as "binary" operators but as "multiple-argument" operators.

所以输入如下:

Plus(x,Plus(y,x))

第一步，由于 Flat 的属性

Plus(x,y,x)

下一步，由于 Orderless 属性的作用，可以对其进行转换(排序)

in the next step it can be transformed (sorted) because of the Orderless attribute to

Plus(x,x,y)

在您的评估"中，步骤您现在可以遍历参数并简化"(例如)表达式为:

In your "evaluation" step you can now go through the arguments and "simplify" the expression to:

Plus(Times(2,x),y)

该方法的优点在于，结构相等"的表达式可以被替换.它们以相同的规范形式"存储.并且例如可以相对于对象相等"更容易地进行比较.用所用的编程语言.

This approach has the advantage that expressions which are "structural equal" are stored in the same "canonical form" and could for example easier compared for "object equality" in the used programming language.

这篇关于简化表达树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！