動態條件邏輯函數

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讀取從輸入隊列令牌
• 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