抛砖引玉 假设输入只有字母和数字

#!/usr/bin/python
import re

def revert_string_recursively(strings):
  if len(strings) <= 0:
    return ''
  return strings[-1] + revert_string_recursively(strings[0:-1])

def main():
  with open('case.txt') as f:
    for line in f:
      sub_strings = re.findall('\d+|\D+', line.strip('\n'))
      print revert_string_recursively(sub_strings)

if __name__ == '__main__':
  main()

case.txt:

APPLE1234BOOK5678
APPLE
1234

1楼 @amosji 谢谢回复！看了代码，方法是先把字符串根据字母，数字拆分成字符串数组，再通过递归，从后往前连接。如果不事先拆分字符串的话，实现起来比较复杂吧。

2楼 @sadcat 不拆分字符串的方法。

    public class WeightedChar : IComparable<WeightedChar>
    {
        public Char Char;
        public double Weight;

        public int CompareTo(WeightedChar other)
        {
            return this.Weight.CompareTo(other.Weight);
        }

        public static List<WeightedChar> Build(String txt)
        {
            // 给每个字符赋个权重。这里就不用递归了。那位有兴趣可以将这里转换为递归。
            List<WeightedChar> list = new List<WeightedChar>();
            if(String.IsNullOrEmpty(txt) == false)
            {
                double length = txt.Length;
                int level = 0;
                for (int idx = 0; idx < length; idx++)
                {
                    if (idx > 0 && Char.IsDigit(txt[idx]) != Char.IsDigit(txt[idx - 1])) level++;
                    list.Add(new WeightedChar { Char = txt[idx], Weight = -level + idx / length });
                }
            }

            return list;
        }

        public static void Test(String txt = "APPLE1234BOOK5678")
        {
            List<WeightedChar> list = Build(txt);
            list.Sort(); // SORT 可以用递归实现。直接调用库函数了。
            StringBuilder sb = new StringBuilder();
            foreach (WeightedChar item in list) sb.Append(item.Char);
            String result = sb.ToString();
            Console.WriteLine(result); // 5678BOOK1234APPLE
        }
    }

另一个版本，谁来改成递归版：

        public static void Insert(StringBuilder txt, Char c)
        {
            for(int i = 0; i < txt.Length; i++)
            {
                if( Char.IsDigit(txt[i]) != Char.IsDigit(c))
                {
                    txt.Insert(i, c);
                    return;
                }
            }
            txt.Append(c);
        }

        public static void Test2(String txt = "APPLE1234BOOK5678")
        {
            StringBuilder sb = new StringBuilder();
            foreach(Char c in txt)
            {
                Insert(sb, c);
            }
            Console.WriteLine(sb);
            //5678BOOK1234APPLE
        }

pythonic string reversing

def reverse_words(s):
  i,l,r = 0,len(s),''

  for j in range(1,l+1):
    if j == l or s[j-1].isdigit() != s[j].isdigit():
      r += s[i:j][::-1]
      i = j

  return r[::-1]

if __name__ == '__main__':
  ss = ['APPLE1234BOOK5678','1234','abc', 'abc1234', '1234abc']
  for s in ss:
    print "%s -> %s" % (s, reverse_words(s))

不拆当然可以啦
但是你总要用某种方法判断哪一块是单词 哪一块是数字
下面的code 是先把每一个单词或数字反转 再把整个字符串反转
example: APPLE1234BOOK5678 -> ELPPA1234BOOK5678 -> ELPPA4321BOOK5678 -> ELPPA4321KOOB5678 -> ELPPA4321KOOB8765 -> 5678BOOK1234APPLE
其中反转字符串是递归实现的

#include <stdio.h>
#include <ctype.h>
void revert_sub_string(char *string, int start, int end) {
  if (start >= end) return;

  char temp = string[start];
  string[start] = string[end];
  string[end] = temp;
  revert_sub_string(string, start+1, end-1);
}

void revert_string_by_word(char *string) {
  int start = 0, i, string_length = 0;

  for (i = 0; string[i] != ''; i++) {
    if (isdigit(string[i]) != isdigit(string[i+1])) {
      revert_sub_string(string, start, i);
      start = i+1;
    }
    string_length++;
  }

  if (start != 0)
    revert_sub_string(string, 0, string_length-1);
}

