## Reverse String Ignoring Special Characters

### October 30, 2015

Let’s begin with the program to reverse a string in place, without considering the requirement to ignore special characters. The simple algorithm uses two pointers, one to the left end of the string and one to the right end of the string, swapping the two characters they point to, then moving the pointers one character closer to the other at each step until they meet:

```(define (string-reverse! str)
(let loop ((lo 0) (hi (- (string-length str) 1)))
(cond ((<= hi lo) str)
(else (let ((t (string-ref str lo)))
(string-set! str lo (string-ref str hi))
(string-set! str hi t)
(loop (+ lo 1) (- hi 1)))))))```
```> (string-reverse! "a!b3c")
"c3b!a"```

Now it is obvious how to reverse a string while ignoring special characters; ensure that `lo` and `hi` never point to special characters:

```(define (string-reverse! str)
(let loop ((lo 0) (hi (- (string-length str) 1)))
(cond ((<= hi lo) str)
((not (char-alphabetic? (string-ref str lo)))
(loop (+ lo 1) hi))
((not (char-alphabetic? (string-ref str hi)))
(loop lo (- hi 1)))
(else (let ((t (string-ref str lo)))
(string-set! str lo (string-ref str hi))
(string-set! str hi t)
(loop (+ lo 1) (- hi 1)))))))```
```> (string-reverse! "a!b3c")
"c!b3a"```

This function is identical to the previous function except that two clauses have been added to the `cond` expression, one checking that the `lo` character is alphabetic and one checking that the `hi` character is alphabetic.

You can run the program at http://ideone.com/Szld2K.

Pages: 1 2

### 22 Responses to “Reverse String Ignoring Special Characters”

1. FA said

Two solutions in scala.
The first works with the indexes -> complicated, slow
The second is a faster tail recursive solution

```package programmingpraxis

// https://programmingpraxis.com/2015/10/30/reverse-string-ignoring-special-characters/
object ReverseStringIgnoringSpecialCharacters {
// Given an input string that contains both alphabetic characters and non-alphabetic characters, reverse the alphabetic characters while leaving the non-alphabetic characters in place.
// For instance, given the input string a!b3c, return the output string c!b3a, where the non-alphabetic characters ! and 3 are in their original positions.

val in = "a!b3c,d.abc"

def rsisc(in: String): String = {
val rev = in.filter(_.isLetter).reverse
val is = in.zipWithIndex.filter(_._1.isLetter).zipWithIndex
val revis = is.map(x => (rev(x._2), x._1._2))
val isall = revis ++ in.zipWithIndex.filter(!_._1.isLetter)
isall.sortBy(_._2).unzip._1.mkString

}
rsisc(in)                                       //> res0: String = c!b3a,d.cba

def rsiscTailRec(in: String): String = {
def rsiscTailRec(in: String, lettersReversed: String, agg: String = ""): String = {
if (in.isEmpty()) agg
else rsiscTailRec(in.tail, lettersReversed, agg + in.head)
}
rsiscTailRec(in, in.filter(_.isLetter).reverse)
}
rsiscTailRec(in)                                //> res1: String = c!b3a,d.cba

}
```
2. matthew said

Here’s some C++:

```#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <algorithm>

template<typename T, typename P>
void srev(T start, T end, P pred) {
while(start < end) {
if (!pred(*start)) start++;
else if (!pred(*end)) end--;
else std::swap(*start++,*end--);
}
}

int main(int argc, char *argv[]) {
char *s = argv;
srev(s, s+strlen(s)-1, isalpha);
printf("%s\n", s);
}
```

```#!/usr/bin/runghc
import Data.Char
import System.Environment

match [] _ = []
match (a:s) (b:t) =
if not (isAlpha a) then a:match s (b:t)
else if not (isAlpha b) then match (a:s) t
else b:match s t

srev s = match s (reverse s)

main = do s <- getArgs; mapM_ (print . srev) s
```
3. wert310 said

```strrev s = substAlpha s [ x | x<-(reverse s), isAlpha x ]
where substAlpha s1 "" = s1
substAlpha (x:xs) s2@(y:ys)
| isAlpha x = y : (substAlpha xs ys)
| otherwise = x : (substAlpha xs s2)
```
4. Paul said

In Python.

