Существуют ли библиотеки для разбора «числовых выражений», такие как 1,2-9,33- в Java - PullRequest
5 голосов
/ 25 мая 2010

Я не думаю, что это трудно, просто утомительно писать: небольшая бесплатная (как в пиве) библиотека, где я могу вставить строку типа 1,2-9,33- и она может сказать мне, является ли данный число соответствует этому выражению. Так же, как большинство программ имеют в своих диалоговых окнах диапазона печати. Специальные функции для сопоставления только нечетных или четных чисел, или для сопоставления каждого числа, которое является 2 mod 5 (или что-то в этом роде), было бы неплохо, но не нужно.

Единственная операция, которую я должен выполнить в этом списке, состоит в том, содержит ли диапазон заданное (неотрицательное) целочисленное значение; больше операций, таких как значение max / min (если они существуют) или итератор, конечно, было бы неплохо.

Что бы потребовалось, чтобы он не занимал много ОЗУ, если кто-нибудь введет 1-10000000, но единственное число, которое я когда-либо запрашиваю, это 12345: -)

(Для его реализации я бы разбил список на несколько (min / max / value / mod) пар, например, 1,10,0,1 для 1-10 или 11,33,1,2 для 1-33odd или 12,62,2,10 для 12-62 / 10 (т. е. 12, 22, 32, ..., 62), а затем проверьте каждое число для всех интервалов. Откройте интервалы с помощью Integer.MaxValue и т. д. Если есть нет ли библиотек, есть идеи сделать это лучше / эффективнее?)

Ответы [ 3 ]

3 голосов
/ 26 мая 2010

Я решил, что это действительно так. Используйте на свой страх и риск :-)

/* 
 * NumberExpression.java - a simple number expression parser
 * 
 * Copyright (c) 2010 Michael Schierl
 * 
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 
 * - Redistributions of source code must retain the above copyright notice,
 *   this list of conditions and the following disclaimer.
 *   
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 *   
 * - Neither name of the copyright holders nor the names of its
 *   contributors may be used to endorse or promote products derived from
 *   this software without specific prior written permission.
 *   
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND THE CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * HOLDERS OR THE CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
 * TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
 * USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package numberexpression;

/**
 * An expression that matches nonnegative numbers. This supports cron-like
 * expressions, like <code>1,3-6,100-200,666,1000-3000/5,400-/7</code>,
 * <code>-100,102-</code> or <code>*</code>. Odd or even numbers can be
 * matched either by cron's step syntax, or by suffixing a simple range
 * (without step values) with <code>e</code> or <code>o</code>.
 * 
 * @author Michael Schierl
 */
public class NumberExpression {

    private final NumberRange[] ranges;
    private final int min, max;

