Improving the readability and efficiency of parser code

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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).