```def swap_alpha(txt):
alphas = reversed([t for t in txt if str.isalpha(t)])
return "".join(next(alphas) if str.isalpha(t) else t for t in txt)
```
5. mcmillhj said

Standard ML solution.

```(* reverseAlpha
Works by comparing the supplied string s to reverse(s') where s' is only the alpha characters from s.

Example: s  ="a!b3c"
s' ="cba"

output | transitions
--------------------
[]     | a!b3c -> !b3c
| cba      ba
c      | !b3c  -> b3c
| ba       ba
c!     | b3c   -> 3c
| ba       a
c!b    | 3c    -> c
| a        a
c!b3   | c     -> []
| a
c!b3a
*)
fun reverseAlpha s = let
val chars = (explode s)
val alphachars = List.filter (fn c => Char.isAlpha c) chars
fun reverseAlpha' [] [] acc = acc
| reverseAlpha' [] (r::rs) acc = acc
| reverseAlpha' (L as c::cs) [] acc = acc @ L
| reverseAlpha' (L as c::cs) (R as r::rs) acc =
if Char.isAlpha c then reverseAlpha' cs rs (acc @ [r])
else reverseAlpha' cs R (acc @ [c])
in
reverseAlpha' chars (List.rev alphachars) []
end
```
6. Informatimago said

Here is a Common Lisp solution:

```(defun reverse-string-leaving-non-alphabetic-in-place (string)
(reverse-elements-such (function alpha-char-p) string))
```

As you can see, it’s very simple. We just use a “generic” function that is not restricted to strings, or vectors, but that will work on any sequence (list, vectors, strings), and using any predicate to select the elements to be reversed.

We’ll use Common Lisp generic functions with methods to provide the variants for the various sequence subclasses (and since string is a subclass of vector, it’ll be included in the method for vector).

Also, we provide two versions of the generic function, one destructive and one non-destructive. nreverse-elements-such will reverse the sequence in place, while reverse-elements-such will create a new sequence. Of course, we will reuse the former to implement the later.

```(defgeneric nreverse-elements-such (predicate sequence)
(:method (predicate (sequence list))
(replace sequence (nreverse-elements-such predicate (coerce sequence 'vector))))
(:method (predicate (sequence vector))
(loop
:with i := 0
:with j := (1- (length sequence))
:while (< i j)
:do (cond
((not (funcall predicate (aref sequence i)))
(incf i))
((not (funcall predicate (aref sequence j)))
(decf j))
(t (rotatef (aref sequence i)  (aref sequence j))
(incf i)
(decf j))))
sequence))

(defgeneric reverse-elements-such (predicate sequence)
(:method (predicate (sequence list))
(coerce (nreverse-elements-such predicate (coerce sequence 'vector))
'list))
(:method (predicate (sequence vector))
(nreverse-elements-such predicate (copy-seq sequence))))

(defun test/reverse-elements-such ()
(let ((tests '(((1 2 3 4 5 6 7 8) oddp (7 2 5 4 3 6 1 8))
((2 4 6 8 1 3 5 7) oddp (2 4 6 8 7 5 3 1))
((1 3 5 7 2 4 6 8) oddp (7 5 3 1 2 4 6 8))
((1 2 3 4 5 6 7 8) oddp (7 2 5 4 3 6 1 8))
((1 3 5 2 4 6 7 8) oddp (7 5 3 2 4 6 1 8))
((2 4 6 8 1 3 5)   oddp (2 4 6 8 5 3 1))
((1 3 5 2 4 6 8)   oddp (5 3 1 2 4 6 8))
((1 3 5 2 4 6 8)   oddp (5 3 1 2 4 6 8))
((2 4 6 8)         oddp (2 4 6 8))
((1 3 5 7)         oddp (7 5 3 1))
((1)               oddp (1))
((2)               oddp (2))
(()                oddp ()))))
(loop :for (sequence predicate expected) :in tests
:do (let ((input (copy-seq sequence)))
(let ((output (nreverse-elements-such predicate input)))
(assert (eql input output))
(assert (equalp output expected))))
(let ((input (coerce sequence 'vector)))
(let ((output (nreverse-elements-such predicate input)))
(assert (eql input output))
(assert (equalp output (coerce expected 'vector)))))
(let ((input (copy-seq sequence)))
(let ((output (reverse-elements-such predicate input)))
(assert (or (null output) (not (eql input output))))
(assert (equalp input sequence))
(assert (equalp output expected))))
(let ((input (coerce sequence 'vector)))
(let ((output (reverse-elements-such predicate input)))
(assert (not (eql input output)))
(assert (equalp input (coerce sequence 'vector)))
(assert (equalp output (coerce expected 'vector)))))))
:success)

(test/reverse-elements-such)
;; --> :success

(defun reverse-string-leaving-non-alphabetic-in-place (string)
(reverse-elements-such (function alpha-char-p) string))

(defun test/reverse-string-leaving-non-alphabetic-in-place ()
(assert (string= (reverse-string-leaving-non-alphabetic-in-place
"reverse-string-leaving-non-alphabetic-in-place")
"ecalpni-citeba-hplanon-gni-vaelgnirts-es-rever"))
(assert (string= (reverse-string-leaving-non-alphabetic-in-place "a!b3c")
"c!b3a"))
:success)

(test/reverse-string-leaving-non-alphabetic-in-place)
;; --> :success

```
7. Jussi Piitulainen said