    /**
     * Create a new {@link NumberExpression}.
     * 
     * @param pattern
     *            the expression pattern.
     * @throws IllegalArgumentException
     *             if the pattern is malformed
     */
    public NumberExpression(String pattern) {
        String[] parts = pattern.toLowerCase().split(",",-1);
        ranges = new NumberRange[parts.length];
        int min = Integer.MAX_VALUE, max = 0;
        for (int i = 0; i < ranges.length; i++) {
            String part = parts[i];
            try {
                if (part.equals("*")) {
                    ranges[i] = new NumberRange(0, Integer.MAX_VALUE, 0, 1);
                } else if (part.matches("\\*/\\d+")) {
                    ranges[i] = new NumberRange(0, Integer.MAX_VALUE, 0, Integer.parseInt(part.substring(2)));
                } else if (part.matches("\\d+")) {
                    int value = Integer.parseInt(part);
                    ranges[i] = new NumberRange(value, value, 0, 1);
                } else if (part.matches("\\d*-\\d*")) {
                    String[] limits = part.split("-", -1);
                    int from = limits[0].length() == 0 ? 0 : Integer.parseInt(limits[0]);
                    int to = limits[1].length() == 0 ? Integer.MAX_VALUE : Integer.parseInt(limits[1]);
                    if (to < from)
                        throw new IllegalArgumentException("Invalid pattern: " + part);
                    ranges[i] = new NumberRange(from, to, 0, 1);
                } else if (part.matches("\\d*-\\d*/\\d+")) {
                    String[] rangeAndModulus = part.split("/", -1);
                    String[] limits = rangeAndModulus[0].split("-", -1);
                    int from = limits[0].length() == 0 ? 0 : Integer.parseInt(limits[0]);
                    int to = limits[1].length() == 0 ? Integer.MAX_VALUE : Integer.parseInt(limits[1]);
                    int modulus = Integer.parseInt(rangeAndModulus[1]);
                    if (to < from)
                        throw new IllegalArgumentException("Invalid pattern: " + part);
                    ranges[i] = new NumberRange(from, to, from % modulus, modulus);
                } else if (part.matches("\\d*-\\d*[eo]")) {
                    String[] limits = part.substring(0, part.length() - 1).split("-", -1);
                    int from = limits[0].length() == 0 ? 0 : Integer.parseInt(limits[0]);
                    int to = limits[1].length() == 0 ? Integer.MAX_VALUE : Integer.parseInt(limits[1]);
                    if (to < from)
                        throw new IllegalArgumentException("Invalid pattern: " + part);
                    ranges[i] = new NumberRange(from, to, part.charAt(part.length() - 1) == 'o' ? 1 : 0, 2);
                } else {
                    throw new IllegalArgumentException("Invalid pattern: " + part);
                }
                max = Math.max(max, ranges[i].getMax());
                min = Math.min(min, ranges[i].getMin());
            } catch (NumberFormatException ex) {
                throw new IllegalArgumentException("Invalid pattern: " + part);
            }
        }
        this.max = max;
        this.min = min;
    }

    /**
     * Check whether this number expression matches the given number.
     * 
     * @param number
     *            the number to check against
     * @return whether the expression matches the number
     */
    public boolean matches(int number) {
        if (number < min || number > max)
            return false;
        for (int i = 0; i < ranges.length; i++) {
            if (ranges[i].matches(number))
                return true;
        }
        return false;
    }

    /**
     * Return the minimum number that can be matched.
     */
    public int getMinimum() { return min; }

    /**
     * Return the maximum number that can be matched.
     */
    public int getMaximum() { return max; }

    private static class NumberRange {
        private final int min, max, remainder, modulus;

        NumberRange(int min, int max, int remainder, int modulus) {
            this.min = min;
            this.max = max;
            this.remainder = remainder;
            this.modulus = modulus;
        }

        boolean matches(int number) {
            return number >= min && number <= max && number % modulus == remainder;
        }

        int getMin() { return min; }  
        int getMax() { return max; }
    }
}
1 голос
/ 25 мая 2010

Похоже, было бы проще просто написать код.

Вот код Python, поддерживающий часть диапазона ваших пожеланий.

>>> def f(n, pattern):
...     ranges = [r.split('-') for r in pattern.split(',')]
...     for a,b in ranges:
...             if (not a or int(a) <= n) and (not b or int(b) >= n):
...                     return True
...     return False
... 
>>> f(4, '-1,2-9,33-')
True
>>> f(11, '-1,2-9,33-')
False
>>> f(100, '-1,2-9,33-')
True
>>> 

Он работает за линейное время до длины строки. Если вы скомпилируете шаблон в IntervalTree, вы можете сделать это логарифмическим. Использование памяти всегда линейно.

1 голос
/ 25 мая 2010

Apache Commons имеет NumberRange

http://commons.apache.org/lang/api-2.4/org/apache/commons/lang/math/NumberRange.html

Это также соответствует вашим потребностям:

http://gleichmann.wordpress.com/2008/01/21/declarative-programming-a-range-type-for-java/

...