CODEWITHSUNDEEP
stringalgorithmparsing
John Henckel
John Henckel

Reputation: 11377

Algorithm to add implied parentheses in boolean expression

I have a string such as "A and B or not C and D". The atoms are all simple uppercase letters A,B,C... and the operators are only { and, or, not }. I would like to devise an algorithm that can add parentheses that are implied by the usual rules of precedence.

Can anyone think of a very simple way to do this? perhaps using Regex?

The desired output is "(A and B) or ((not C) and D)".

Upvotes: 0

Views: 845

Answers (2)

Juan Lopes
Juan Lopes

Reputation: 10575

It can be as simple as this (Python code ahead):

def popnext(stream, token):
    if stream[0:len(token)] == list(token):
        del stream[0:len(token)]
        return True
    return False

def parse_binary(stream, operator, nextfn):
    es = [nextfn(stream)]
    while popnext(stream, operator):
        es.append(nextfn(stream))
    return '(' + ' {} '.format(operator).join(es) + ')' if len(es) > 1 else es[0]

def parse_ors(stream):
    return parse_binary(stream, 'or', parse_ands)

def parse_ands(stream):
    return parse_binary(stream, 'and', parse_unary)

def parse_unary(stream):
    if popnext(stream, 'not'):
        return '(not {})'.format(parse_unary(stream))
    return parse_primary(stream)

def parse_primary(stream):
    if popnext(stream, '('):
        e = parse_ors(stream)
        popnext(stream, ')')
        return e
    return stream.pop(0)


def evaluate(expression):
    return parse_ors(list(expression.replace(' ', '')))[1:-1]

print evaluate('A and B or not C and D')
print evaluate('A and (B or not C) and D')

result:

(A and B) or ((not C) and D)
A and (B or (not C)) and D

Upvotes: 4

das-g
das-g

Reputation: 9994

A grammar for your these Strings might be defined by the following production rules:

  1. S → E
  2. E → EorE
  3. E → F
  4. F → FandF
  5. F → T
  6. F → notT
  7. T → A
  8. T → B
  9. T → C
  10. T → D

(Make rule 6 "T → not T"), if strings like "not not D and not not not B" shall be allowed, too.)

While this grammar is context free, it isn't regular. I don't think a regular grammar for your strings exists, so regular expressions are not sufficient to match exactly these strings, and by extension also not to parse and transform (re-write) them correctly.

Upvotes: 0

Related Questions