9
\$\begingroup\$

I'm working on a program that corrects all punctuation spacing in a String.


Examples:

// "Hello ,World"  ->  "Hello, World"
// "9 :00 A .M ."  ->  "9:00 A.M."
// "can 't even."  ->  "can't even."

Here's how it works:

My process is to first add a space between all punctuation and then remove any unnecessary spaces. This allows me to tokenize both punctuation and words/numbers correctly.

For example, the acronym String s = " A .M ." is transformed into "A . M .".

When split by a space, it returns the list ["A", ".", "M", "."].

I then attempt to "fix" the remaining line spacing in the String, so the result will become "A.M.".


Here's an example of what the code looks like for correcting acronyms:

In FixAcronym.java:

/**
 * Fix acronyms.
 */
private static String fix(String line, SubtitleObject so) {
    StringBuilder builder = new StringBuilder();
    String[] split = so.split(RegexEnum.SPACE, line); // same as line.split(" ") but cached
    String prevPrevPrev = null, prevPrev = null, prev = null, current = null;
    boolean addSpace;
    for (int i = 0; i < split.length; ++i) {
        prevPrevPrev = prevPrev;
        prevPrev = prev;
        prev = current;
        current = split[i];
        addSpace = true;
        if (prevPrevPrev != null && prevPrevPrev.length() == 1
            && Character.isLetter(prevPrevPrev.charAt(0))) {
            if (prevPrev.equals(".")) {
                if (prev.length() == 1 && Character.isLetter(prev.charAt(0))) {
                    if (current.equals(".")) {
                        StringBuilderUtil.deleteSpaceAt(builder, builder.length() - 2);
                        StringBuilderUtil.deleteOnlyIfSpaceAt(builder, builder.length() - 3);
                        addSpace = false;
                    }
                }
            }
        }

        if (i > 0 && addSpace) {
            builder.append(' ');
        }
        builder.append(current);
    }

    return builder.toString();
}

In StringBuilderUtil.java:

/**
 * Delete space at index within StringBuilder.
 */
public static void deleteSpaceAt(StringBuilder builder, int index) {
    assert builder.charAt(index) == ' ';
    builder.deleteCharAt(index);
}

/**
 * Delete only if space at index within StringBuilder.
 */
public static void deleteOnlyIfSpaceAt(StringBuilder builder, int index) {
    if (builder.charAt(index) == ' ') {
        builder.deleteCharAt(index);
    }
}

Here's the problem: Because of all the different grammatical rules, there are a lot of different "fix" methods, and each subsequent "fix" uses the same technique.

line = FixTime.fix(line, this);
line = FixContractions.fix(line, this);
line = FixAcronym.fix(line, this);
// etc...

Each fix splits the line by a space, iterates through the tokens, deletes the space(s) in the StringBuilder when necessary, and appends the space and/or token.

The problem with this process is hypothetically I only need to iterate through the split line once to get the corrected String. This also makes the continuous creations, deletions, and appendings of the StringBuilder extraneous.


So the question is: Is there a better way to generalize this process while still preserving modularity, or is this as good as it gets?

\$\endgroup\$
  • \$\begingroup\$ Have you looked more into regular expressions? \$\endgroup\$ – h.j.k. Nov 12 '15 at 1:34
  • 1
    \$\begingroup\$ Yes I have. As I was writing this question I noticed that specifically the acronym example could be simplified using a regex. I haven't tried anything out yet, but the biggest challenge I think would be to handle acronyms of size >2, such as "S . H . I . E . L . D .". \$\endgroup\$ – budi Nov 12 '15 at 2:33
  • \$\begingroup\$ What about cases like "Numbers as text. 10: ten , 9: nine", or IP-addresses: "192.168 . 1 . 2" or "2001:0db8:85a3:08d3:1319:8a2e:0370:7344", or ratio's "1:3", or ... In short your example list is a little short and simplistic, and maybe you'll want to look at websites punctuationguide: period or punctuationguide: colon. \$\endgroup\$ – holroy Nov 18 '15 at 22:09
  • \$\begingroup\$ @holroy I didn't want to put too many test cases in my post, but I do have unit-tests for some of the more specific cases as you said! \$\endgroup\$ – budi Nov 18 '15 at 22:18
  • \$\begingroup\$ When not putting all diffferent cases, you'll have a hard time verifying whether the different solutions actually does what they are supposed to do... \$\endgroup\$ – holroy Nov 18 '15 at 22:22
2
+50
\$\begingroup\$

