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

Question

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

申请的两个要求是:

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

如果语句的格式是:

if(expression;pass;fail)

例如，考虑以下表达式:

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

如果我们已经知道 a=1 和 b=1，那么无论 c、d、e 和 f 的值如何，我们都知道答案将为 1。因此无需要求用户输入这些变量的值。

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

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 的情况也是如此。