I’m learning Julia, at v0.4.0 now. Strings are stored as UTF-8, character length in a string varies, in-place mutation makes no sense. A vector of valid indices is neatly reversed using a bit vector to mark the positions of the alphabetic indices. The resulting index gives the result.

```"""Reverses alphabetically, leaving rest as is."""
function ralph(s::AbstractString)
x = collect(eachindex(s))
v = falses(length(x))
v[find(k -> isalpha(s[k]), x)] = true
x[v] = reverse(x[v])
s[x]
end

let s = "Tämä! on testi. Väli-merkein!?"
println(s)
println(ralph(s))
end

# printlns:
# Tämä! on testi. Väli-merkein!?
# niek! re miläV. itse-tnoämäT!?

let s = "c!b3a"
println(s)
println(ralph(s))
end

# printlns:
# c!b3a
# a!b3c
```
8. Globules said

Another Haskell solution. Similar to the Lisp version, we write a reversal function that takes a predicate indicating which elements to reverse and which to leave in their original positions. We then use it to define functions to reverse letters of a string and odd numbers in a list of numbers. (Arguably, the revPred function suffers from a round of code golf. It’s a sickness… :-)

```import Data.Bool (bool)
import Data.Char (isLetter)
import Data.List (mapAccumR)

-- Reverse only those elements of a list matching a predicate, p, keeping
-- non-matching elements in their original positions.
revPred :: (a -> Bool) -> [a] -> [a]
revPred p xs = snd \$ mapAccumR step (filter p xs) xs
where step ps x = bool (ps, x) (tail ps, head ps) (p x)

-- Reverse only the letters of a string, keeping non-letters in their original
-- positions.
revLets :: String -> String
revLets = revPred isLetter

-- Reverse only the odd numbers in a list, keeping even numbers in their
-- original positions.
revOdds :: Integral a => [a] -> [a]
revOdds = revPred odd

main :: IO ()
main = do
putStrLn \$ revLets "a!b3c"
putStrLn \$ revLets "Tämä! on testi. Väli-merkein!?"
print \$ revOdds [0..5 :: Int]
```
```\$ ./revpred
c!b3a
niek! re miläV. itse-tnoämäT!?
[0,5,2,3,4,1]
```
9. fisherro said
```//https://programmingpraxis.com/2015/10/30/reverse-string-ignoring-special-characters/

// This solution is verbose, but solves the problem in an interesting way.
//
// We create a Sort_proxy object that stores a pointer to the original
// elements. We create a swap member function that swaps the original values
// in-place. Then we create a global override for swap that calls our member
// function, because that's what std::reverse will use.
//
// We create a std::vector of these Swap_proxy objects. We initialize it with
// proxies to the alpha characters in the target string.
//
// Now, when we reverse the vector, rather than sorting the proxy objects
// themselves, it sorts the alpha charaters in the original string.
//
// Requires C++11.

#include <string>
#include <vector>
#include <algorithm>
#include <cctype>
#include <iostream>

template<typename T>
class Sort_proxy {
public:
Sort_proxy(T* tp = nullptr): p(tp) {}

void swap(Sort_proxy& that)
{
T t = *(that.p);
*(that.p) = *p;
*p = t;
}

private:
T* p;
};

template<typename T>
void swap(Sort_proxy<T>& lhs, Sort_proxy<T>& rhs)
{
lhs.swap(rhs);
}

int main()
{
std::string s("a!b3c");
std::vector<Sort_proxy<char>> v;
for (auto& c: s) if (isalpha(c)) v.push_back(Sort_proxy<char>(&c));
std::reverse(v.begin(), v.end());
std::cout << s << '\n';
}
```
10. fisherro said