Before I start with the logic there are some points that needs addressing :

  1. What is a SubtitleObject? (In that case, it's not naming related, it doesn't seem to be a Java object). Why don't you work with a String? Those are questions that might remain unanswered, but I see no reasons why your method wouldn't work with a String input and without the SubtitleObject.

  2. Naming. line isn't a good variable name. What is line in this case? split isn't good either in my opinion. The content of the split variable isn't a split, it's the result of a splitted input. So maybe splittedInput might be better? fix as a method name isn't good either. What does it fix? How am I supposed to know? (Especially since there's very little JavaDoc). This could be fixed (lol) by adding more documentation to your method. I won't address the other variables as I think they might disappear during the review.

The problem with your implementation is that it hides the logic! Here are the cases as I've understood them from your code:

  1. Period . – remove all spaces
  2. Comma , – keep a space at the right and remove everything else
  3. Apostrophe/single quote ' – remove all spaces
  4. Colon : – remove all spaces

This logic is hidden behind some charAt, length, prevValue etc. It is very hard to understand what your code does just by looking at it!

So, to remove some "noise", we'd start by normalizing the input. What does that mean? It means removing "multi-spaces" and spaces that might be at the beginning/ending of your String. We'll do that in two steps, the first one is to trim the input, the second is to apply a regex to remove multi-spaces. Let's extract this in a method.

private String normalizeInput(String input) {
    String newInput = input.trim();
    return newInput.replaceAll(" +", " ");
}

Now, we have a clean input! We can split it to a well-formed array that won't contain useless spaces. I'll skip the split, you have that done already.

Now, I'll use an example to continue. Imagine the input is : " 9 :00 A .M . ,I can 't even. " which seems to cover all your cases.

After the normalization and the split, we now have this array :

["9",":00","A",".M",".",",I","can","'t","even."]

Let's create a list with the characters that we need to verify. (I'm using a list because we'll use contains later).

List<Character> Punctuations = Arrays.asList('\'','.',':',',');

We'll use this array to verify if we need to work on a chunk of the array. We'll create a method to verify if there's a punctuation sign at the beginning or the end of your input, any other checks are useless! (You'll see why we return the index later). Note that you'll need good JavaDoc to document this method.

private int indexOfContainedPunctuation(String input) {
    if (Punctuations.contains(input.charAt(0))) {
        return 0;
    }
    else if(punctuation.contains(input.charAt(input.length() - 1))) {
        return input.length() - 1;
    }
    return -1;
}

Now, if the chunk of array doesn't contain punctuation, we can skip it. Even if we had a case like : "asd ,b" -> ["asd"," ,b"], we'll be able to treat the punctuation correctly in the second chunk of array.

Now, if there's a punctuation sign, we need to treat it!. As I wrote before, we have two cases : [':',''','.'], [','].

We need to treat them clearly. We're going to use a switch statement for this :

String chunk = splittedInput[index];
int indexOfPunctuation = indexOfContainedPunctuation(chunk);
Character punctuation = chunk[indexOfPunctuation];
switch (punctuation) {
    case '\'':
    case ':':
    case '.':
        //Method to come
        break;
    case ',':
        //Method to come
        break;
}

We have now separated how we'll treat all our punctuation signs.

Let's check all methods, the first cases ['\'',':','.'], we need to remove all spaces. In the array, all spaces are already removed! So we can add the chunk to our StringBuilder.

The last case [','], we need to add a space after the comma. Let's do it, shouldn't be hard!

Here's the final result.

private static String fix(String input) {
    StringBuilder builder = new StringBuilder();
    String normalizedInput = normalizeInput(input);
    String[] splittedInput = normalizedInput.split(" ");

    for(int index = 0; index < splittedInput.length; index++) {
        String chunk = splittedInput[index];
        int punctuationIndex = indexOfContainedPunctuation(chunk);
        if(punctuationIndex == -1) {
            //There's nothing to do with this chunk
            builder.append(chunk + " ");
            continue;
        }

        switch(chunk.charAt(punctuationIndex)) {
            case '.':
            case ':':
            case '\'':
                fixForOthers(builder,chunk,isPunctuationAtBegin(punctuationIndex));
                break;
            case ',':
                fixForComma(builder,chunk,isPunctuationAtBegin(punctuationIndex));
                break;
        }
    }

    return builder.toString();
}

private static String normalizeInput(String input) {
    String newInput = input.trim();
    return newInput.replaceAll(" +", " ");
}

private static final List<Character> Punctuations = Arrays.asList('\'','.',':',',');
private static int indexOfContainedPunctuation(String input) {
    if (Punctuations.contains(input.charAt(0))) {
        return 0;
    }
    else if(Punctuations.contains(input.charAt(input.length() - 1))) {
        return input.length() - 1;
    }
    return -1;
}

private static void fixForOthers(StringBuilder builder, String chunk, boolean punctuationAtBegin) {
    if(punctuationAtBegin) {
        builder.deleteCharAt(builder.length() - 1);
        builder.append(chunk + " ");
    } else {
        builder.append(chunk);
    }
}

