算法創建隨機的，但有效的數學表達式

-1

爲了產生大量的測試數據的表達式解析器（基於Dijkstra的調車場），我想出了以下Python腳本：算法創建隨機的，但有效的數學表達式

#!/usr/bin/python 

import ast 
import sys 
import random 
import operator as op 

def gen_digit(n): 

    i = 0 
    digit = "" 

    if random.randint(0, 1e06) % 17 == 0: 
     digit = digit + "-" 

    while i < n: 
     if i == 0: 
      digit = digit + str(random.randint(1, 9)) 
     else: 
      digit = digit + str(random.randint(0, 9)) 

     i = i + 1 

    return digit; 

def rnd_op(): 
    ops = [ "+", "-", "*", "/", "%" ] 
    return ops[random.randint(0, 4)] 

operators = {ast.Add: op.add, ast.Sub: op.sub, ast.Mult: op.mul, 
     ast.Div: op.truediv, ast.Mod: op.mod, ast.USub: op.neg} 

def eval_(node): 
    if isinstance(node, ast.Num): 
     return node.n 
    elif isinstance(node, ast.BinOp): 
     return operators[type(node.op)](eval_(node.left), eval_(node.right)) 
    elif isinstance(node, ast.UnaryOp): 
     return operators[type(node.op)](eval_(node.operand)) 
    else: 
     raise TypeError(node) 

def eval_expr(expr): 
    return eval_(ast.parse(expr, mode='eval').body) 

def right_op(op, expr): 

    if op == "/" or op == "%": 

     try: 
      v = eval_expr(expr) 
     except ZeroDivisionError: 
      v = 0 

     if v == 0: 
      return op + " (" + expr + " + " + gen_digit(random.randint(1, 4)) + ")" 
     else: 
      return op + " " + expr 

    else: 
     return op + " " + expr 

def gen_term(): 

    term = "" 

    if random.randint(0, 1e06) % 17 == 0: 
     term += "-" 

    term += "(" + right_op(gen_digit(random.randint(1, 4)), \ 
      right_op(rnd_op() + " " + gen_digit(random.randint(1, 4)), \ 
      rnd_op() + " " + gen_digit(random.randint(1, 4)))) + ")" 

    return term 

def build_expr(): 
    return "(" + gen_term() + " " + \ 
     right_op(rnd_op(), gen_term()) + " " + \ 
     right_op(rnd_op(), gen_term()) + ")" 

def rnd_expr(expr, m, d): 

    if d < m: 
     expr = "(" + build_expr() + " " + \ 
       right_op(rnd_op(), rnd_expr(expr, m, d + 1)) + " " + \ 
       right_op(rnd_op(), build_expr()) + ")" 

    return expr 

argc = len(sys.argv) 

if argc > 1: 

    dpth = int(sys.argv[1]); 
    sys.setrecursionlimit(dpth * 10) 
    print (rnd_expr(build_expr(), dpth, 0)) 

else: 
    print (rnd_expr(build_expr(), 1, 0))

我調車場執行（另一個C++項目）是否正確，並接受四個基本算術運算符加％（模）。

我想讓生成的表達式有效，但目前我遇到了劃分/模以零錯誤，儘管我試圖使它們無效。此外，在大於98的遞歸深度上溢出ast。

編輯：的師/模數由零錯誤Python腳本內發生，而是通過與像bc上的Linux外部工具解析。

有人有一個想法，爲什麼函數right_op或算法有時會失敗。

來源

2016-02-13 Heiko Schäfer

我的說法50嘗試過1000次，但沒有零錯誤（寡婦7個python 3.5.1）獲得的劃分。也許你可以提供一個random.seed來重現錯誤。 – miracle173

通過一個外部工具，如'bc'（* Linux *的命令行計算器），可以檢測到零除。我不會這樣做的問題。 –

我可以使用主項目中的工具，如果表達式是錯誤的，那麼它的退出碼爲1，所以我在* bash * shell中用：while（./ rnd_expr.py 40 | expr2cf）對其進行了測試。確實如此; done' –

其實Python腳本正在做它專門做的事情：生成有效的測試數據！

如果更改

def rnd_op(): 
    ops = [ "+", "-", "*", "/", "%" ] 
    return ops[random.randint(0, 4)]

到

def rnd_op(): 
    ops = [ "+", "-", "*", "/", "%" ] 
    return ops[random.randint(0, 3)]

即省略模運算%的創造，不是在bash外殼下面的一行會證明這一點正確的：

while(./rnd_expr.py 4 | perl -e 'my $exp = <STDIN>; if(!defined(eval($exp))) { print [email protected]" ".$exp; exit(1) } else { print eval($exp)."\n"; exit(0); }'); do true; done

而沒有變化它會抱怨模零。用bc重新檢查顯示相同的結果。

我的主要C++項目大多接受表達式，而perl和bc大多都會拒絕它。所以我在我的主要C++項目中有一個（可能）優先錯誤。

編輯：兩個是正確的，perl/bc和我的主要C++項目。第一個解釋結果爲integer並截斷中間結果，而我的主要C++項目正在計算符號（即帶有分數類）。

的另一種證明，即rubberduck調試實際工作:)

來源

2016-02-13 14:06:20

算法創建隨機的，但有效的數學表達式

回答

相關問題