Another, more straight-forward solution…

```//https://programmingpraxis.com/2015/10/30/reverse-string-ignoring-special-characters/
#include <string>
#include <algorithm>
#include <iterator>
#include <cctype>
#include <iostream>

int main()
{
std::string s1("a!b3c");
//Copy just the alpha characters into a second string.
std::string s2;
std::copy_if(s1.begin(), s1.end(), std::back_inserter(s2), ::isalpha);
//Reverse the alpha characters.
std::reverse(s2.begin(), s2.end());
//Substitute the alpha characters back into the original string.
std::transform(s1.begin(), s1.end(), s1.begin(),
[&s2, i = 0UL](char c) mutable {
return isalpha(c)? s2[i++]: c;
});
std::cout << s1 << '\n';
}
```
11. matthew said

@fisherro: Nice ingenious solution. We can extend your proxy idea to an outer container of iterators over the inner container, with a suitable iterator class that acts as a proxy for the inner elements. Now we can eg. sort all digits as well as reversing just the alphabetic characters:

```#include <vector>
#include <string>
#include <cctype>
#include <iterator>
#include <algorithm>
#include <iostream>

template<template <class...> class InnerCont,
template <class...> class OuterCont,
typename T>
class ProxyCont {
private:
typedef InnerCont<T> Inner;
typedef typename Inner::iterator InnerIter;
typedef OuterCont<InnerIter> Outer;
typedef typename Outer::iterator OuterIter;
typedef typename OuterIter::iterator_category OuterIterCat;
typedef typename OuterIter::difference_type OuterIterDiff;
public:
typedef T value_type;
class iterator: public std::iterator<OuterIterCat, char> {
public:
iterator(OuterIter it_) : it(it_) {}
value_type &operator*() { return **it; }
iterator operator--() { return iterator(--it); }
iterator operator++() { return iterator(++it); }
friend iterator operator+(iterator it, int n) { return iterator(it.it + n); }
friend iterator operator-(iterator it, int n) { return iterator(it.it - n); }
friend OuterIterDiff operator-(iterator it1, iterator it2) { return it1.it - it2.it; }
friend bool operator==(iterator it1, iterator it2) { return it1.it == it2.it; }
friend bool operator!=(iterator it1, iterator it2) { return it1.it != it2.it; }
friend bool operator<(iterator it1, iterator it2) { return it1.it < it2.it; }
private:
OuterIter it;
};
iterator begin() { return iterator(a.begin()); }
iterator end() { return iterator(a.end()); }
void push_back(InnerIter it) { a.push_back(it); }
private:
Outer a;
};

int main(int argc, char *argv[])
{
for (int i = 1; i < argc; i++) {
std::string s(argv[i]);
ProxyCont<std::basic_string,std::vector,char> alphas;
ProxyCont<std::basic_string,std::vector,char> nums;
for (auto it = s.begin(); it != s.end(); it++) {
if (std::isalpha(*it)) alphas.push_back(it);
else if (std::isdigit(*it)) nums.push_back(it);
}
std::reverse(alphas.begin(), alphas.end());
std::sort(nums.begin(), nums.end());
std::cout << s << '\n';
}
}
```
12. fisherro said

@matthew Very nice!

I’m not sure if it is ever practical, but I like the fact that you could use this to std::sort a std::list in-place by proxying through a std::vector.

13. fisherro said

It occurs to me that my second solution is not guaranteed to work. Because std::transform does not guarantees the order in which it transforms the elements. It should use std::for_each instead.

14. Davo said

package reversestring;

