logic - 动态条件逻辑函数

Question

我需要编写一个可以在运行时使用 if 语句的函数（例如，用户输入或来自数据文件）。理想情况下，它应该能够解决不比以下复杂的表达式：

a && ( b || !c || ( d && e ) )

我想我需要的是一个递归函数（一个调用自己的函数）。当然，该函数需要返回true或false。

由于上述示例的复杂性，该函数不仅需要遍历各个条件，还需要了解运算符，知道评估它们的顺序，并优先考虑它们的速度（例如，在示例中，如果为假，则无需评估语句的其余部分）。

有没有人有任何想法？

Answer 1

一种解决方案是使用分流码算法将表达式转换为 RPN，然后将其评估为 RPN（因为 RPN 比中缀更容易评估）。第一部分，转换为 RPN（伪代码）：

while (tokens left) {
  t = read_token();
  if (t is number) {
    output(t);
  } else if (t is unary operator) {
    push(t);
  } else if (t is binary operator) {
    r = pop();
    if (r is operator and precedence(t)<=precedence(r)) {
       output(r);
    } else {
       push(r);
    }
    push(t);
  } else if (t is left parenthesis) {
    push(t);
  } else if (r is right parenthesis) {
    while ((r = pop()) is not left parenthesis) {
        output(r);
        if (stack is empty) {
          mismatched parenthesis!
        }
    }
    if (top() is unary operator) {
        output(pop());
    }
  }
}
while (stack is not empty) {
  if (top() is parenthesis) {
     mismatched parenthesis!
  }
  output(pop());
}

• read_token从输入队列中读取一个令牌
• output将值插入输出队列
• push将一个值推入堆栈（您只需要一个）
• pop从堆栈中弹出一个值
• top在不弹出的情况下查看堆栈顶部的值

RPN 评估更简单：

while (tokens left) {
  t = read_token();
  if (t is number) {
    push(t);
  } else if (t is unary operator) {
    push(eval(t, pop()));
  } else if (t is binary operator) {
    val1 = pop();
    val2 = pop();
    push(eval(t, val1, val2));
  }
}
result = pop();

• read_token()从上一步生成的 RPN 队列中读取值
• eval(t, val)t用操作数计算一元运算符val
• eval(t, val1, val2)t使用操作数计算二元运算符val1和val2
• result是表达式的最终值

如果您的所有运算符都是左关联的并且没有使用任何函数，那么这个简化的算法应该可以工作。请注意，不需要递归，因为我们使用自己的堆栈实现。有关示例和更多信息，请参阅调车场上的罗塞塔代码和RPN 上的罗塞塔代码