A clean design solution By using design pattern


  • 40
    W

    This problem give me a good chance to convey the importance of good design. The problem is very vogue. The point here is not how you design a algorithm, it is how you handle all cases well. There is no a clear standard for whether is a number valid, is it .50 , 39. a legal float point number? Are there only valid formats given by the example? Is hex format such as 0x12ab legal? How about if we need to add another format such as roman number like "I, II , IV" as legal format. I found all solution are just plug logic into one function, there are lots of switch case, if else in there. It is problematic, easy for bugs, difficult to add new features, and of course, in-reusable, and here I propose a design to handle this problem easily and nicely.

    First we we can give out an interface for this problem:

    interface NumberValidate {
    
    	boolean validate(String s);
    }
    

    for any string, we call validate and it return whether the given string is a valid number. Follow we can create concrete implementation for this interface, such as IntegeValidator, FloatValidator, ScienceValidator. and then using chain of responsibility design patter (from book of GOF) , chain all those validator into a list, and feed the string to each one, if there is one validator return true, then the string is a valid number.

    The design has two advantages, one is easy to fix, for any corner cases or bug, we can locate the problem to specific validator, the effect of changing one validator will not sprint out to the all system, we call this as "encapsulation".

    Second is easy to extend, if we need to verify hex format or roman number format , we just need to create new validator and add to the chain, we call this advantage as "close for modification open for extension".

    Follow is code for the passed design:

    interface NumberValidate {
    
    	boolean validate(String s);
    }
    
    abstract class  NumberValidateTemplate implements NumberValidate{
    
    public boolean validate(String s)
    	{
    		if (checkStringEmpty(s))
    		{
    			return false;
    		}
    		
    		s = checkAndProcessHeader(s);
    		
    		if (s.length() == 0)
    		{
    			return false;
    		}
    		
    		return doValidate(s);
    	}
    	
    	private boolean checkStringEmpty(String s)
    	{
    		if (s.equals(""))
    		{
    			return true;
    		}
    		
    		return false;
    	}
    	
    	private String checkAndProcessHeader(String value)
    	{
    	    value = value.trim();
    	    
    		if (value.startsWith("+") || value.startsWith("-"))
    		{
    			value = value.substring(1);
    		}
    	
    	
    		return value;
    	}
    	
    	
    	
    	protected abstract boolean doValidate(String s);
    }
    
    class NumberValidator implements NumberValidate {
    	
    	private ArrayList<NumberValidate> validators = new ArrayList<NumberValidate>();
    	
    	public NumberValidator()
    	{
    		addValidators();
    	}
    
    	private  void addValidators()
    	{
    		NumberValidate nv = new IntegerValidate();
    		validators.add(nv);
    		
    		nv = new FloatValidate();
    		validators.add(nv);
    		
    		nv = new HexValidate();
    		validators.add(nv);
    		
    		nv = new SienceFormatValidate();
    		validators.add(nv);
    	}
    	
    	@Override
    	public boolean validate(String s)
    	{
    		for (NumberValidate nv : validators)
    		{
    			if (nv.validate(s) == true)
    			{
    				return true;
    			}
    		}
    		
    		return false;
    	}
    
    	
    }
    
    class IntegerValidate extends NumberValidateTemplate{
    	
    	protected boolean doValidate(String integer)
    	{
    		for (int i = 0; i < integer.length(); i++)
    		{
    			if(Character.isDigit(integer.charAt(i)) == false)
    			{
    				return false;
    			}
    		}
    		
    		return true;
    	}
    }
    
    class HexValidate extends NumberValidateTemplate{
    
    	private char[] valids = new char[] {'a', 'b', 'c', 'd', 'e', 'f'};
    	protected boolean doValidate(String hex)
    	{
    		hex = hex.toLowerCase();
    		if (hex.startsWith("0x"))
    		{
    			hex = hex.substring(2);
    		}
    		else
    		{
    		    return false;
    		}
    		
    		for (int i = 0; i < hex.length(); i++)
    		{
    			if (Character.isDigit(hex.charAt(i)) != true && isValidChar(hex.charAt(i)) != true)
    			{
    				return false;
    			}
    		}
    		
    		return true;
    	}
    	
    	private boolean isValidChar(char c)
    	{
    		for (int i = 0; i < valids.length; i++)
    		{
    			if (c == valids[i])
    			{
    				return true;
    			}
    		}
    		
    		return false;
    	}
    }
    
    class SienceFormatValidate extends NumberValidateTemplate{
    
    protected boolean doValidate(String s)
    	{
    		s = s.toLowerCase();
    		int pos = s.indexOf("e");
    		if (pos == -1)
    		{
    			return false;
    		}
    		
    		if (s.length() == 1)
    		{
    			return false;
    		}
    		
    		String first = s.substring(0, pos);
    		String second = s.substring(pos+1, s.length());
    		
    		if (validatePartBeforeE(first) == false || validatePartAfterE(second) == false)
    		{
    			return false;
    		}
    		
    		
    		return true;
    	}
    	
    	private boolean validatePartBeforeE(String first)
    	{
    		if (first.equals("") == true)
    		{
    			return false;
    		}
    		
    		if (checkHeadAndEndForSpace(first) == false)
    		{
    			return false;
    		}
    		
    		NumberValidate integerValidate = new IntegerValidate();
    		NumberValidate floatValidate = new FloatValidate();
    		if (integerValidate.validate(first) == false && floatValidate.validate(first) == false)
    		{
    			return false;
    		}
    		
    		return true;
    	}
    	
    private boolean checkHeadAndEndForSpace(String part)
    	{
    		
    		if (part.startsWith(" ") ||
    				part.endsWith(" "))
    		{
    			return false;
    		}
    		
    		return true;
    	}
    	
    	private boolean validatePartAfterE(String second)
    	{
    		if (second.equals("") == true)
    		{
    			return false;
    		}
    		
    		if (checkHeadAndEndForSpace(second) == false)
    		{
    			return false;
    		}
    		
    		NumberValidate integerValidate = new IntegerValidate();
    		if (integerValidate.validate(second) == false)
    		{
    			return false;
    		}
    		
    		return true;
    	}
    }
    
    class FloatValidate extends NumberValidateTemplate{
    	
       protected boolean doValidate(String floatVal)
    	{
    		int pos = floatVal.indexOf(".");
    		if (pos == -1)
    		{
    			return false;
    		}
    		
    		if (floatVal.length() == 1)
    		{
    			return false;
    		}
    		
    		NumberValidate nv = new IntegerValidate();
    		String first = floatVal.substring(0, pos);
    		String second = floatVal.substring(pos + 1, floatVal.length());
    		
    		if (checkFirstPart(first) == true && checkFirstPart(second) == true)
    		{
    			return true;
    		}
    		
    		return false;
    	}
    	
    	private boolean checkFirstPart(String first)
    	{
    	    if (first.equals("") == false && checkPart(first) == false)
    	    {
    	    	return false;
    	    }
    	    
    	    return true;
    	}
    	
    	private boolean checkPart(String part)
    	{
    	   if (Character.isDigit(part.charAt(0)) == false ||
    				Character.isDigit(part.charAt(part.length() - 1)) == false)
    		{
    			return false;
    		}
    		
    		NumberValidate nv = new IntegerValidate();
    		if (nv.validate(part) == false)
    		{
    			return false;
    		}
    		
    		return true;
    	}
    }
    
    public class Solution {
        public boolean isNumber(String s) {
            NumberValidate nv = new NumberValidator();
    
    	    return nv.validate(s);
        }
    }

  • 0
    P

    Hi! Very brilliant algorithm.I have a question:
    why is the part
    if (Character.isDigit(part.charAt(0)) == false ||
    Character.isDigit(part.charAt(part.length() - 1)) == false)
    {
    return false;
    }
    in class FloatValidate necessary?


  • 0
    M

    This is because in cases like "0. 7" , when we run the following code on the part after decimal,we will get incorrect result as validate() will clean leading spaces:

    NumberValidate nv = new IntegerValidate();
    if (nv.validate(part) == false)
    {
    return false;
    }

        return true;

  • 0
    M

    if we want to skip the part mentioned by you, we should use :
    IntegerValidate nv = new IntegerValidate();
    instead of
    NumberValidate nv = new IntegerValidate();
    And then use nv.doValidate(part) instead of nv.validate(part)


  • 0
    M

    Excellent! This should be the most voted solution


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.