4
\$\begingroup\$

I am currently working on a function that should return true or false based on a condition written in string by a user. The condition will look something like this:

((dog OR cat) AND *Horse*)

The () grouping objects and *word* making the search case insensitive.

How I approached the problem was to have a string that would replace the words by True or False and then simply do an eval() of the new string, giving us the final result.

For example ((dog OR cat) AND *Horse*) would become ((True or False) and True) if applied to the sentence "My dog is not a horse, obviously",

What I don't like about my code it is that it looks really messy, is there a better way to do this task?

import re
def text2cond(text, condition):
    """Will transform a string into a condition usable by tweet_filter"""
    # We will need to give modularity to this
    s = ""
    for token in condition.split():
        regex = None
        if token.startswith('('):
            open_par = 0
            case_sens = False
            for char in token:
                if char == "(":
                    open_par = open_par + 1
                elif char == "*":
                    case_sens = True
            if case_sens:
                regex = r"\b" + re.escape(token[open_par+1:-1]) + "\\b"
                if re.search(regex, text, re.IGNORECASE):
                    s= s + ("("*open_par + "True ")
                else:
                    s= s + ("("*open_par + "False ")
            else:
                regex = r"\b" + re.escape(token[open_par:]) + "\\b"
                if re.search(regex, text):
                    s= s + ("("*open_par + "True ")
                else:
                    s= s + ("("*open_par + "False ")
        elif token.endswith(')') and not token.startswith("*"):
            close_par = 0
            for char in token:
                if char == ")":
                    close_par = close_par + 1
            regex = r"\b" + re.escape(token[:-close_par]) + "\\b"
            if re.search(regex, text):
                s= s + ("True" + ")"*close_par + " ")
            else:
                s= s + ("False" + ")"*close_par + " ")
        elif token.lower() == "or":
            s= s + ("or ")
        elif token.lower() == "and":
            s= s + ("and ")
        elif token.lower() == "not":
            s= s + ("not ")
        elif token.startswith('*'):
            close_par = 0
            for char in token:
                if char == ")":
                    close_par = close_par + 1
            regex = r"\b" + re.escape(token[1:-1-close_par]) + "\\b"
            if re.search(regex, text, re.IGNORECASE):
                s= s + ("True" + close_par*")")
            else:
                s= s + ("False" + close_par*")")
    return s

_condition = "((dog OR cat) AND *Horse*)"
_text = "My dog is obviously not a horse"

print(text2cond(_text, _condition))
print(eval(text2cond(_text, _condition)))
\$\endgroup\$
  • 1
    \$\begingroup\$ I corrected everything, now it works but as said previously I find this way of doing really bad looking and was wondering if there was a way to do it more elegantly. \$\endgroup\$ – Axel Uran Jul 18 '17 at 10:00
  • \$\begingroup\$ Doing eval() is considered bad practice \$\endgroup\$ – Ludisposed Jul 18 '17 at 10:15
  • \$\begingroup\$ @Ludisposed Answers in answer boxes please. Also Python itself uses exec, there's a time and a place for eval. \$\endgroup\$ – Peilonrayz Jul 18 '17 at 10:27
  • \$\begingroup\$ I don't fully understand why using eval() would be bad practice, the goal is to tell me if the condition is overall True or False. I come from a neuroscience background so I'm sorry if it was obvious. \$\endgroup\$ – Axel Uran Jul 18 '17 at 10:34
  • 1
    \$\begingroup\$ Thank you Axel Uran, I've retracted my close vote. And notified chat it's working. I hope you get a good answer. :) \$\endgroup\$ – Peilonrayz Jul 18 '17 at 10:56
5
\$\begingroup\$

1. Difficulties

The approach taken in the post is to use string operations to transform the input into a Python expression and then evaluate the result.

The trouble with this approach is that the string comes from a user, who may not enter exactly what you expect. So handling of erroneous input is vital. For example, suppose I want to know if text contains "dog". The first thing I would try is dog:

>>> eval(text2cond(_text, 'dog'))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<string>", line 0

    ^
SyntaxError: unexpected EOF while parsing

Ok, maybe I need parentheses? What about (dog):

