符号代数表达式的符号

Question

符号代数表达式的符号

algorithmalgebracomputer-algebra-systems

4

有没有一种算法可以在“树形结构”中给定任意符号代数表达式的符号？

我知道一般算法不存在，因为对于任意表达式，零识别问题是不可判定的，但是如何解决找到表达式符号的问题呢？（计算机代数中是如何做的？）

例如：sign(sqrt(2)-1) = ?

- Andrei Kh

当你说“代数”的时候，它是否包含未知数？ - Eric

不，它是没有变量的。另外，当我说“代数”的时候，我并不是指它只能包含代数数字。它也可以包含像log（2）或atan（2）这样的内容。但我不是在寻找一个通用算法。 - Andrei Kh

2

你应该使用足够精度来评估表达式。你可能需要使用任意精度算术包，或在其基础上使用区间算术。 - n. m.

我曾经考虑过这个问题，但是如果这个数字非常小以至于被计算机认定为数值“0”，会怎样呢？更大的问题是，对一个表达式进行精确计算需要花费时间（有时候是过多的时间）。 - Andrei Kh

有些问题在数值上很困难，你可能无法轻易地（如果你能的话）解决它们。如果数字非常接近于0，以至于差异可能小于机器精度，我认为可能没有解决方案。 - 3yakuya

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Spektre · Answer 1

计算函数值

你需要一个函数求值引擎（编写起来并不难），如果你想要支持加减运算，那么就没有办法仅仅计算符号！所有我的函数求值器都是这样工作的：

编译函数的源文本。首先创建支持函数表（id，操作数数量，名称，指向函数的指针），如下所示：

+，-，*，/，sin，cos等。

这些将是您需要评估的任何支持表达式的构建块。不要忘记在代码中编写所有函数。还要处理括号（push，pop）作为函数。按操作数数量对函数进行分组，因此+，-具有1个和2个操作数（每个都是两个不同的函数！！！）。

现在从表达式中提取以下内容：变量名称常量名称和值数字值

放入某种表/列表中：

variables[] (id, name, value) constants[] (id, name, value) numbers[] (id, value)

最后构建编译后的函数字符串。我的字符串由两个int组成。第一个是类型（要使用哪个表），第二个是id（在表中的索引）。

例如表达式：

sign(sqrt(2)-1)

类型： id 类型 0 函数 1 数字 2 常量 3 变量

函数： id 名称指针 0 '(' ??? 1 ')' ??? 2 '+' ??? 3 '-' ??? 4 '*' ??? 5 '/' ??? 6 'sqrt' ??? 7 'sign' ???

没有变量或常量。数字是：

id 值 0 2 1 1

编译后的字符串：

类型 id 0 7 // sign（1个操作数） 0 6 // sqrt（1个操作数） 1 0 // 2 0 3 // -（2个操作数） 1 1 // 1

编译后，您需要解释字符串并计算其值。

初始化变量 op1 = 0, op2 = 0，将所有操作数设置为零（数字取决于支持的函数通常为2） opn = 0 实际操作数数量 fx = none 实际函数（例如none = -1） fxn = 0 实际函数操作数数量

读取编译后字符串的第一条记录如果它是值（数字，常量，变量），则使用它设置适当的op? 值，并增加操作数计数器opn。如果它是函数，则设置fx，fxn代码。

如果opn == fxn 达到所需的操作数计数，因此执行函数fx并初始化下一个函数

op1 = fxtab[fx].pointer(op1, op2, ...) fx = none，fxn = 1 opn = 1 （某些特殊函数可能返回更多操作数，然后设置op1，op2，.. opn = ...）

如果未结束字符串，请转至#2，但使用下一个字符串记录

最后op1应该保存您的输出值。

一些示例函数（C++实现）：

double sign(double op1) 
 { 
 if (op1>0.0) return +1.0; 
 if (op1<0.0) return -1.0; 
 return 0.0; 
 }
double sqrt1(double op1) { return sqrt(op1); }
double plus1(double op1) { return op1; }
double minus1(double op1) { return -op1; }
double plus2(double op1,double op2) { return op1+op2; }
double minus2(double op1,double op2) { return op1-op2; }

[注]

您需要处理特殊情况，例如function = "";。此外，要注意空格、大小写敏感性，因为编译中的任何错误都会使结果无效。

速度不是一个大问题，这是解释-评估而不是数值解。所有操作都与您在纸上执行的操作相同次数。

您还应该处理数学错误（溢出、无效操作数、NaN、Inf等）

我通常将具有相同操作数的函数分组到自己的类型中以简化事情。