Boolean expression parser

Question

I was trying to write some of the Haskell list functions into Java, and I realized that one of the key strengths for many of the functions was the ability to pass in a boolean expression. I decided to write a parser to facilitate this. It has worked perfectly as far as I have tested it, but I want to know just how [in]efficiently I've done this, and if there's anything key that I missed.

A few rules for using this parser:

• You cannot use the ! operator in an expression [yet].
• For comparison of strings, use ==, !=, etc...
• For exponentiation, use ^.
• PEMDAS ("order of operations") is followed for mathematical expressions.

Otherwise, expressions can be written almost exactly like a normal if statement. For example:

Halo.takeWhile("[x]>=2", someArray);

As a direct call to the parser:

ExpressionParser.evaluate("2+[x] == [y] && (1==1 && Joe==Joe && 3^2>10)", "x", 5, "y", 7);

---

class ExpressionParser
{
    private static final String[] operators = { "!=", "==", ">=", "<=", ">", "<", "||", "&&", "*", "/", "+", "-", "^" };

    private static boolean parseAndEvaluateExpression(String ex)
    {
            for (char c : ex.toCharArray())
            {
                    if (!Character.isSpaceChar(c))
                            return parseWithStrings(ex);
            }
            System.err.println("ERROR: Expression cannot be empty!");
            return false;
    }

    @SafeVarargs
    static <T> boolean evaluate(String or, T... rep)
    {
            String[] temp = new String[rep.length];
            for (int i = 0; i < rep.length; i++)
                    temp[i] = "" + rep[i];
            return evaluate(or, temp);
    }

    static boolean evaluate(String or, String... vars)
    {
            if ((vars.length % 2 == 1 || vars.length < 2) && vars.length != 0)
            {
                    System.err.println("ERROR: Invalid arguments!");
                    return false;
            }
            for (int i = 0; i < vars.length; i += 2)
                    or = or.replace("[" + vars[i] + "]", "" + vars[i + 1]);
            return parseAndEvaluateExpression(or);
    }

    private static boolean parseWithStrings(String s)
    {
            int[] op = determineOperatorPrecedenceAndLocation(s);
            int start = op[0];
            String left = s.substring(0, start).trim();
            String right = s.substring(op[1]).trim();
            String oper = s.substring(start, op[1]).trim();
            int logType = logicalOperatorType(oper);
            System.out.println("PARSE: Left: \"" + left + "\" Right: \"" + right + "\" Operator: \"" + oper + "\"");
            if (logType == 0) // encounters OR- recurse
                    return parseWithStrings(left) || parseWithStrings(right);
            else if (logType == 1) // encounters AND- recurse
                    return parseWithStrings(left) && parseWithStrings(right);
            if (containsMathematicalOperator(left)) // evaluate mathematical expression
                    left = "" + parseMathematicalExpression(left);
            if (containsMathematicalOperator(right))// see above
                    right = "" + parseMathematicalExpression(right);
            String leftSansParen = removeParens(left);
            String rightSansParen = removeParens(right);
            if (isInt(leftSansParen) && isInt(rightSansParen))
                    return evaluate(Double.parseDouble(leftSansParen), oper, Double.parseDouble(rightSansParen));
            else
                    return evaluate(leftSansParen, oper, rightSansParen); // assume they are strings
    }

    private static int[] determineOperatorPrecedenceAndLocation(String s)
    {
            s = s.trim();
            int minParens = Integer.MAX_VALUE;
            int[] currentMin = null;
            for (int sampSize = 1; sampSize <= 2; sampSize++)
            {
                    for (int locInStr = 0; locInStr < (s.length() + 1) - sampSize; locInStr++)
                    {
                            int endIndex = locInStr + sampSize;
                            String sub;
                            if ((endIndex < s.length()) && s.charAt(endIndex) == '=')
                                    sub = s.substring(locInStr, ++endIndex).trim();
                            else
                                    sub = s.substring(locInStr, endIndex).trim();
                            if (isOperator(sub))
                            {
                                    // Idea here is to weight logical operators so that they will still be selected over other operators
                                    // when no parens are present
                                    int parens = (logicalOperatorType(sub) > -1) ? parens(s, locInStr) - 1 : parens(s, locInStr);
                                    if (containsMathematicalOperator(sub))
                                    {
                                            // Order of operations weighting
                                            switch (sub)
                                            {
                                            case "^":
                                            case "/":
                                            case "*":
                                                    parens++;
                                                    break;
                                            case "+":
                                            case "-":
                                                    break;
                                            }
                                    }
                                    if (parens <= minParens)
                                    {
                                            minParens = parens;
                                            currentMin = new int[] { locInStr, endIndex, parens };
                                    }
                            }
                    }
            }
            return currentMin;
    }

