Vizor Vizor - 13 days ago 4
Java Question

Java string arrayList: Sorting the elements in descending order (like polynomials in math)

I'm still quite new to programming, so I'm sorry if I caused you to face palm.

Right now, I am trying to create parentheses-expander in Java. The current program can already expand the parentheses, but it can not simplify the results, because the terms are not in the descending order. I do understand that you could try to add the terms without re-ordering them by comparing the variables contained in each of the elements. However, I want the program to "show work" like a human, so I need the terms in descending order.

And for that, I want to create a method that, given a string arrayList, re-orders the elements in something like descending order for polynomials in math.

If any of the variables had exponents, the variable is just repeated to the number of the exponent.
for example:

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


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.
Capital letters have higher importance than lower case letters, and elements with just numbers should be re-located to the very end.

I forgot the mathematical word for that, but the terms should be ordered in a interest of A, then B so on until Z, and then a,b,c,...so on.(I mean, terms with most A comes first, B second ,C third... up until z)

Coefficients and operators should be ignored.

For example, if the input was this:

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


Then I want the method to return the arrayList like:

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


I'm very much stuck right here. any help will be appreciated. If I didn't describe my problem clear enough, please let me know. I will clarify.

I believe wolfram alpha already has parentheses expanding capabilities. However, I still want to make this.

If anyone can help me with this, that will be amazing. Thanks in advance!

Answer

You have a couple of challenges that need to be dealt with individually:

  1. How do I parse something like -1b into a format I can work with?
  2. How do I sort by a custom sorting rule?

For the first part, your rule is very well-defined and the format is pretty simple. This lends itself well to using a regular expression to parse it:

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.

So a good regular expression format might be:

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

This would result in two "capture groups". The first would be the numeric part, and the second would be the (optional) repeated string part.

After decomposing each entry into these two separate parts, it is pretty easy to come up with a set of rules for determining the sort order:

  1. If both of them are numbers (having only the first part), then sort as numbers
  2. If one of them is a number, and the other has letters, sort the number afterward.
  3. If both have numbers and letters, sort according to the letters only using normal String sorting.

An easy way to do custom sorting is to write a custom Comparator class which would be used as an argument to the sort function. Combining all the ideas presented above that might look something like this:

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;
    }
}

Finally, to tie it all together, here is a simple program that correctly sorts your provided example using this Comparator (with the exception of your second and third entry which I believe is wrong in your example):

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]

Hopefully you can spend some time walking through this and learn a few ideas that will help you on your way. Cheers!

Comments