栈的应用实例之——括号匹配

2019-11-06 06:22:51

字体：大中小

来源：转载

供稿：网友

在上一篇博文中我们利用后进先出的数据结构栈成功地实现了十进制数向二进制数的转换。

在这篇博客中我将和大家一起实现Stack的另一个重要的应用，检测序列中括号是否匹配。

假设我们现在面临着一个问题：

一个给出序列中包含着三种括号：圆括号（）、方括号 [ ] 、花括号 { } ，这些括号在序列中嵌套排序的顺序随意。

序列： [ ( { } ) ( ) ]为合法的序列； { ( ] }或 ( ) } {均为非法序列。

那么思考一下，我么如何能够利用栈这种后进先出的数据结构实现上面的这个任务呢？

其实算法很简单：我们首先构建一个空栈；读入整个序列；如果符号是左括号包括 ( 、[ 或 { ，我们将它压入栈中；如果符号是右括号，我们首先检查栈是否为空，若为空则该序列必定不合法；若不为空，则与栈顶的元素进行匹配，匹配成功则弹出该栈顶元素并继续读取下个符号；若匹配失败则该序列必定不合法；当这个序列都被读完后，若栈为空则说明该序列为合法序列，否则该序列非法。

java实现该算法的代码如下：

public class ParenthesesMatchTest { public static void main(String[] args) { // TODO Auto-generated method stub String seq1 = "[()]{}{[)}[]()}"; String seq2 = "{[]({}[]){[()]}}"; System.out.PRintln("seq1 matches is "+isMatched(seq1)); System.out.println("seq2 matches is "+isMatched(seq2)); } private static boolean isMatched(String seq) { // TODO Auto-generated method stub MyArrayStack<String> stack = new MyArrayStack<String>(); while(seq.length()>0){ //取出字符串的首字母 String c = seq.substring(0,1); seq = seq.substring(1); //如果字母是左括号，则压入栈中 if(c.equals("(") || c.equals("[") || c.equals("{")) stack.push(c); //如果字母是右括号 else if(c.equals(")") || c.equals("]") || c.equals("}")){ if(stack.isEmpty()) return false; //如果左右括号匹配，就将左括号从栈中弹出 if(matches(stack.peek(),c)) stack.pop(); else return false; } } //如果栈空则说明符号序列合法，如果栈不为空则说明符号序列不合法 return stack.isEmpty(); } private static boolean matches(String left, String right){ if(left.equals("(")){ if(right.equals(")")) return true; else return false; } else if(left.equals("[")){ if(right.equals("]")) return true; else return false; } else { if(right.equals("}")) return true; else return false; } }}

本博文源码下载地址，内含MyArrayStack源码及括号匹配源码，欢迎下载测试。

上一篇：3Sum问题及解法

下一篇：关于计算1^2+2^2+……+n^2的和，用公式n(n+1)(2n+1)/6计算，复杂度为O（1）.