The RPN expressions

a b + c *

and

f d e + *

are algebraically equivalent, though the names of the variables are different and the order of evaluation is slightly different. The expressions

a b * c +

a b * c *

though they have the same length and number of variables as the first expression, are not algebraically equivalent, i.e. in general

c (a + b) ≠ c + a * b
c (a + b) ≠ a * b * c

Without substituting values for any of the variables, is there a property that we could compute which is the same for a b + c * and f d e + * but not for a b + c * and a b * c + or a b * c *?

Assume the variables are real numbers, not e.g. matrices, so + and * are commutative, but - and ÷ are not.

This is a simple example of a broader question I am interested in: what are some properties that RPN expressions (i.e. unambiguous expression trees) have that are different for algebraically different expressions but do not change when the names or order of evaluation of the variables change?

This would be useful because it would be a kind of fingerprint for algebraic expressions that would not change merely because of choice of variable names.

I realize that this could be a big topic; references to sections of textbooks or research articles are welcome.

没有正确的解决方案

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top