2

Let's suppose to have this sum of products boolean expresion in prefix form:

str_formula = 'Or(A, And(B, C, D), E, F, And(G, H))'

Or and And are the only operators permitted and there is no more nesting structure than the one representing above . I would like to rewrite the expression in order to receive the infix form.

My idea, without using regular expressions, was:

import ast
import re

or_op = ' OR '
and_op = ' AND '

str_formula = str_formula.replace('Or(', '[').replace('And(', '[').replace(')', ']')
s_list = re.sub('(\w+)', r"'\1'", str_formula)
list_formula = [x if isinstance(x, list) else [x] for x in ast.literal_eval(s_list)]

infix_form = or_op.join([and_op.join(sublist) for sublist in list_formula])

The infix_form variable is: 'A OR B AND C AND D OR E OR F OR G AND H'

Can you suggest a regex in order to solve in a smarter way this problem?

enneppi
  • 1,029
  • 2
  • 15
  • 33
  • Your infix form is wrong: parenthesis are missing. – Laurent LAPORTE Dec 24 '16 at 14:56
  • I think it's right. read my infix form as: A + BCD + E + F + GH. The AND operator has an high priority wrt OR – enneppi Dec 24 '16 at 15:03
  • If you want to support arbitrary nesting of `OR` and `AND` I don't think Pythons `re` is advanced enough to capture such constructs (they are not a *regular language*), and you'd be better of in a more advancing parsing solution. (see: [nested structures in Python](http://stackoverflow.com/questions/1099178/matching-nested-structures-with-regular-expressions-in-python)) – ᴘᴀɴᴀʏɪᴏᴛɪs Dec 24 '16 at 15:22
  • no nesting Or and And. The original formula is in the form A+B+...where A and B are in the form X * Y * Z (+ is or, * is and, as usual) – enneppi Dec 24 '16 at 15:26

1 Answers1

1

Consider the following approach using re.sub() function with replacement callback replaceOperands:

str_formula = 'Or(A, And(B, C, D), E, F, And(G, H))'

def replaceOperands(m):
    s = re.sub(r'\(|\)', '', m.group(2).replace(',', ' OR')) if m.group(1) == 'Or' else '('+m.group(2).replace(',', ' AND')+')'
    return s

str_formula = re.sub(r'\b(Or)\(([A-Z], (?:\(.*\))[A-Z]?)', 
                     replaceOperands, 
                     re.sub(r'\b(And)\(([^)]+)\)', replaceOperands, str_formula))
print(str_formula)

The output:

A OR B AND C AND D OR E OR F OR G AND H
RomanPerekhrest
  • 88,541
  • 4
  • 65
  • 105