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

Question

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

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

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

Answer 1

评估函数值

为此你需要函数评估器引擎​​(编码并不难)如果你想支持 + ,- 操作!!!我所有的函数求值器都是这样工作的:

1. 编译函数源码

   首先创建支持的函数表(id、操作数的数量、名称、指向函数的指针)，如:

   +,-,*,/,sin,cos,....
   

   这些将是您需要评估的任何受支持表达式的构建 block 。不要忘记在代码中编写所有函数。处理方括号 (,) 也作为函数 (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
   

2. 编译后您需要解释字符串并评估它的值。

   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. 读取编译字符串的第一条记录

      如果它是值(数字、常量、变量)，则用它设置适当的 op? 值并增加操作数计数器 opn++。

      如果是函数集fx,fxn代码用它

   3. if 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 ...)

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