Java字符串数组列表: Sorting the elements in descending order (like polynomials in math)

Question

我对编程还很陌生，所以如果我让你面朝手掌，我很抱歉。

现在，我正在尝试用 Java 创建括号扩展器。当前的程序已经可以展开括号，但无法简化结果，因为项不是按降序排列的。我确实理解，您可以尝试通过比较每个元素中包含的变量来添加术语，而无需重新排序。但是，我希望程序像人类一样“展示工作”，因此我需要按降序排列这些术语。

为此，我想创建一个方法，在给定字符串 arrayList 的情况下，以类似于数学多项式的降序顺序对元素进行重新排序。

如果任何变量有指数，则该变量将重复到指数数。 例如:

X^2 = XX,
a^3 = aaa,
Z^5 = ZZZZZ

此外，不会有负指数或括号。 所有元素都以 + 或 - 开头(之后没有其他运算符)。 所有元素都有一个系数，即使它是 1。 大写字母比小写字母更重要，只有数字的元素应该重新定位到最后。

我忘记了数学术语，但是这些术语应该按照 A 的兴趣排序，然后是 B 等等，直到 Z，然后是 a，b，c，...等等。(我的意思是，术语大多数A排在第一位，B排在第二位，C排在第三位...直到z)

应忽略系数和运算符。

例如，如果输入是这样的:

[-1b,+3XX,-4AA,+1aaa,+20CCa,-9ABa,-9ABaa,+20CCCa,+3BBX,+1aab,+10]

然后我希望该方法返回 arrayList，如下所示:

[-4AA,-9ABaa,-9ABa,+3BBX,+20CCCa,+20CCa,+3XX,+1aaa,+1aab,-1b,+10]

我被困在这里了。任何帮助将不胜感激。如果我没有足够清楚地描述我的问题，请告诉我。我会澄清。

我相信 Wolfram alpha 已经具有括号扩展功能。不过，我还是想做这个。

如果有人能帮助我解决这个问题，那就太棒了。提前致谢!

Answer 1

您有几个需要单独处理的挑战:

1. 如何将 -1b 之类的内容解析为我可以使用的格式？
2. 如何按照自定义排序规则进行排序？

对于第一部分，您的规则定义非常明确，并且格式非常简单。这非常适合使用正则表达式来解析它:

Also, there will be no negative exponents nor parentheses. All elements have either + or - at the beginning(and no other operators after that). All elements have a coefficient, even if it is 1.

所以一个好的正则表达式格式可能是:

([-+]\d+)(\w+)?

这将产生两个“捕获组”。第一个是数字部分，第二个是(可选)重复的字符串部分。

将每个条目分解为这两个单独的部分后，很容易得出一组用于确定排序顺序的规则:

1. 如果都是数字(只有第一部分)，则按数字排序
2. 如果其中一个是数字，另一个是字母，则先对数字进行排序。
3. 如果两者都有数字和字母，则仅使用普通字符串排序根据字母进行排序。

进行自定义排序的一个简单方法是编写一个自定义的 Comparator 类，该类将用作 sort 函数的参数。结合上面提出的所有想法，可能看起来像这样:

public class PolynomialComparator implements Comparator<String> {

    private static Pattern pattern = Pattern.compile("([-+]\\d+)(\\w+)?");

    @Override
    public int compare(String s1, String s2) {
        if (s1 == null) throw new NullPointerException("s1");
        if (s2 == null) throw new NullPointerException("s2");

        int compare = 0;

        Matcher m1 = pattern.matcher(s1);
        Matcher m2 = pattern.matcher(s2);

        if (!m1.matches()) throw new IllegalArgumentException("Invalid Polynomial format: " + s1);
        if (!m2.matches()) throw new IllegalArgumentException("Invalid Polynomial format: " + s2);

        int n1 = Integer.parseInt(m1.group(1));
        int n2 = Integer.parseInt(m2.group(1));

        String p1 = m1.group(2);
        String p2 = m2.group(2);

        if (p1 == null && p2 == null) {  // Rule #1: just compare numbers
            compare = n2 - n1;
        } else if (p1 == null) {  // Rule #2: always sort number last
            compare = 1;
        } else if (p2 == null) {  // Rule #2: always sort non-number first
            compare = -1;
        } else {  // Rule #3: compare the letters
            compare = m1.group(2).compareTo(m2.group(2));
        }

        return compare;
    }
}

最后，为了将它们结合在一起，这里有一个简单的程序，它使用此 Comparator 对您提供的示例进行正确排序(除了您的第二个和第三个条目，我认为您的示例中的第二个和第三个条目是错误的) ):

public static void main(String args[]){
    String input = "[-1b,+3XX,-4AA,+1aaa,+20CCa,-9ABa,-9ABaa,+20CCCa,+3BBX,+1aab,+10]";
    String[] array = input.substring(1, input.length() - 1).split(",");
    Arrays.sort(array, new PolynomialComparator());
    System.out.println("[" + String.join(",", array) + "]");
}

OUTPUT: [-4AA,-9ABa,-9ABaa,+3BBX,+20CCCa,+20CCa,+3XX,+1aaa,+1aab,-1b,+10]

希望您能花一些时间浏览一下本文并了解一些对您有所帮助的想法。干杯!