创建随机但有效的数学表达式的算法

Question

为了为表达式解析器生成大量测试数据（基于 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++ 项目）是正确的，接受四个基本算术运算符加上 %（取模）.

我想让生成的表达式有效，但目前我有时会遇到 division/modulo 零错误 ，尽管我试图避免它们。此外 ast 在大于 98.

的递归深度上溢出

编辑： division/modulo 由零错误 发生不在 Python 内脚本，但通过在 Linux.

上使用 bc 等外部工具进行解析

有人知道为什么函数 right_op 或算法通常有时会失败吗？

Answer 1

实际上 Python 脚本 正在做它专做的事情：生成有效的测试数据！

如果你改变

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

至

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

即省略 模运算符 % 的创建，而不是在 bash shell 中遵循 one-liner将证明它是正确的：

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

而没有变化它会抱怨以零为模。使用 bc 重新检查显示相同的结果。

我的主要 C++ 项目大多接受表达式，而 perl 和 bc 大多总是拒绝它。所以我的主要 C++ 项目中有一个（可能）优先级错误。

编辑： 两个都是正确的，perl/bc和我的主要C++项目。第一个是将结果解释为 integer 并截断中间结果，而我的主要 C++ 项目正在计算 符号（即分数 class）.

另一个证明，rubberduck 调试 确实有效:)

创建随机但有效的数学表达式的算法

Algorithm to create random, but valid mathematical expressions

python

algorithm

arithmetic-expressions