数据结构入门（三）栈的应用

  在之前的两篇文章——数据结构入门（一）栈的实现和数据结构入门（二）栈的应用之数学表达式求值中，笔者分别介绍了“栈”这个数据结构在数的进制转换和数学表达式求值方面的应用。在本文中，笔者将会再介绍栈的三个应用，它们分别是：

判断字符串是否回文

括号匹配

行编辑程序

二叉树的深度优先遍历

  栈的结构实现可以参考数据结构入门（二）栈的应用之数学表达式求值，本文将不再具体给出。

判断字符串是否回文

  所谓回文字符串就是指正读反读均相同的字符序列，如“12321”、“aha”、“ahaha”、“清水池里池水清”均是回文，但“ahah”不是回文。通过栈这个数据结构我们将很容易判断一个字符串是否为回文。
  首先我们需要找到该字符串的中心点。对于长度为奇数的字符串，中心点就是中间的那个元素；对于长度为偶数的字符串，中心点恰好位于长度为一半的那个元素及其后一个元素的中间。接着将中心点前面的字符依次入栈，然后将当前栈中的字符依次出栈，看看是否能与 中心点之后的字符一一匹配，如果都能匹配则说明这个字符串是回文字符串，否则就不是回文字符串。
  以下是利用栈来实现判断字符串是否回文的Python代码：

# -*- coding: utf-8 -*- # using Stack to check if a string is plalindrome from Stack import Stack def isPlalindrome(words): length = len(words) flag = length//2 s = Stack() for i in range(flag): s.push(words[i]) start = flag+1 if length % 2 else flag for item in words[start:]: if s.pop() != item: return False return True def main(): words_list = ["12321", "aha", "ahaha", "清水池里池水清", "ahah"] for words in words_list: res = isPlalindrome(words) print("'%s' is plalindrome: %s" % (words, res)) main()

输出结果如下：

'12321' is plalindrome: True
'aha' is plalindrome: True
'ahaha' is plalindrome: True
'清水池里池水清' is plalindrome: True
'ahah' is plalindrome: False

括号匹配

  在字符串中，我们常常会遇到括号匹配的问题，常见的括号如下：

小括号： “(”和“）”

中括号： “[”和“]”

花括号： “{”和“}”

每一个开符号必须匹配与其对应的闭符号。以下为匹配示例：

正确: ( )(( )){([( )])}

正确: ((( )(( )){([( )])}))

错误: )(( )){([( )])}

错误: ({[])}

错误: (

  下面说明括号匹配的算法。从左至右检查每个元素，用栈S储存括号。每当遇到一个开符号时，就入栈，每当遇到闭符号时，就出栈（假设S非空），并检查两者是否匹配。如果所有元素都检查完毕，且栈S为空，那么原来的表达式括号匹配，否则就不匹配。
  下面是括号匹配的Python代码：

# -*- coding: utf-8 -*- # matching parentheses from Stack import Stack def is_matched(expr): # return True if all delimiters are properly match; False otherwise lefty = '({[' # opening delimiters righty = ')}]' # respective closing delimiters s = Stack() for c in expr: if c in lefty: s.push(c) elif c in righty: if s.is_empty(): # nothing to match with return False if righty.index(c) != lefty.index(s.pop()): # mismatched return False return s.is_empty() def main(): expr_list = ['[(5+x)-(y+z)]', '(5+x))*y', '{[1+(x+y)]}*[(3*z)]'] for expr in expr_list: Flag = is_matched(expr) print('%s is matched: %s' %(expr, Flag)) main()

输出结果如下：

[(5+x)-(y+z)] is matched: True
(5+x))y is matched: False
{[1+(x+y)]}[(3*z)] is matched: True

行编辑程序

  一个简单的行编辑程序的功能是：接收用户从终端输入的程序或数据，并存入用户的数据区。由于用户在终端上进行输入时，不能保证不出差错，因此，若在编辑程序中，“每接收一个字符即存入用户数据区”的做法是不恰当的。较好的做法是，设立一个输入缓冲区，用以接受用户输入的每一行字符，然后逐行存入用户数据区。允许用户输入出差错，并在发现有误时可以及时更正。例如，当用户发现刚刚输入的一个字符是错的时，可以补进一个退格符“#”，表示前一个字符无效；如果发现当前输入的行内差错较多或难以补救，则可以输入一个退行符“@”，表示当前行中的字符均无效。比如，假设从终端接收了两行这样的字符：

whli##ilr#e(s#*s)
outcha@putchar(*s=#++);

则实际有效的是下列两行：

while(*s)
putchar(*s++);

  行编辑程序的输出结果可用栈来解决。可设这个输入缓冲区为一个栈结构，每当从终端接受了一个字符后先做如下判别：如果它既不是退格符也不是退行符，则将该字符入栈；如果是一个退格符，则从栈顶删去一个字符；如果它是退行符，则将该栈清空。以下为实现行编辑程序的Python代码：

# -*- coding: utf-8 -*- # line edit programming from Stack import Stack # line edit programming using Stack def LineEdit(chars): s = Stack() for char in chars: if char != '\n': # line edit if char == '#': s.pop() elif char == '@': s.clear() else: s.push(char) else: # output line = [] while not s.is_empty(): line.append(s.pop()) print(''.join(line[::-1])) def main(): chars = """whli##ilr#e(s#*s) outcha@putchar(*s=#++) fi@if a=# == 'exti##it': system@ sys.tiex####exit((#) """ LineEdit(chars) main()

输出结果如下：

while(*s) putchar(*s++) if a == 'exit': sys.exit() 二叉树的深度优先遍历