...
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
Task | Description | Notes |
---|---|---|
Define Criteria grammar | Implement the rules of the grammar, define all the appropriate symbols, and define all the appropriate operations | |
Port Shunting-yard to Java | Given a collection of symbols, implement the algorithm that returns those symbols in reverse polish notation. | |
Implement Criteria builder | Implement a builder that allows the programatic creation of a Criteria | |
Edit Public API | Add the appropriate methods to the public api |