# Improving the readability and efficiency of parser code

Recently, I had a test and I wrote this code, but they didn't like my code because it was "deplete and nested".

In order to improve my skills, what would be good ways to make this more readable and less deplete and nested?

Exercise

The validBraces method takes a string of braces as a single parameter and determines if the order of the braces is valid. All input strings will only consist of open curly braces {, closed curly braces }, open parentheses (, closed parentheses ), and open brackets [ and closed brackets ].

• A string of braces is considered valid if all open braces are matched with their corresponding closed brace. For example: (){}[] and ([{}]) would be considered valid, while (}, [(]), and [({})](] would be considered invalid.
• An empty string is considered valid.
• A non-string input is considered an invalid input. The method should throw an InvalidArgumentException in this case.

### titleCase

A string is considered to be in title case if each word in the string is either:

1. capitalised: that is, only the first letter of the word is in upper case; or
2. considered to be an exception and put entirely into lower case unless it is the first word, which is always capitalised.

The titleCase method will convert a string into titleCase given an optional list of exceptions. The list of exception words will be given as an array of strings. The method should ignore the case of the exception word strings—it should behave in the same way even if the case of the exception word strings changes.

Examples
php
// should return: 'Do Androids Dream of Electric Sheep?'
->titleCase('do androids dream of electric SHEEP?', array('do', 'an', 'of'));

php
//should return: 'Rendezvous with Rama'
->titleCase('RENDEZVOUS WITH RAMA', array('With'));

php
// should return: 'Stranger In A Strange Land'
->titleCase('stranger in a strange land');


This is my code:

class StringUtil {
/**
* Verify a string of braces
*
* Takes a string of braces as a single parameter and determines if the order of the braces is
* valid.
*
* @access public
* @param String $braces * @return Boolean * @throws \InvalidArgumentException If$braces is not a string
*/
public function validBraces($braces = '') { /** * I assume that empty string is valid because * is the default value * and you have in the test as valid */ if ($braces === '') {
return true;
} elseif (empty($braces)) { return false; } /** * array of chars allowed, * the keys are the open chars * the values are the closure */$symbols = array("(" => ")", "{" => "}", "[" => "]");

// get array with all characters allowed
$search = array_merge(array_keys($symbols), array_values($symbols)); //check valid string if (\strlen(str_replace($search, '', $braces)) > 0) { throw new \InvalidArgumentException("ERROR: Invalid Arguments. Just (){}[] characters allowed in the string"); } //check if the length is even if (\strlen($braces) % 2 !== 0) {
return false;
}

// Make sure start & end chars are not incorrect
if (in_array(substr($braces, 0, 1),$symbols) || array_key_exists(substr($braces, -1, 1),$symbols)) {
return false;
}

//Make sure the string have the same amount of open & end chars
foreach ($symbols as$key => $value) { if (substr_count($braces, $key) !== substr_count($braces, $value)) { return false; } }$bracesArray = str_split($braces); for ($i = 0; $i <= count($bracesArray) - 1; $i++) { if (in_array($bracesArray[$i],$symbols)) {
if ($bracesArray[$i] === $symbols[$bracesArray[$i - 1]]) { unset($bracesArray[$i],$bracesArray[$i - 1]); break; } else { return false; } } } if (!empty($bracesArray)) {
$newBraces = implode("",$bracesArray);
return $this->validBraces($newBraces);
}

return true;
}

/**
* Convert a string into title case given an optional list of exceptions.
*
* @access public
* @param String $title * @param Array$exceptions
* @return String
*/
public function titleCase($title,$exceptions = array()) {
$newExecption = array(); foreach ($exceptions as $execptionV) {$newExecption[] = strtolower($execptionV); }$stringArray = explode(' ', $title); foreach ($stringArray as $key =>$value) {
if (empty($newExecption)) {$new[] = ucfirst(strtolower($value)); } else { if ($key == 0) {
$new[] = ucfirst(strtolower($value));
} else {
if (!in_array(strtolower($value),$newExecption)) {
$new[] = ucfirst(strtolower($value));
} else {
$new[] = strtolower($value);
}
}
}
}
$newPhrase = implode(" ",$new);
return $newPhrase; } }  Test for validBraces:  public function validBraces() { return array( array('()'), array('{}'), array('[]'), array('(){}[]'), array('([{}])'), array('{}({})[]'), array('({})[({})]'), array('(({{[[]]}}))'), array('') ); } public function invalidBraces() { return array( array('(}'), array('[(])'), array('(})'), array(')(}{]['), array('())({}}{()][]['), array('(((({{'), array('}}]]))}])') ); } /** * @expectedException \InvalidArgumentException */ public function testInvalidArgumentException() {$this->util->validBraces(1);
}


Test for titleCase:

  public function testDefault() {
$this->assertSame('Abc Def Ghi',$this->util->titleCase('aBC deF Ghi'));
}

public function testFirstWord() {
$this->assertSame('Ab',$this->util->titleCase('ab', array('ab')));
}

public function testExceptionWord() {
$this->assertSame('A bc',$this->util->titleCase('a bc', array('bc')));
}

public function testExceptionWordIgnoresCase() {
$this->assertSame('A bc',$this->util->titleCase('a bc', array('BC')));
}

public function testBogusExceptionWords() {
$this->assertSame('First A Of In',$this->util->titleCase(
'First a of in', array('an', 'often', 'into')
));
}

public function testTitles() {
$this->assertSame('A Clash of Kings',$this->util->titleCase(
'a clash of KINGS', array('a', 'an', 'the', 'OF')
));

$this->assertSame('The quick Brown fox',$this->util->titleCase(
'the QUICK bRoWn fOX', array('xyz', 'fox', 'quick', 'the')
));
}