>>> eval(text2cond(_text, '(dog)'))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<string>", line 1
    (False 
          ^
SyntaxError: unexpected EOF while parsing

Ok, I suppose I have to use an operator too? I'll try (dog OR dog):

>>> eval(text2cond(_text, '(dog OR dog)'))
True

Suppose that I want case-insensitive matching of two words? I might try *(dog AND horse)*:

>>> eval(text2cond(_text, '*(dog AND horse)*'))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<string>", line 1, in <module>
NameError: name 'Falseand' is not defined

Ok, maybe I need more parentheses? What about (*(dog AND horse)*):

>>> eval(text2cond(_text, '(*(dog AND horse)*)'))
False

Which is misleading — what I should have written is (*dog* AND *horse*):

>>> eval(text2cond(_text, '(*dog* AND *horse*)'))
True

I think that users will find this behaviour hard to cope with. Of course you can go through the code and try to fix up these cases as users discover them. But how can you be sure you have caught everything? And even if you've caught all the cases, the SyntaxError that you get if the user makes a mistake are not likely to be very friendly.

>>> eval(text2cond(_text, '(dog AND horse OR cat)'))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<string>", line 1
    (True and or False) 
               ^
SyntaxError: invalid syntax

The other problem is that using eval on text that comes from the user is risky — if you didn't manage to completely sanitize the input, then the user may be able to run arbitrary code.

2. The standard approach

The standard approach to this kind of problem is parsing. The idea is to break down the problem into three processing stages:

  1. Tokenization. In this stage the input string is turned into a sequence of tokens (pieces which can't be further broken down). For example, given this input:

    ((dog OR cat) AND *Horse*)
    

    the tokenizer might emit this sequence of tokens:

    '(', '(', 'dog', 'OR', 'cat', ')', 'AND', '*', 'Horse', '*', ')', '<end of input>'
    
  2. Parsing. In this stage the sequence of tokens is turned into a parse tree, a data structure corresponding to the syntactic structure of the input. For example, given the input above, the parser might construct the following data structure:

    BinOp(
        left=BinOp(
            left='dog',
            op='OR',
            right='cat'),
        op='AND',
        right=IgnoreCase(
            body='Horse'))
    
  3. Evaluation. This is easy to do by a depth-first pass over the parse tree.

There are several good reasons to solve the problem using this approach:

  1. It's the standard approach, so other programmers will easily understand how it works.

  2. It's efficient: each stage needs to pass over its input exactly once.

  3. Splitting the work into steps with clearly defined inputs and outputs makes it easier to test.

  4. The approach extends to more complicated applications, such as interpretation of programming languages.

3. Tokenization

In Python an easy way to tokenize a string is to use the finditer method on regular expressions. A little bit of care has to be taken to avoid gaps between tokens (other than whitespace, which you are allowing). This is done by having a "catch-all" alternative (\S) which matches any non-whitespace character that doesn't belong to a valid token.

import re

# Regular expression matching a token (group 1) or an error (group 2).
_TOKEN_RE = re.compile(r'\s*(?:([()*]|\w+\b)|(\S))')

# Token representing the end of the input.
TOKEN_END = '<end of input>'

def tokenize_condition(s):
    """Generate the tokens in the condition s.

    >>> list(tokenize_condition("((dog OR cat) AND *Horse*)"))
    ['(', '(', 'dog', 'OR', 'cat', ')', 'AND', '*', 'Horse', '*', ')', '<end of input>']

    """
    for match in _TOKEN_RE.finditer(s):
        token, error = match.groups()
        if error:
            raise SyntaxError("unexpected character {!r}".format(error))
        yield token
    yield TOKEN_END

4. Parsing

(In this section I'm using a simplified version of your language, lacking the NOT operator.)

First, we'll need a data structure to represent the parse tree. Here I'm going to use collections.namedtuple:

from collections import namedtuple

# Binary operation with left operand, operator and right operand.
BinOp = namedtuple('BinOp', 'left op right')

# Ignore case when matching against body.
IgnoreCase = namedtuple('IgnoreCase', 'body')

A word to be matched like dog will be represented by a string.

Second, the parser. There are lots of different techniques for writing parsers. I could use a parser generator like pyparsing, that constructs the parser from a representation of a formal grammar, but I think it's more illustrative to write a recursive descent parser by hand.

def parse_condition(tokens):
    """Parse a condition given by an iterator of tokens, and return a
    parse tree.

    >>> tokens = tokenize_condition("((dog OR cat) AND *Horse*)")
    >>> parse_condition(tokens)
    BinOp(left=BinOp(left='dog', op='OR', right='cat'), op='AND', right=IgnoreCase(body='Horse'))

    """
    token = next(tokens)           # The current token.

    def error(expected):
        # Current token failed to match, so raise syntax error.
        raise SyntaxError("Expected {} but found {!r}"
                          .format(expected, token))

    def match(*valid_tokens):
        # If the current token is found in valid_tokens, consume it
        # and return True. Otherwise, return False.
        nonlocal token
        if token in valid_tokens:
            token = next(tokens)
            return True
        else:
            return False

    def term():
        # term ::= ( binop ) | * binop * | WORD
        if match('('):
            tree = binop()
            if match(')'):
                return tree
            else:
                error("')'")
        elif match('*'):
            tree = binop()
            if match('*'):
                return IgnoreCase(tree)
            else:
                error("'*'")
        elif token in (')', 'AND', 'OR'):
            error("term")
        else:
            t = token
            match(token)
            return t

    def binop():
        # binop ::= term | term OR term | term AND term
        left = term()
        op = token
        if match('AND', 'OR'):
            right = term()
            return BinOp(left, op, right)
        else:
            return left

    tree = binop()
    if token != TOKEN_END:
        error("end of input")
    return tree

5. Evaluation

I'll leave the details of evaluating of the parse tree as an exercise. What we want is something like this:

def evaluate_condition(text, tree, ignorecase=False):
    """Return true if the expression given by the parse tree matches the text.

    >>> tokens = tokenize_condition("((dog OR cat) AND *Horse*)")
    >>> tree = parse_condition(tokens)
    >>> evaluate_condition("horse", tree)
    False
    >>> evaluate_condition("cat on a horse", tree)
    True
    >>> evaluate_condition("horse with a dog", tree)
    True

    """
    if isinstance(tree, str):
        # search for tree in text, ignoring case if ignorecase=True
    elif isinstance(tree, BinOp):
        # evalute tree.left (and maybe tree.right) recursively; apply op
    elif isinstance(tree, IgnoreCase):
        # evaluate tree.body, passing ignorecase=True
    else:
        # raise an error

6. Conclusion

The code here is substantially longer than the code in the post, but has these advantages:

  1. It handles the difficult examples I gave in section 1.
  2. It generates reasonable (if not great) syntax error messages.
  3. Because you are in charge of generating the error messages (rather than delegating them to Python) you can improve them if you need to.
  4. It is straightforward to extend this to handle more syntax features (such as the NOT operator).
  5. You can start to think about how to improve the performance, for example if your have a node in the parse tree of the form BinOp(left=word1, op='OR', right=word2) then you could evaluate this in just one pass over the text instead of two. This kind of transformation is much easier to do here when you have a parse tree to work on.
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.