Is there a way to autogenerate valid arithmetic expressions?

Question

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 1

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....