• You'll have problems with UTF-8 characters... – smt Oct 1 '14 at 6:15
• In the future, it would be better to post these as separate questions since they are separate problems. – David Harkness Oct 2 '14 at 4:44
• New code for the validBraces method – Emilio Gort Dec 9 '14 at 14:53

The code doesn't exactly match the question as stated.

A non-string input is considered an invalid input. The method should throw an InvalidArgumentException in this case.

The code does not throw an InvalidArgumentException for non-string inputs. For example, validBraces(array()) does not throw.

All input strings will only consist of open curly braces {, closed curly braces }, open parentheses (, closed parentheses ), and open brackets [ and closed brackets ].

The code checks for other characters in the string, which is unnecessary given this guarantee.

An empty string is considered valid.

But this comment makes it seem like the correct result for an empty string was unclear:

/**
* I assume that empty string is valid because
* is the default value
* and you have in the test as valid
*/


There is a canonical solution to this problem that makes one pass through the string, and uses a stack. A search for "balanced parentheses" will turn up hints/explanations, if you get stuck.

newExecption is misspelled. exceptionV and new are not great names.

We don't need to test if newExecption is empty.

I think there is a simpler approach:

• convert the exceptions to lowercase
• convert the string to lowercase
• for each word in the string:
• if it's the first word or not an exception, convert the first letter of the word to uppercase

I don't write PHP, but this is my attempt:

$caseExceptions = array_map(strtolower,$caseExceptions);
$words = explode(' ', strtolower($input));
foreach ($words as$i => $word) { if ($i == 0 || !in_array($word,$caseExceptions)) {
$words[$i] = ucfirst($word); } } return implode(' ',$words);

• could you please comment about the titleCase() method – Emilio Gort Oct 1 '14 at 14:36
• @EmilioGort updated the answer. – mjolka Oct 1 '14 at 23:32
• thanks @mjolka, also I test the string because they have this in the test $this->util->validBraces(1); but you are right in all you are saying – Emilio Gort Oct 2 '14 at 0:04 • @EmilioGort Yes, you get an InvalidArgumentException for that case, but try this for example: echo validBraces(array());. No exception thrown. – mjolka Oct 2 '14 at 0:10 • @EmilioGort just to be sure, please post your new code as a new question (some people make the mistake of updating their question). I think your problem solving skills are very strong -- completing these two tasks in a half hour is impressive, especially if you haven't seen the first question before. Just be sure to keep going back to the question, and make sure your code matches the spec. Don't jump into writing code either; think about how to make it as simple as possible before writing. That should hopefully reduce the complexity. – mjolka Oct 2 '14 at 0:19 1. The validBraces method is invoked recursively. That is all the preliminary tests are executed at each level of recursion. All of them are redundant beyond the top level: it is already established that • the string consists of valid characters • its length is even (characters are removed by 2 at a time) • each brace has equal count of opens and closes (this is how they are removed) Testing it over and over again just wastes cycles. I am not sure it is worth to test these at all (premature optimization is a word); if you feel it is beneficial, factor out the recursive method as a helper. 2. I don't know for sure the time complexity of str_split and implode. I am pretty positive it is linear at best. Doing them at each level of recursion results in a quadratic complexity overall. Doesn't a PHP string itself allow random access? 3. You shouldn't check for an absence of non-brace characters. An problem statement guarantees that there wouldn't be any, and surely it doesn't warrant an exception if there is one. • could you please comment about the titleCase() method – Emilio Gort Oct 1 '14 at 14:35 Assuming you have provided all input checks, you can write the string validation as public function isValidBraces($line) {
if (!is_string($line)) { throw new InvalidArgumentException("Input must be stirng."); }$braces = array(
array('[', ']'),
array('{', '}'),
array('(', ')')
)
$counters = array_fill(0, count($braces), 0);

foreach ($line as$char) {
for ($i = 0;$i < count($braces);$i++) {
$counters[i] +=$char == $braces[i][0];$counters[i] -= $char ==$braces[i][1];
// closing braces should not be first
if ($counters[i] < 0) { return false; } } } foreach ($counters as $counter) { // number of onpening and closing braces should be the same if ($counter > 0)
return false;
}

return true;
}


I also find this to be a more readable solution.

• The algorithm is incorrect and will return true for [(]). There are also syntax errors (foreach doesn't work with strings, missing semicolon, missing $s). ideone.com/eNOXOU – mjolka Oct 3 '14 at 2:30 • @mjolka, oh, I see – outoftime Oct 3 '14 at 7:01 validBraces() method review is imo complete (worth implementing @mjolka suggestion about using stack: open brace => add to stack|close brace => take from stack and compare match...). titleCase() contains some redundant & duplicated code. If you have repeating operations performed in the tree of conditions that usually means that these conditions might be connected not by its structure but with logical operators. Lowercasing exception arguments shouldn't be neccessary. You won't pass exceptions arguments like you didn't know what it's for. These are predetermined. I'd rather check if $title is actually a string because it might be user supplied argument, but that's validator's job so after all it's good you didn't do that.

My suggestion:

public function titleCase($title,$exceptions = array()) {
// $exceptions should be predetermined -> redundant lowercase conversion array_walk($exceptions, function (&$str) {$str = strtolower($str); });$words = explode(' ', $title); foreach ($words as $position => &$word) {
$capitalize = ($position == 0 || empty($exceptions) || !in_array($word, $exceptions));$word = ($capitalize) ? ucfirst(strtolower($word)) : strtolower($word); } return implode(' ',$words);
}


Note how descriptive variable condition increases readability. Also got rid of a few variables - $exceptions are still exceptions and $words are being processed and replaced instead stored separately (good place to use assign by reference).