Edwin Edwin - 1 month ago 8
Python Question

Is there a way to autogenerate valid arithmetic expressions?

I'm currently trying to create a Python script that will autogenerate space-delimited arithmetic expressions which are valid. However, I get sample output that looks like this:

( 32 - 42 / 95 + 24 ( ) ( 53 ) + ) 21


While the empty parentheses are perfectly OK by me, I can't use this autogenerated expression in calculations since there's no operator between the 24 and the 53, and the + before the 21 at the end has no second argument.

What I want to know is, is there a way to account for/fix these errors using a Pythonic solution? (And before anyone points it out, I'll be the first to acknowledge that the code I posted below is probably the worst code I've pushed and conforms to...well, very few of Python's core tenets.)

import random
parentheses = ['(',')']
ops = ['+','-','*','/'] + parentheses

lines = 0

while lines < 1000:
fname = open('test.txt','a')
expr = []
numExpr = lines
if (numExpr % 2 == 0):
numExpr += 1
isDiv = False # Boolean var, makes sure there's no Div by 0

# isNumber, isParentheses, isOp determine whether next element is a number, parentheses, or operator, respectively
isNumber = random.randint(0,1) == 0 # determines whether to start sequence with number or parentheses
isParentheses = not isNumber
isOp = False
# Counts parentheses to ensure parentheses are matching
numParentheses = 0
while (numExpr > 0 or numParentheses > 0):
if (numExpr < 0 and numParentheses > 0):
isDiv = False
expr.append(')')
numParentheses -= 1
elif (isOp and numParentheses > 0):
rand = random.randint(0,5)
expr.append(ops[rand])
isDiv = (rand == 3) # True if div op was just appended
# Checks to see if ')' was appended
if (rand == 5):
isNumber = False
isOp = True
numParentheses -= 1
# Checks to see if '(' was appended
elif (rand == 4):
isNumber = True
isOp = False
numParentheses += 1
# All other operations go here
else:
isNumber = True
isOp = False
# Didn't add parentheses possibility here in case expression in parentheses somehow reaches 0
elif (isNumber and isDiv):
expr.append(str(random.randint(1,100)))
isDiv = False
isNumber = False
isOp = True
# If a number's up, decides whether to append parentheses or a number
elif (isNumber):
rand = random.randint(0,1)
if (rand == 0):
expr.append(str(random.randint(0,100)))
isNumber = False
isOp = True
elif (rand == 1):
if (numParentheses == 0):
expr.append('(')
numParentheses += 1
else:
rand = random.randint(0,1)
expr.append(parentheses[rand])
if rand == 0:
numParentheses += 1
else:
numParentheses -= 1
isDiv = False
numExpr -= 1

fname.write(' '.join(expr) + '\n')
fname.close()
lines += 1

Answer

Yes, you can generate random arithmetic expressions in a Pythonic way. You need to change your approach, though. Don't try to generate a string and count parens. Instead generate a random expression tree, then output that.

By an expression tree, I mean an instance of a class called, say, Expression with subclasses Number, PlusExpression,MinusExpression, 'TimesExpression, DivideExpression, and ParenthesizedExpression. Each of these, except Number will have fields of type Expression. Give each a suitable __str__ method. Generate some random expression objects and just print the "root."

Can you take it from here or would you like me to code it up?

ADDENDUM: Some sample starter code. Doesn't generate random expressions (yet?) but this can be added....

# This is just the very beginning of a script that can be used to process
# arithmetic expressions.  At the moment it just defines a few classes
# and prints a couple example expressions.

# Possible additions include methods to evaluate expressions and generate
# some random expressions.

class Expression:
    pass

class Number(Expression):
    def __init__(self, num):
        self.num = num

    def __str__(self):
        return str(self.num)

class BinaryExpression(Expression):
    def __init__(self, left, op, right):
        self.left = left
        self.op = op
        self.right = right

    def __str__(self):
        return str(self.left) + " " + self.op + " "  + str(self.right)

class ParenthesizedExpression(Expression):
    def __init__(self, exp):
        self.exp = exp

    def __str__(self):
        return "(" + str(self.exp) + ")"

e1 = Number(5)
print e1

e2 = BinaryExpression(Number(8), "+", ParenthesizedExpression(BinaryExpression(Number(7), "*", e1)))
print e2

** ADDENDUM 2 **

Getting back into Python is really fun. I couldn't resist implementing the random expression generator. It is built on the code above. SORRY ABOUT THE HARDCODING!!

from random import random, randint, choice

def randomExpression(prob):
    p = random()
    if p > prob:
        return Number(randint(1, 100))
    elif randint(0, 1) == 0:
        return ParenthesizedExpression(randomExpression(prob / 1.2))
    else:
        left = randomExpression(prob / 1.2)
        op = choice(["+", "-", "*", "/"])
        right = randomExpression(prob / 1.2)
        return BinaryExpression(left, op, right)

for i in range(10):
    print(randomExpression(1))

Here is the output I got:

(23)
86 + 84 + 87 / (96 - 46) / 59
((((49)))) + ((46))
76 + 18 + 4 - (98) - 7 / 15
(((73)))
(55) - (54) * 55 + 92 - 13 - ((36))
(78) - (7 / 56 * 33)
(81) - 18 * (((8)) * 59 - 14)
(((89)))
(59)

Ain't tooooo pretty. I think it puts out too many parents. Maybe change the probability of choosing between parenthesized expressions and binary expressions might work well....

Comments