确定表达式中的哪些变量不必确定答案的算法

Question

我正在处理一个遍历决策树的项目。决策树中的每个节点都有一个可以包含多个变量并且相当复杂的公式。应用程序要求用户逐个输入变量的值。应用程序的

两个条件：

1. 应用程序必须要求用户回答变量，它们出现在表达式中的顺序。
2. 应用程序必须跳过任何不需要的变量来确定答案。

If语句的格式为：

if(expression;pass;fail) 

例如，考虑以下表达式：

if((a=1&b=1)|(c=1&d=1&e=1)|f=1;1;2) 

如果我们已经知道，a = 1且B = 1，则我们知道答案是1，而不管c，d，e和f的值如何。所以没有必要要求用户输入这些变量的值。

这些表达式可能相当复杂，包含多个比较运算符和嵌入的ifs。例如：

if(a>1;if(b<5;1;if(c=2;2;0));if(d!=2;if(e=1;1;if(f=2;2;0));0)) 

我有一个可怕的时间想出一个算法来有效地做到这一点。是否有一个现有算法来决定哪些变量在给定表达式中无关紧要？或者也许只是一种新的思维方式，可以帮助我解决这个问题？

Answer 1

如何构建语法树？

正如你可以看到，作为解决面值数字被认为。每当用户给变量赋值时，对应的叶节点就会解析为该值。然后遍历树解析值直到没有更多节点可以解析。如果你到达根节点，那么你可以确定答案。

编辑：甲if(e1;e2;e3)表达式可表示为一个三元操作符节点（具有三个子节点）。如果e1已解析为true和e2至某值v，则此表达式解析为v。 e1=false的情况也是如此。