private static void fixForComma(StringBuilder builder, String chunk, boolean punctuationAtBegin) {
    if(punctuationAtBegin) {
        builder.deleteCharAt(builder.length() - 1);
        builder.append(", " + chunk.substring(1) + " "); 
    } else {
        builder.append(chunk + ", ");
    }
}

private static boolean isPunctuationAtBegin(int punctuationIndex){
    return punctuationIndex == 0;
}

I had to add a little tweak here : builder.deleteCharAt(builder.length() - 1);. This is to counter the whitespace that is added on the previous chunk.

I've extracted alot of methods. I still don't like the fix method name but I added it in my examples for clarity. There's still a need for JavaDoc but I didn't add it to keep my post as short as possible.

\$\endgroup\$
  • \$\begingroup\$ I think you are really onto something here, but I would clarify the case list with something like: 'Case 1: . period:', 'Case 2: , comma:', and so on. It looks a little confusing with only the punctioation marks... \$\endgroup\$ – holroy Nov 18 '15 at 22:25
  • \$\begingroup\$ It's dumb, but I don't know the name of the punctuation marks in English :p If you want to edit it though, I would appreciate it! \$\endgroup\$ – IEatBagels Nov 18 '15 at 22:36
  • 1
    \$\begingroup\$ I did a little edit on your post! :-) \$\endgroup\$ – holroy Nov 18 '15 at 22:47
5
\$\begingroup\$

I would split it into three stages, and two concepts.

Conceptually, split the problem into:

  1. String manipulation (reading and writing)
  2. Logical problems (what exists and what needs doing)

The stages the process might be split into:

  1. The first stage involves reading the string, parsing it from beginning to end, recording the logical aspects of what exists.
  2. The second stage involves manipulating the logical record that represents the tokens, transforming it from a representation of what exists, to a representation of what string manipulations are required.
  3. The third stage is executing the string manipulation.
\$\endgroup\$
3
\$\begingroup\$

To answer your question

In my experience, there's (almost) always a better way :)

As a review to your code

Everything looks good to me. The one thing I'd change is the following piece of code:

   if (prevPrevPrev != null && prevPrevPrev.length() == 1
        && Character.isLetter(prevPrevPrev.charAt(0))) {
        if (prevPrev.equals(".")) {
            if (prev.length() == 1 && Character.isLetter(prev.charAt(0))) {
                if (current.equals(".")) {
                    StringBuilderUtil.deleteSpaceAt(builder, builder.length() - 2);
                    StringBuilderUtil.deleteOnlyIfSpaceAt(builder, builder.length() - 3);
                    addSpace = false;
                }
            }
        }
    }

into

   if (prevPrevPrev != null && prevPrevPrev.length() == 1
       && Character.isLetter(prevPrevPrev.charAt(0))
       && prevPrev.equals(".")
       && prev.length() == 1 
       && Character.isLetter(prev.charAt(0))
       && current.equals(".")) {

       StringBuilderUtil.deleteSpaceAt(builder, builder.length() - 2);
       StringBuilderUtil.deleteOnlyIfSpaceAt(builder, builder.length() - 3);
       addSpace = false;
  }

and set the 2 and 3 as fields/variables (they seem kind of magic numbers now). Basically, the refactoring just reduces the depth of the code, but that's just personal taste.

As an alternative method

The critical point, IMO is to know what the input string represents and seems like you've already taken care of that (if I understood it correctly). Everything else should be pretty easy.

The way I'd go with it is the following:

  1. Get the type of info the input string represents. Already taken care of.
  2. Keep track of the different punctuation characters in the different input types. For example: : and . for dates, . for acronyms, and so on.
  3. Write a method that splits and merges again a string on a certain char. Something on the lines of public static string splitAndMergeAgain(string original, char splittingChar, bool includeSpaceAfterSplittingChar). Once you split the original string by the splitting char you just trim its components (remove the starting and ending spaces).
  4. Call the method in the various cases. In the acronym's case (picked this one because it has only one splitting character) the call will be something like the following: String result = splitAndMergeAgain(original, '.', false). In the case of dates you have to call it twice, once per punctuation character. In the case of phrases you have to call it more times (you have multiple splitting punctuation characters: ,, ., ;, :, ? and so on).
  5. Final step. Remove possible double spaces (just replace with and you should be good to go).

Let me know if anything is unclear.

\$\endgroup\$
2
\$\begingroup\$

Similar to Jodes answer, i would suggest to break up the process in multiple steps:

For each type of textblock you want to correct( date, acronym ...) define formatting rules.

  1. You split the string on whitespaces.
  2. try to identify all the parts as specific tokens ( hour part, acronym part, ...)
  3. Pass the tokens to formatter classes
  4. Re-build the string up again from the tokens with the correct formatting applied!

