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.
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 if (in.head.isLetter) rsiscTailRec(in.tail, lettersReversed.tail, agg + lettersReversed.head) else rsiscTailRec(in.tail, lettersReversed, agg + in.head) } rsiscTailRec(in, in.filter(_.isLetter).reverse) } rsiscTailRec(in) //> res1: String = c!b3a,d.cba }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[1]; srev(s, s+strlen(s)-1, isalpha); printf("%s\n", s); }And some Haskell:
Haskell:
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)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)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) [] endHere is a Common Lisp solution:
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) ;; --> :successI’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!b3cAnother 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… :-)
//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'; }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'; }@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'; } }@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.
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.
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);
}
}
Sorry guys, I stuffed the indentation on that one.
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); } }@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.
Reblogged this on anutech.
@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.
@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. ^_^
http://codepad.org/qNmEkqgy
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[1]; 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[1] << "\n"; p++; q--; } } }The output is quite pretty:
Probably doesn’t deal with combining characters properly though…