logic - 动态条件逻辑函数

Question

我需要编写一个可以在运行时接受 if 语句的函数(例如，用户输入，或来自数据文件)。理想情况下，它应该能够求解不低于以下复杂度的表达式:

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

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

由于上述示例的复杂性，该函数不仅需要遍历各个条件，还需要了解运算符，了解评估它们的顺序，并最好优先考虑它们的速度(例如，在示例中，如果 a 为 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从输入队列中读取 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是表达式的最终值

如果您的所有运算符都是左结合的且未使用任何函数，则此简化算法应该有效。请注意，不需要递归，因为我们使用自己的堆栈实现。有关示例和更多信息，请参阅 Rosetta Code on Shunting-yard和 Rosetta Code on RPN