Versions Compared

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.

...

Given validly formed grouped criteria, we must process everything with the correct order of operations. For this, we should use the Shunting-yard algorithm. I've written this algorithm in PHP so we should port it to Java.

Code Block
	/**
     * Breakdown a valid selection criteria using the Shunting-yard algorithin
     * @see http://en.wikipedia.org/wiki/Shunting-yard_algorithm
     * @param string $criteria
     * @return array $criteria in reverse polish notation {@link http://en.wikipedia.org/wiki/Reverse_Polish_notation}
     * @since 1.1.0
     */
    private static function breakdownSelectionCriteria($criteria) {
        $rangeSeparator = "*\*";
        $spaceSeperator = "++\++";
        $_criteria = $criteria;
        $stack = array();
        $queue = array();
        $criteria = str_replace("(", " ( ", $criteria);
        $criteria = str_replace(")", " ) ", $criteria);
        $criteria = preg_replace("/(range) ([0-9]+) ([0-9]+)/i",
                "$1$2$rangeSeparator$3", $criteria);
        $criteria = preg_replace("/'([a-zA-Z0-9]+)([\s])+([a-zA-Z0-9]+)'[\s]*/i",
                "$1$spaceSeperator$3", $criteria);
        foreach (self::$_SELECTION_CRITERIA_OPERATORS as $operator) {
            $criteria = str_ireplace(" $operator", $operator, $criteria);
            $criteria = str_ireplace("$operator ", $operator, $criteria);
        }
        $tokens = array_filter(explode(" ", $criteria));
        foreach ($tokens as $token) {
            $token = str_replace($rangeSeparator, " ", $token);
            $token = str_replace($spaceSeperator, " ", $token);
            if (strcasecmp($token, "and") == 0 || strcasecmp($token, "or") == 0) {
                while (!empty($stack)) {
                    $topOfStack = $topOfStack = $stack[count($stack) - 1];
                    if (strcasecmp($token, "or") == 0 && (strcasecmp($topOfStack,
                                    "or") == 0 || strcasecmp($topOfStack, "and")
                            == 0)) {
                        $queue[] = array_pop($stack);
                    }
                    else {
                        break;
                    }
                }
                array_push($stack, $token);
            }
            else if (strcasecmp($token, "(") == 0) {
                array_push($stack, $token);
            }
            else if (strcasecmp($token, ")") == 0) {
                $foundLeftParen = false;
                while (!empty($stack)) {
                    $topOfStack = $stack[count($stack) - 1];
                    if (strcasecmp($topOfStack, "(") == 0) {
                        $foundLeftParen = true;
                        break;
                    }
                    else {
                        $queue[] = array_pop($stack);
                    }
                }
                if (!$foundLeftParen) {
                    throw new \Exception("Syntax error in criteria $_criteria. Mismatched parenthesis");
                }
                array_pop($stack);
            }
            else {
                $queue[] = $token;
            }
        }
        while (!empty($stack)) {
            $topOfStack = $stack[count($stack) - 1];
            if (strcasecmp($topOfStack, ")") == 0 || strcasecmp($topOfStack, "(")
                    == 0) {
                throw new \Exception("Syntax error in criteria $_criteria. Mismatched parenthesis");
            }
            $queue[] = array_pop($stack);
        }
        return $queue;
    }

 

Implementation Plan

...

Implementation Plan

TaskDescriptionNotes
Define Criteria grammarImplement the rules of the grammar, define all the appropriate symbols, and define all the appropriate operations 
Port Shunting-yard to JavaGiven a collection of symbols, implement the algorithm that returns those symbols in reverse polish notation. 
Implement Criteria builderImplement a builder that allows the programatic creation of a Criteria 
Edit Public APIAdd the appropriate methods to the public api