    private static int logicalOperatorType(String op)
    {
            switch (op.trim())
            {
            case "||":
                    return 0;
            case "&&":
                    return 1;
            default:
                    return -1;
            }
    }

    private static boolean containsMathematicalOperator(String s)
    {
            s = s.trim();
            for (char c : s.toCharArray())
                    if (c == '/' || c == '+' || c == '*' || c == '-' || c == '^')
                            return true;
            return false;
    }

    private static int parens(String s, int loc)
    {
            int parens = 0;
            for (int i = 0; i < s.length(); i++)
            {
                    if (s.charAt(i) == '(' && i < loc)
                            parens++;
                    if (s.charAt(i) == ')' && i >= loc)
                            parens++;
            }
            return parens;
    }

    private static String removeParens(String s)
    {
            s = s.trim();
            String keep = "";
            for (char c : s.toCharArray())
            {
                    if (!(c == '(') && !(c == ')'))
                            keep += c;
            }
            return keep.trim();
    }

    private static boolean isOperator(String op)
    {
            op = op.trim();
            for (String s : operators)
            {
                    if (s.equals(op))
                            return true;
            }
            return false;
    }

    private static boolean isInt(String s)
    {
            for (char c : s.toCharArray())
                    if (!Character.isDigit(c) && c != '.')
                            return false;
            return true;
    }

    private static boolean evaluate(double left, String op, double right)
    {
            switch (op)
            {
            case "==":
                    return left == right;
            case ">":
                    return left > right;
            case "<":
                    return left < right;
            case "<=":
                    return left <= right;
            case ">=":
                    return left >= right;
            case "!=":
                    return left != right;
            default:
                    System.err.println("ERROR: Operator type not recognized.");
                    return false;
            }
    }

    private static double parseMathematicalExpression(String s)
    {
            int[] op = determineOperatorPrecedenceAndLocation(s);
            int start = op[0];
            String left = s.substring(0, start).trim();
            String right = s.substring(op[1]).trim();
            String oper = s.substring(start, op[1]).trim();
            System.out.println("MATH:  Left: \"" + left + "\" Right: \"" + right + "\" Operator: \"" + oper + "\"");
            if (containsMathematicalOperator(left))
                    left = "" + parseMathematicalExpression(left);
            if (containsMathematicalOperator(right))
                    right = "" + parseMathematicalExpression(right);
            return evaluateSingleMathematicalExpression(Double.parseDouble(removeParens(left)), oper,
                            Double.parseDouble(removeParens(right)));
    }

    private static double evaluateSingleMathematicalExpression(double result1, String oper, double result2)
    {
            switch (oper)
            {
            case "*":
                    return result1 * result2;
            case "/":
                    return result1 / result2;
            case "-":
                    return result1 - result2;
            case "+":
                    return result1 + result2;
            case "^":
                    return Math.pow(result1, result2);
            default:
                    System.err.println("MATH ERROR: Mismatched Input.");
                    return 0;
            }
    }

    private static boolean evaluate(String left, String op, String right)
    {
            switch (op)
            {
            case "==":
                    return left.equals(right);
            case "!=":
                    return !left.equals(right);
            default:
                    System.err.println("ERROR: Operator type not recognized.");
                    return false;
            }
    }
}

Answer 1

You've written something quite impressive there, but it is an unorthodox approach and some of the code is rather impenetrable. I've laid out a few points of issue and in some cases possible solutions and comments below.

Method documentation

Your methods could stand to have a brief JavaDoc block at the top. Here's how you might annotate what I believe to be your simplest method, isInt:

/**
 * Determines whether a given string consists only of digits.
 *
 * @param s The string to test.
 * @return True if the string consists only of digits; false otherwise.
 */
private static boolean isInt(String s)
{
    for (char c : s.toCharArray())
        if (!Character.isDigit(c) && c != '.')
            return false;
    return true;
}

