Algorithmic Reversals

20 03 2011

Consider the problem of taking a string and using PHP to display it in reverse — algorithmically, i.e without using one of those convenient, fast built-ins. I’m going to show a few ways you might do this using the initial demo string of “The rain in Spain stays mainly in the plain.” First, let’s see what the result should look like by using strrev(), as follows:

```\$str = "The rain in Spain stays mainly in the plain.";
echo strrev( \$str );
// result: .nialp eht ni ylniam syats niapS ni niar ehT
```

Now, let’s attempt to achieve the same result but this time without the benefit of strrev(), Here’s one way below:

```function reverseString( \$str ){
\$retval = '';
for(\$i=(strlen(\$str)-1), \$max = 0; \$i >= \$max; \$i--)
{
\$retval .= \$str[\$i];
}
return \$retval;
}
echo reverseString( \$str );
```

What the code does is to display each letter or character in the string starting with the last one,first, namely the period. You might possibly run into an interviewer, as I have, who asks that you take a stronger algorithmic approach and avoid using strlen(). Here’s that sort of solution:

```function getStrLen( \$str ){
\$str_length = 0;
for(\$i=0; isset( \$str[ \$i] ); \$i++) {
\$str_length++;
}
return \$str_length;
}
function reverseStringNu( \$str ){
\$retval = '';
for(\$i=(getStrLen( \$str ) - 1), \$max = 0; \$i >= \$max; \$i--){
\$retval .= \$str[\$i];
}
return \$retval;
}
echo reverseStringNu( \$str );
```

If the interviewer is against your using isset(), be of good courage because you can get by without it. You could use the Standard PHP Library, as I do below:

```function getStrLenSPL(\$str)
{
\$str_length = 0;
\$arrayStr = str_split( \$str );
\$arrayobject = new ArrayObject(\$arrayStr);
\$iterator = \$arrayobject->getIterator();
while ( \$iterator->valid() ) {
\$str_length++;
\$iterator->next();
}
return \$str;
}
function reverseStringSPL( \$str )
{
\$retval = '';
for(\$i=(getStrLenSPL(\$str) - 1), \$max = 0; \$i >= \$max; \$i--)
{
\$retval .= \$str[\$i];
}
return \$retval;
}
echo reverseStringSPL( \$str );
```

While strings can be handled using array syntax when you need a string to actually be converted into an array,then str_split is a most handy function. Using explode is not an option because it no longer works with an empty string. The iterator object iterates over the array and the while loop remains in effect as long as the next element index in the array is valid.

What is interesting is that isset() checks to see if the array index exists and if the value of the element is not null. But the iterator of the ArrayObject only checks to see if an array index exists and is unconcerned about its value which may be null. Here’s an example:

```\$a = array(1,null,3);
\$arrayobject = new ArrayObject(\$a);
\$iterator = \$arrayobject->getIterator();
\$str_length=0;
while ( \$iterator->valid() ) {
\$str_length++;
\$iterator->next();
}
echo \$str_length; //array's length: 3
```

Returning back to the issue of reversal, how about if we reverse the order of the words in a string? For this purpose I’ve chosen a string with a bit more punctuation than our previous demo string. Here’s the new string:

```\$str = 'The best things in life are free (ha!), you must be joking!';
```

An easy, fast way to reverse the words would be the following snippet:

```echo implode(array_reverse(explode( \$str ) ) );
```

Now let’s take an algorithmic approach. We could do something like the following:

```\$a = explode(' ',\$str);
for(\$i=(count(\$a) - 1), \$max=0; \$i >= \$max; \$i--) {
echo \$a[\$i] . ' ';
}
```

It is a more algorithmic approach but it does have a weakness that could be a problem. Suppose you wanted only the words in reverse order. With the above code, you get words, plus punctuation, in the result below:

joking! be must you (ha!), free are life in things best The

You might wish instead to use the PHP function strtok() which takes a string and views it as a component of strings, each marked by one or more word delimiters. The first time you call the function, you need to specify the string and any delimiters, too. On subsequent calls, just passing the string of delimiter(s) as a parameter is sufficient. Initially, I used two arrays and then I decided to go with just one to put the words in a string in reverse order, as follows:

```function getJustWords( \$str )
{
\$a = array();
// get first token
\$a[] = strtok(\$str,' !(),');
// get all subsequent tokens
while (\$token = strtok(' !(),') ) {
\$a[] = \$token;
}
return \$a;
}
function getStopValue( \$max )
{
\$stop = 0;
if ((\$max % 2 ) == 0) {
\$stop = (\$max/2) + 1;
}
else
if (\$max % 2 ) {
\$stop = ceil(\$max/2);
}
return \$stop;
}

function Swap2Reverse( \$str )
{
\$a = getJustWords( \$str );
\$max = ( count( \$a ) ) - 1;
\$stop = getStopValue( \$max );
\$temp = '';
for(\$i = \$max,\$k=0; \$k != \$stop; \$i--,\$k++) {
\$temp = \$a[\$k];
\$a[\$k] = \$a[\$i];
\$a[\$i] = \$temp;
if (\$k == \$stop) break;
}
return implode(\$a, ' ');
}
echo Swap2Reverse( \$str );

```

2 responses

11 07 2011

)-: .ti dekil yllaer I

.B nhoJ

11 07 2011

John,