public class ReverseString {
static String input = “a!b3c”;

public static void main(String[] args) {
int stringLength = input.length();
int currentAlphaindex = 0;
char currentChar = ‘a’;
String letters = “”;
String output = “”;
int replacementCount = 0;
char[] alpha = new char[stringLength];
int[] alphaIndex = new int[stringLength];
char[] fullText = new char[stringLength];

for (int i = 0; i = 0; i–){
letters = letters + alpha[i];
letters = letters.trim();
}
for(int i = 0; i = 0)){
fullText[alphaIndex[i]] = letters.charAt(replacementCount);
replacementCount++;
}
output = output + fullText[i];
}
System.out.println(“input: ” + input + “\noutput: ” + output);
}
}

15. Davo said

Sorry guys, I stuffed the indentation on that one.

16. Davo said

attempt number 2

```
package reversestring;

public class ReverseString {
static String input = "a!b3c";

public static void main(String[] args) {
int stringLength = input.length();
int currentAlphaindex = 0;
char currentChar = 'a';
String letters = "";
String output = "";
int replacementCount = 0;
char[] alpha = new char[stringLength];
int[] alphaIndex = new int[stringLength];
char[] fullText = new char[stringLength];

for (int i = 0; i < stringLength; i++){
currentChar = input.charAt(i);
fullText[i] = currentChar;
alphaIndex[i] = -1;
if(Character.isLetter(currentChar)){
alpha[currentAlphaindex] = currentChar;
alphaIndex[currentAlphaindex] = i;
currentAlphaindex++;
}
}
for (int i = (stringLength - 1); i >= 0; i--){
letters = letters + alpha[i];
letters = letters.trim();
}
for(int i = 0; i < stringLength; i++){
if((alphaIndex[i] >= 0)){
fullText[alphaIndex[i]] = letters.charAt(replacementCount);
replacementCount++;
}
output = output + fullText[i];
}
System.out.println("input: " + input + "\noutput: " + output);
}
}
```
17. matthew said

@fisherro: Thanks. I liked that possible use too. Incidentally, I think my iterator operator++ and operator– should return a *this reference rather than a new iterator (and I don’t think the template template parameter is necessary for the inner container).

I wonder if we could define an inner container that iterates over the contents of a UTF-8 string.

18. fisherro said

@matthew

A UTF-8 iterator might be tricky. My first instinct is to use std::string as the value_type. But the specification wants an iterator’s operator* to return a reference. (And operator-> requires returning a pointer.) Maybe it could be faked with a proxy object?

I think using char32_t has the same issue.

A string_view might work, though. It can point directly to the original bytes.

19. fisherro said

@matthew
Here’s a rough first pass of an iterator adapter for walking the characters in a UTF-8 string. It would be better as a container adapter. Well…probably a lot about it could be better. ^_^

20. matthew said

Yes, looks tricky wrapping up UTF-8 in an iterable class. I was musing on the idea of dealing with UTF-8 in-place, and came up with this. It uses the well-known trick for reversing a sequence of blocks in memory by reversing each block individually, then the whole sequence. Seems a waste of electrons to do the full reverse when the outer blocks are the same size so we deal with that specially:

```#include <string.h>
#include <wchar.h>
#include <wctype.h>
#include <locale.h>
#include <iostream>
#include <vector>
#include <algorithm>

// Reverse from p to q, inclusive of q.
void reverse(char *p, char *q) {
while(p < q) std::swap(*p++,*q--);
}

// Swap p-q with r-s, excluding q and s
void swap2(char *p, char *q, char *r, char *s) {
// q-p == s-r
while(p < q) std::swap(*p++,*r++);
}

// Same, when blocks are different sizes
void swap3(char *p, char *q, char *r, char *s) {
// q-p != s-r
reverse(p,q-1);
reverse(q,r-1);
reverse(r,s-1);
reverse(p,s-1);
}

int main(int argc, char *argv[]) {
setlocale(LC_CTYPE, "");
char *s = argv;
std::vector<char*> chars;
std::vector<int> alphas;
mbstate_t mbstate = mbstate_t();
int len = strlen(s)+1;
while (true) {
chars.push_back(s);
wchar_t wc;
ssize_t nbytes = mbrtowc(&wc, s, len, &mbstate);
if (nbytes <= 0) break; // No error check!
alphas.push_back(iswalpha(wc));
s += nbytes;
len -= nbytes;
}
int p = 0, q = alphas.size()-1;
while (p < q) {
if (!alphas[p]) p++;
else if (!alphas[q]) q--;
else {
int diff = (chars[q+1]-chars[q])-(chars[p+1]-chars[p]);
if (diff == 0) {
swap2(chars[p],chars[p+1],chars[q],chars[q+1]);
} else {
swap3(chars[p],chars[p+1],chars[q],chars[q+1]);
for (int i = p+1; i <= q; i++) chars[i] += diff;
}
std::cout << argv << "\n";
p++; q--;
}
}
}
```

