[Java] String format against opening & closing characters

How to validate the format of a given string according to a given set of opening-closing character pairs? This has been raised as an interview question, so I thought of writing a simple program to solve this.

Let me elaborate the question. There are characters that are considered as opening characters and closing characters; when '(' is an opening character, the relevant closing character is ')' For example; ([]) is correctly formatted, but ([) is not. So your task is to find out whether all the starting characters are properly ended with a ending character.

Here, I am using a Stack (java.util.Stack) to solve the problem.

GroupingPair class

A simple class named GroupingPair is written to hold pair of opening and closing characters. For instance, '[' for starting and ']' for ending.

package com.digizol.interviews.string.format;

public class GroupingPair {

    private Character start;
    private Character end;

    public GroupingPair(Character start, Character end) {
        this.start = start;
        this.end = end;
    }

    public Character getStart() {
        return start;
    }

    public Character getEnd() {
        return end;
    }
}

FormatValidator class

This class has implemented the logic using a stack. This can be initialized with a list of GroupingPair objects. Then a given strings each character is compared against the GroupingPair objects to find out whether there is an opening or closing characters. If an opening character is found, related GroupingPair instance is pushed to the stack. Similarly, if a closing tag is found, the top GroupingPair is popped and compared with the character to see whether it matches with the expected.

package com.digizol.interviews.string.format;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class FormatValidator {

    private Map<Character, GroupingPair> openingChars;
    private Map<Character, GroupingPair> closingChars;

    public FormatValidator(GroupingPair[] pairs) {
        initOpeningCharacters(pairs);
        initClosingCharacters(pairs);
    }

    private void initClosingCharacters(GroupingPair[] pairs) {
        closingChars = new HashMap<Character, GroupingPair>();
        for (GroupingPair pair: pairs) {
            closingChars.put(pair.getEnd(), pair);
        }
    }

    private void initOpeningCharacters(GroupingPair[] pairs) {
        openingChars = new HashMap<Character, GroupingPair>();
        for (GroupingPair pair: pairs) {
            openingChars.put(pair.getStart(), pair);
        }
    }

    public boolean validate(String string) {
        return validate(string, false);
    }
    
    public boolean validate(String string, boolean validateOtherCharacters) {

        Stack<GroupingPair> stack = new Stack<GroupingPair>();

        char[] characterArray = string.toCharArray();

        for (Character c: characterArray) {

            if (openingChars.containsKey(c)) {
                stack.push(openingChars.get(c));
            } else if (closingChars.containsKey(c)) {
                if (!c.equals(stack.pop().getEnd())) {
                    return false;
                }
            } else if (validateOtherCharacters) {
                System.out.println("Unexpected character '" + c + "' found in string: " + string);
                return false;
            }
        }
        return stack.isEmpty();
    }
}

Test class

This is a simple class with the main method to test few examples. Character pairs (), '<'>' and [] are given for initialization.

package com.digizol.interviews.string.format;

public class Test {

    public static void main(String[] args) {

        FormatValidator validator = new FormatValidator(createPairs());

        String[] toTest = { "[(])", 
                            "([<>])", 
                            "([)", 
                            "()[]<>", 
                            "(()[]<>)",
                            "(mal [ formatted )",
                            "(this [ is < well > formatted ] text)"
                            };

        for (String string : toTest) {

            boolean valid = validator.validate(string, false);

            if (valid) {
                System.out.println(string + " \t-> well formatted");
            } else {
                System.out.println(string + " \t-> malformed");
            }
        }
    }

    private static GroupingPair[] createPairs() {
        GroupingPair[] pairs = new GroupingPair[] {
                                new GroupingPair('(', ')'), 
                                new GroupingPair('<', '>'), 
                                new GroupingPair('[', ']') 
        };
        return pairs;
    }
}

Following is the output you will get when this Test class is executed.

[(]) -> malformed
([<>]) -> well formatted
([) -> malformed
()[]<> -> well formatted
(()[]<>) -> well formatted
(mal [ formatted ) -> malformed
(this [ is < well > formatted ] text) -> well formatted

As you can see, the program has identified whether a string is well formatted or not. This eclipse project is available for download.