For more complex scenarios you could create formatter classes that take multiple tokens to generate the correct formatting.

For example: a date contains day,month, year, maybe even the time. You could have a DateFormatter class that can output the correct format.

\$\endgroup\$
1
\$\begingroup\$

I wouldn't go into word splitting. I'd use a sequence of RegExp instead.

Here is a JavaScript sample. Take a look at out3 variable in processAll method and how I cascade call multiple regexp methods.

You can see it running here: http://jsfiddle.net/davidrc/7o9ubs4b/3/

var samples = [
    "9 :00 A .  M .",
    "14:  54   A  .    M   .",
    "at 23  :  00 A  . M . I'll watch S.   H.  I. E.     L.  D. and go"
];

processAll(samples);

function normalizeHour(src) {
    // A simple substitution using regexp in the entire string
    var re = /\b([012]?\d)\s*:\s*(\d{2})\b/g;
    return src.replace(re, "$1:$2");
}

function normalizeAcronyms(src) {
    // Let's first match all Acronyms occurrencies
    var re = /\b(\w\s*\.)(\s*\w\s*\.)+/g;
    var changeFILOQueue = [];
    var myArr;

    while ( (myArr = re.exec(src)) != null) {
        var subSrc = myArr[0]; // We want the whole match
        var newText = subSrc.replace(/\s+/g, ""); // Get rid of all spaces between
        var spliceParams = {start: myArr.index, count: subSrc.length, add: newText};
        // Push your changes to a FILO (First In Last Out) queue, applying later
        changeFILOQueue.push(spliceParams);
    };


    // We need to apply our changes backwards,
    // otherwise captured positions become wrong after each change
    var result = src;
    while (changeFILOQueue.length > 0) {
        var prm = changeFILOQueue.pop();
        result = strSplice(result, prm.start, prm.count, prm.add);
    }

    return result;
}

function normalizeSpaces(src) {
    // A simple substitution to get rid of multiple spaces
    var re = / {2,}/g;
    return src.replace(re, " ");
}


function processAll(samples) {
    print("Applying normalizeHour");
    for (var i=0; i < samples.length; i++) {
        var src = samples[i];
        var out1 = normalizeHour(src);
        var out2 = normalizeAcronyms(src);
        var out3 = normalizeHour(src);
        out3 = normalizeAcronyms(out3);
        out3 = normalizeSpaces(out3);
        print("#out1", src, out1);
        print("#out2", src, out2);
        print("#out3", src, out3);
    }
}

function print(out, originalText, newText) {
    var $out = $(out);
    $out.text($out.text() + originalText + "  ===>  " + newText + "\n");
}

function strSplice(str, start, count, add) {
  return str.slice(0, start) + (add || "") + str.slice(start + count);
}

PS: I know you are using java, but it's not hard to transform it to equivalent java code. I put it as a Javascript because it is faster to code and to understand.

\$\endgroup\$
1
\$\begingroup\$

I'd use a strategy pattern for your problem: make all the Fix... methods classes that implements a FixStrategy interface. Than make an array of strategies.

Now you can:

  1. Split your string and set an empty result string.
  2. While the list of tokens is not empty
  3. Iterate on the strategies
  4. Pass the list of tokens to the strategy
  5. Let the strategy pop as many items as it needs from the list of tokens and return the corrisponding string.
  6. Update the result string and go to point 3

In this way you can also have more complex strategies: for instance you can make your strategies return a score and then apply the strategy with the best score.

In every case take a look at the strategy pattern, as it is one of the fundamentals for OO programming.

\$\endgroup\$
0
\$\begingroup\$

You have pretty much broken the problem into parts when you say

Each fix splits the line by a space, iterates through the tokens, deletes the space(s) in the StringBuilder when necessary, and appends the space and/or token.

You can have an abstract class on the lines below.

abstract class Fix implements Iterator {

    Fix(String line) {
        //Store them in private
        //Split them here by space if you want
    }

    //Call through the iterator's next
    abstract void deleteSpace();
    abstract boolean shouldDeleteSpace();

    //You said you have to iterate over the tokens
    //So now implement the iterator

    @Override
    public boolean hasNext() {
        //Your check. Length of token maybe?
    }

    @Override
    public Object next() {
        deleteSpace();
        //Other stuff
    }

    public String getResult() {
       //Iterate here. You just need to call appropriate methods here
       //From the outside you can just use this.
    }
}

Then just implement the parts which make sense for your sub-classes.

You said there is a lot of same stuff and just a small bit of difference. Isn't that a sure sign that you need inheritance? The abstract super class can give you the generalization that you need while still preserving modularity.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.