algorithm - 符号代数表达式的符号

Question

是否有任何算法可以找到“树 - 形式”中给出的任意符号代数表达式的符号？

我知道不存在通用算法，因为零识别问题对于任意表达式是不可判定的，但是我应该如何解决查找表达式符号的问题？（这是如何在计算机代数中完成的？）

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

score 0 · Accepted Answer

评估函数值

您需要函数评估器引擎（编码并不难）只有当您想支持 +,-操作时才能评估符号！我所有的函数评估器都是这样工作的：

编译函数的源文本

首先创建支持的函数表（id、操作数数量、名称、指向函数的指针），例如：
```
+,-,*,/,sin,cos,....
```
这些将是您需要评估的任何受支持表达式的构建块。不要忘记在您的代码中编写所有函数。处理括号(，)也作为函数 ( push,pop)。按操作数的数量对函数进行分组，因此+,-使用 1 和 2 个操作数（每个有两个不同的函数！！！）。

现在从表达式提取：
- 变量名
- 常量名称和值
- 数值
进入某种表格/列表：
```
variables[](id,name,value)
constants[](id,name,value)
numbers  [](id,    ,value)
```
现在终于构造编译的函数字符串。我的字符串是一组两个int。第一个是type（使用哪个表），第二个是id（表中的索引）。

例如表达式：
```
sign(sqrt(2)-1)
```
类型：
```
id type
0  function
1  number
2  constant
3  variable
```
功能：
```
id name   pointer
0  '('    ???
1  ')'    ???
2  '+'    ???
3  '-'    ???
4  '*'    ???
5  '/'    ???
6  'sqrt' ???
7  'sign' ???
```
没有变量或常量。数字是：
```
id value
0  2  
1  1
```
编译字符串：
```
type id
0    7   // sign(1 operand)
0    6   // sqrt(1 operand)
1    0   // 2
0    3   // - (2 operands)
1    1   // 1
```
编译后，您需要解释字符串并评估它的值。
1. 初始化变量
```
op1=0`,`op2=0, // set all operands to zero (number depends on supported functions usually 2)
opn=0          // actual operands number
fx=none        // actual function (for example none=-1)
fxn=0          // actual function operands number
```
2. 读取已编译字符串的第一条记录
  
  如果它是 value (number,constant,variable) 设置适当op?的值并增加操作数 counter opn++。
  
  如果它是功能集fx,fxn代码
3. 如果opn == fxn
  
  您达到了所需的操作数计数，因此执行函数fx并初始化下一个函数
```
op1=fxtab[fx].pointer(op1,op2,...)
fx=none,fxn=1
opn=1  (some spec functions can return more operands, then set op1,op2,.. opn=...)
```
4. 如果不是字符串结尾转到#2，但有下一个字符串记录
5. 最后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...）

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

algorithm - 符号代数表达式的符号

1 回答 1

Related

Reference