(By the way, Character.isDigit('.') == false, so you don't need that && c != '.' bit in there.)

Proper typing of arguments

I notice you provide arguments with a sort of “key, value, key, value” style and explicitly check to make sure that format is followed. I suppose that works, but you could be more semantic and get more out of the type system by using a Map from variable names to values.

Non-usage of exceptions

You've got a lot of error cases:

System.err.println("ERROR: Expression cannot be empty!");
System.err.println("ERROR: Invalid arguments!");
System.out.println("PARSE: Left: \"" + left + "\" Right: \"" + right + "\" Operator: \"" + oper + "\"");
System.err.println("ERROR: Operator type not recognized.");
System.out.println("MATH:  Left: \"" + left + "\" Right: \"" + right + "\" Operator: \"" + oper + "\"");
System.err.println("MATH ERROR: Mismatched Input.");
System.err.println("ERROR: Operator type not recognized.");

Printing them out to standard error (or standard output, without rhyme or reason) may be suitable for debugging, but it is not appropriate beyond that. Java has a method of dealing with errors: exceptions. Use them; they won't bite.

Inefficient concatenation

In removeParens (and possibly elsewhere), you're repeatedly concatenating strings using +. This is fine for one-offs, or where the number of operands are constant, as Java can optimize it. However, doing it repeatedly in a loop is inefficient. You'd be better off using a StringBuilder:

private static String removeParens(String s)
{
    s = s.trim();
    StringBuilder keep = new StringBuilder();
    for (char c : s.toCharArray())
    {
        if (!(c == '(') && !(c == ')'))
            keep.append(c);
    }
    return keep.toString().trim();
}

Also realize you can change that if condition to c != '(' && c != ')'. You may also want to consider initializing the StringBuilder to s and deleting the parentheses. Also keep in mind that the first s = s.trim() is not necessary given the trim at the end.

parens

This could be clarified with more documentation as recommended at the top, but it seems to me like it's supposed to determine (twice?) the nesting level of parentheses at a particular location in the string. I'm worried there's a bug with closing parentheses before the location or opening parentheses after. Consider the following situation, where ^ is the location in question.

( ( ) ( ) ( ) )
       ^

At that ^ point, there are two levels of nesting of parentheses. parens will return 6, counting these:

( ( ) ( ) ( ) )
^ ^   ^ ^   ^ ^

I think you probably want a result of 4 instead, ignoring the paired parentheses.

( ( ) ( ) ( ) )
  ~~~     ~~~   <- irrelevant to middle pair, but counted anyway

determineOperatorPrecedenceAndLocation

This method is quite impenetrable to me, and I really suspect there are latent bugs lurking within it, particularly given the behavior of parens above. I think you'll want to comment more heavily what you're doing here or take a different approach.

Overall approach

Unorthodox method of parsing

Your overall approach to parsing expressions is unorthodox. Now, this isn't necessarily a bad thing, but it's more difficult for me to examine, and a more traditional approach may end up being more extensible and easier to maintain. Normally you'd split this up into a few stages: first, you lex the string into a series of tokens, so the input 5 + 6 == 10 + [x] might yield the tokens

INT 5
PLUS
INT 6
EQUALS
INT 10
PLUS
VAR x

From there, you parse it out. If you're just planning on using the result, you can evaluate it as you parse. You can also build an abstract syntax tree (AST) and evaluate from there, but evaluating immediately should be fine.

For the actual parsing, you've got a bunch of possible approaches. If you wanted to go down this route, I might read up on recursive-descent parsers and then Pratt parsers. There are also a variety of parser-generators like ANTLR, but I'd try to first write one manually.

Extensibility

You may want to consider making it easier to extend your expression parser to add more operators and such. For example, say I wanted to use the modulo operator. A good API for this might be something like this:

ExpressionParser parser = new ExpressionParser();
parser.addOperator(new InfixOperator() {
    @Override
    public String getSymbol() {
        return "%";
    }

    @Override
    public int getPrecedence() {
        return 20;  /* or whatever's appropriate within your system */
    }

    @Override
    public Associativity getAssociativity() {
        return Associativity.LEFT;
    }

    @Override
    public double evaluate(double left, double right) {
        return left % right;
    }
});
System.out.println(parser.evaluate("7 % 3 == 2"));  // => false

I don't know how I'd fit this in with your approach, but it is trivial with a Pratt parser.

Appropriateness

I admire your effort in this, and while I imagine this would be useful in many cases, I'm not so sure your list library needs this. There is a rather straightforward translation of predicates into Java: that is, an interface and anonymous classes, as we did with the extensibility example. For example:

public interface Predicate<T> {
    public boolean matches(T item);
}

Then you could filter a list of integers like so:

int[] integers = new int[] { 1, 2, 3, 4, 5 };
integers = Halo.filter(integers, new Predicate<Integer>() {
    @Override
    public boolean matches(Integer item) {
        return item % 2 == 0;  // even items only
    }
});

Now, I'm not suggesting you completely abandon your approach. I just think you might want to support that use and then provide an ExpressionPredicate or something so I could do this:

integers = Halo.filter(integers, new ExpressionPredicate<int>("[item] % 2 == 0"));

Then I can pick and choose whether I want to use Java or your mini-language to write my predicate. I can even use ExpressionPredicate from within my Predicate that's otherwise written in Java: I get the best of both worlds.