4.14　用脚本检验回文字符串

初次C语言编程实验课中的一个练习就是检验某个字符串是否为回文1。这则攻略的目的就是为了告诉你如何解决类似的问题，即如何在文本中重复匹配之前的样式。

1 回文（palindrome）可以是单词、短语、数字等，其特点是从任何一个方向读来，无论从左至右，还是从右至左，都会得到同样的结果，例如acca、“Was it a rat I saw?”以及5885等。

4.14.1　预备知识

sed命令能够记住之前匹配的子样式（sub pattern）。这被称为反向引用。我们可以借助这项功能解决回文问题。而在Bash中，这个问题的解决方法也不止一种。

4.14.2　工作原理

sed能够记得之前匹配的正则表达式，这样一来，我们就可以判断字符串中是否存在重复的字符。这种能够记忆并引用之前所匹配样式的能力就是所谓的反向引用。

让我们看看如何利用反向引用轻松地解决之前的回文问题。例如：

  1. $ sed -n '/\(.\)\1/p' filename

(.) 的作用是记录 () 中的子串。这里出现的 .（点号）是sed用于匹配单个字符的正则表达式。

\1 对应 () 中匹配的第一处内容，\2 对应第二处匹配，因此我们就可以记录多个 ( ) 所匹配的内容。( ) 以 () 的形式出现，表明(和)并不是普通的字符，而是有着特殊的含义。

这条sed语句会打印出所有匹配样式的连续的两个相同字符。

所有的回文字的结构特征如下。

  • 如果字符数是偶数，那么它在结构上表现为：一个字符序列连着另一个字符相同但次序恰好相反的字符序列。2

2 例如ABBA。

  • 如果字符数是奇数，那么它在结构上表现为：一个字符序列连着另一个字符相同但次序恰好相反的字符序列，但是这两个序列中间共享一个相同的字符。3

3 例如ABA，其中的字符B就是共享的字符。

因此，要能够同时匹配这两种结构，我们在编写正则表达式时，需要使得其中有一个可选的字符。

能够匹配包含3个字符的回文字的sed正则表达式类似于下面的形式：

  1. '/\(.\).\1/p'

我们在字符序列及其逆序列之间加了一个额外的字符（.）。

下面让我们来编写一个能够匹配任意长度的回文字的脚本：

  1. #!/bin/bash
  2. #文件名: match_palindrome.sh
  3. #用途: 找出给定文件中的回文字
  5. if [ $# -ne 2 ];
  6. then
  7. echo "Usage: $0 filename string_length"
  8. exit -1
  9. fi
  11. filename=$1 ;
  13. basepattern='/^\(.\)'
  15. count=$(( $2 / 2 ))
  17. for((i=1;i<$count;i++))
  18. do
  19. basepattern=$basepattern'\(.\)' ;
  20. done
  22. if [ $(( $2 % 2 )) -ne 0 ];
  23. then
  24. basepattern=$basepattern'.' ;
  25. fi
  27. for((count;count>0;count--))
  28. do
  29. basepattern=$basepattern'\'"$count" ;
  30. done
  32. basepattern=$basepattern'$/p'
  33. sed -n "$basepattern" $filename

将字典文件作为输入获取一个给定长度的回文字列表，例如：

  1. $ ./match_palindrome.sh /usr/share/dict/british-english 4
  2. noon
  3. peep
  4. poop
  5. sees

4.14.3　工作原理

这些脚本的工作过程很简单。大多数的工作都是用来生成用于sed的正则表达式以及反向引用。

不妨通过一些例子来看看这个脚本是如何工作的。

  • 如果你想匹配一个字符，并对它进行反向引用，可以用(.)匹配单个字符，再用\1引用它。因此，要匹配一个双字符的回文并打印，我们使用：
  1. sed '/\(.\)\1/p'

为了指明必须从行首开始进行匹配，我们加入了行首标记 ^，于是，上面的命令就变成了sed '/^(.)\1/p'。其中，/p用于打印匹配内容。

  • 如果我们要匹配4个字符的回文，则使用：
  1. sed '/^\(.\)\(.\)\2\1/p'

我们用了2个(.)匹配并记录回文中前两个字符。sed会记住所有位于 (和) 中的匹配内容并能够反向引用它们。\2\1 用来对所匹配的字符以相反的顺序进行反向引用。

在上面的脚本中，我们用到了一个被称为basepattern的变量，它包含了用于sed脚本的部分内容。

根据回文中字符的数量，我们利用一个for循环生成匹配样式。

basepattern最初被初始化为basepattern='/^(.)'，它对应匹配一个单字符。for循环用来拼接 (.)和basepattern，循环次数为回文长度的一半。然后再用一个for循环以逆序的形式将反向引用拼接起来（比如 '\4\3\2\1'），循环次数为回文长度的一半。最后，为了支持奇数长度的回文，在正则表达式式与反向引用之间加上一个可选的字符（.）。

按照这种方法，就可以创建出用于匹配回文的sed匹配样式。这个匹配样式能够用来从字典文件中找出回文。

在先前的脚本中，我们用for循环生成sed命令的匹配样式。其实这个样式没必要单独生成，sed可以利用标签和goto自行实现循环结构。作为一门非常给力的语言，sed只需要使用一个复杂的单行脚本，就可以完成回文检查的任务。如果要从头解释就说来话长了。先动手试试下面的脚本：

  1. $ word="malayalam"
  2.  
  3. $ echo $word | sed ':loop ; s/^\(.\)\(.*\)\1/\2/; t loop; /^.\?$/{ s/.*/
  4. PALINDROME/ ; q; }; s/.*/NOT PALINDROME/ '
  5.  
  6. PALINDROME

如果你对sed脚本非常感兴趣，不妨看看一本专门讲解sed和awk的参考书，即由Dale Dougherty和Arnold Robbins所著的《sed 与 awk（第2版）》。

你可以利用这本书试着分析一下上面那个测试回文的单行sed脚本。

4.14.4　补充内容

下面来看看与该任务相关的其他选项或是内容。

最简单直接的方法

检查一个字符串是否是回文的最简单的方法就是使用rev命令。

rev命令接受一个文件或stdin作为输入，并逆序打印出每一行内容。

试试下面的代码：

  1. string="malayalam"
  2. if [[ "$string" == "$(echo $string | rev )" ]];
  3. then
  4. echo "Palindrome"
  5. else
  6. echo "Not palindrome"
  7. fi

rev命令可以结合其他命令来解决不同的问题。来看一个将句中所有单词顺序反转的例子：

  1. sentence='this is line from sentence'
  2. echo $sentence | rev | tr ' ' '\n' | tac | tr '\n' ' ' | rev

输出如下：

  1. sentence from line is this

在上面的单行命令中，首先用rev命令反转所有的字符，然后用tr命令将空格替换成 \n，这样就将所有的单词分隔成每行一个，接着通过tac命令将所有的行进行反转，再用tr将反转后的行合并成单行。最后，对合并后的单行使用rev，实现单词反转。

4.14.5　参考

  • 4.6节讲解了sed命令。

  • 1.15节讲解了字符串比较操作符。