The output is quite pretty:

```\$ ./mbc "Forʒyf ūs ūre ʒyltas ✠ swāswā wē forʒyfað ðāmþe wið ūs āʒyltað."
Forʒyf ūs ūre ʒyltas ✠ swāswā wē forʒyfað ðāmþe wið ūs āʒyltað.
ðorʒyf ūs ūre ʒyltas ✠ swāswā wē forʒyfað ðāmþe wið ūs āʒyltaF.
ðarʒyf ūs ūre ʒyltas ✠ swāswā wē forʒyfað ðāmþe wið ūs āʒyltoF.
ðatʒyf ūs ūre ʒyltas ✠ swāswā wē forʒyfað ðāmþe wið ūs āʒylroF.
ðatlyf ūs ūre ʒyltas ✠ swāswā wē forʒyfað ðāmþe wið ūs āʒyʒroF.
ðatlyf ūs ūre ʒyltas ✠ swāswā wē forʒyfað ðāmþe wið ūs āʒyʒroF.
ðatlyʒ ūs ūre ʒyltas ✠ swāswā wē forʒyfað ðāmþe wið ūs āfyʒroF.
ðatlyʒ ās ūre ʒyltas ✠ swāswā wē forʒyfað ðāmþe wið ūs ūfyʒroF.
ðatlyʒ ās ūre ʒyltas ✠ swāswā wē forʒyfað ðāmþe wið ūs ūfyʒroF.
ðatlyʒ ās ūre ʒyltas ✠ swāswā wē forʒyfað ðāmþe wið ūs ūfyʒroF.
ðatlyʒ ās ūðe ʒyltas ✠ swāswā wē forʒyfað ðāmþe wir ūs ūfyʒroF.
ðatlyʒ ās ūði ʒyltas ✠ swāswā wē forʒyfað ðāmþe wer ūs ūfyʒroF.
ðatlyʒ ās ūði wyltas ✠ swāswā wē forʒyfað ðāmþe ʒer ūs ūfyʒroF.
ðatlyʒ ās ūði weltas ✠ swāswā wē forʒyfað ðāmþy ʒer ūs ūfyʒroF.
ðatlyʒ ās ūði weþtas ✠ swāswā wē forʒyfað ðāmly ʒer ūs ūfyʒroF.
ðatlyʒ ās ūði weþmas ✠ swāswā wē forʒyfað ðātly ʒer ūs ūfyʒroF.
ðatlyʒ ās ūði weþmās ✠ swāswā wē forʒyfað ðatly ʒer ūs ūfyʒroF.
ðatlyʒ ās ūði weþmāð ✠ swāswā wē forʒyfað satly ʒer ūs ūfyʒroF.
ðatlyʒ ās ūði weþmāð ✠ ðwāswā wē forʒyfas satly ʒer ūs ūfyʒroF.
ðatlyʒ ās ūði weþmāð ✠ ðaāswā wē forʒyfws satly ʒer ūs ūfyʒroF.
ðatlyʒ ās ūði weþmāð ✠ ðafswā wē forʒyāws satly ʒer ūs ūfyʒroF.
ðatlyʒ ās ūði weþmāð ✠ ðafywā wē forʒsāws satly ʒer ūs ūfyʒroF.
ðatlyʒ ās ūði weþmāð ✠ ðafyʒā wē forwsāws satly ʒer ūs ūfyʒroF.
ðatlyʒ ās ūði weþmāð ✠ ðafyʒr wē foāwsāws satly ʒer ūs ūfyʒroF.
ðatlyʒ ās ūði weþmāð ✠ ðafyʒr oē fwāwsāws satly ʒer ūs ūfyʒroF.
ðatlyʒ ās ūði weþmāð ✠ ðafyʒr of ēwāwsāws satly ʒer ūs ūfyʒroF.
```
21. matthew said

Probably doesn’t deal with combining characters properly though…