int main() {
  char test_string[1024];
  while(scanf("%s", test_string) == 1) {
    revert_string_by_word(test_string);
    printf("%s\n", test_string);
  }
  return 0;
}

- (void)revert:(NSString*)str start:(int)index
{
    if ( index>=str.length )
    {
        return;
    }

    int len = 1;

    BOOL isNum = ( ([str characterAtIndex:index]>='0') && ([str characterAtIndex:index]<='9') );

    if ( isNum )
    {
        for ( int ind = index+1 ; ind < str.length ; ++ind )
        {
            if ( ([str characterAtIndex:ind] < '0') || ([str characterAtIndex:ind] > '9') )
            {
                break;
            }

            len++;
        }
    }
    else
    {
        for ( int ind = index+1 ; ind < str.length ; ++ind )
        {
            if ( ([str characterAtIndex:ind] < 'A') || ([str characterAtIndex:ind] > 'Z') )
            {
                break;
            }

            len++;
        }
    }

    [self revert:str start:index+len];

    NSLog(@"%@",[str substringWithRange:NSMakeRange(index, len)]);
}

测试

[self revert:@"APPLE1234BOOK5678" start:0];

2014-11-27 17:25:54.483 MMParallaxCell[7838:1199123] 5678
2014-11-27 17:25:54.484 MMParallaxCell[7838:1199123] BOOK
2014-11-27 17:25:54.484 MMParallaxCell[7838:1199123] 1234
2014-11-27 17:25:54.484 MMParallaxCell[7838:1199123] APPLE

看了 @peterwang 的解法，才知道python原来有isdigit这个函数，惭愧。python语法实在太优美了，附上我的答案：

def reverse(s):
    if len(s) <= 1:
        return s
    i = -2
    begin = s[-1]
    while -i <= len(s):
        if s[i].isdigit() != begin.isdigit():
            s = s[:i+1]
            break
        else:
            begin = s[i] + begin
            if begin == s:
                return s
        i = i - 1

    return begin + reverse(s)


input_str = raw_input("Your string: ")

print reverse(input_str)

8楼 @newguy 你的code有问题
比如1A2B 你的结果是B21A
事实上 只要输入字符串的前两个字符一个是数字一个是字母 你的结果就错啦
我想你的问题是在

if -i == len(s):  
    return s  

这里

9楼 @amosji 谢谢指出，我把那个判断去掉了，在

begin = s[i] + begin

后面加了一个判断语句。

3楼 @xiaotie 这方法还是头一次见到，先算出每个字符的权，再排序。

A       0
P       0.058823529
P       0.117647059
L       0.176470588
E       0.235294118
1       -0.705882353
2       -0.647058824
3       -0.588235294
4       -0.529411765
B       -1.470588235
O       -1.411764706
O       -1.352941176
K       -1.294117647
5       -2.235294118
6       -2.176470588
7       -2.117647059
8       -2.058823529

每次面试碰上递归就心跳加速。。。。

4楼 @xiaotie 这个挺简洁的。多谢回复。

来个sicp版：

def reverse_digits_words(ss):

    def reverse(s, pre, result):
        if len(s) == 0:
            return pre+result
        if len(pre) == 0:
            return reverse(s[1:],s[0],result)
        if pre[0].isdigit() ^ s[0].isdigit():                                                                                              
            return reverse(s,'',pre+result)
        return reverse(s[1:],pre+s[0],result)

    return reverse(ss, '', '')

5楼 @peterwang 头一回见到[::-1]，查了一下才知道这叫extended slice，学习了。

来个F#版

let reverse_digits_words ss = 
    let rec reverse s pre result = 
        let isDigit (str : string) = System.Char.IsDigit str.[0]
        let cons str1 (str2 : string) = str1 + (string str2.[0])
        match s, pre with
        | "", pre -> pre + result
        | _, "" -> reverse s.[1..] (cons "" s) result
        | s, pre when isDigit s <> isDigit pre -> reverse s "" pre + result
        | s, pre -> reverse s.[1..] (cons pre s) result
    reverse ss "" ""