算法实例练习记录——括号匹配是否完整问题 [链表实现栈 + 栈的应用]（JAVA实现）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法实例练习记录——括号匹配是否完整问题 [链表实现栈 + 栈的应用]（JAVA实现），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4366字，纯文字阅读大概需要7分钟。
内容图文
括号匹配是否完整问题 [链表实现栈 + 栈的应用]
本篇博文涉及两个内容：
-
用单向链表实现——栈的功能
-
用栈的特点实现——括号匹配（或者叫字符匹配）
第一个问题：单向链表实现——栈的功能（后进先出）
为了实现栈的后进先出功能，选择链表的头节点（head）比较好操作，入栈和出栈操作如下：
- 入栈---push（item）：在链表头部head节点处，完成入栈。
- 出栈---pop（）：在链表头部head节点处，完成出栈，并返回出栈节点的item的值。
下面是具体实现，功能包括——判控、长度计算、入栈、出栈，不包括遍历。
//链表实现栈的操作
//栈的特点——后进先出
//结合单向链表和栈的特点，入栈push（）和出栈pop（）操作，只能在链表的一端完成，这里我们选择都在链表的表头完成即可。
//isEmpty（）判断栈是否为空
//size（）计算栈的长度
public class ItemStack {
private Node head;
private int N;
ItemStack(){
this.head=new Node();
this.N=0;
}
private class Node{
char item;
Node next;
}
//判断栈空
public boolean isEmpty() {
return head==null;
}
//返回链表节点数量
public int size() {
return N;
}
//入栈操作,添加在链表头部
public void push(char item) {
Node node=new Node();
node.item=item;
node.next=head;
head=node;
N++;
}
//出栈操作，从表头删除节点
public char pop() {
char item=head.item;
head=head.next;
N--;
return item;
}
}
第二个问题：用栈的特点实现——括号匹配（或者叫字符匹配）
用上面我们创建好的——ItemStack，来实现匹配问题。
问题比较简单，直接上代码：
public class ParenthesesItemStack {
//利用java的泛型，创建一个存储char的栈--->strstack
private ItemStack strstack;
//构造函数，对strstack栈进行初始化。
ParenthesesItemStack(){
this.strstack=new ItemStack();
}
//判断函数parentheses（str），对str字符串是否符合规则，进行判断，并返回boolean值。
public boolean parentheses(String str) {
boolean flag=false;
char c;
//如果传入的字符串为空串，直接返回false。
if(str.length()==0) {
return false;
}
//判断功能的核心代码
for(int i=0; i<str.length(); i++) {
//逐个获取字符串str中的字符
c=str.charAt(i);
//用switch多分枝选择结构实现规则判定
switch(c) {
//字符c都为左括弧时，做入栈操作。
case '(':
case '[':
case '{':
strstack.push(c);
break;
//字符c为右括弧时,做出栈操作，分情况判断，三种情况--->),],}，看出栈字符和c是否匹配。
case ')':
if(!strstack.isEmpty()) flag=strstack.pop()=='('?true:false;
else flag=false;
break;
case ']':
if(!strstack.isEmpty()) flag=strstack.pop()=='['?true:false;
else flag=false;
break;
case '}':
if(!strstack.isEmpty()) flag=strstack.pop()=='{'?true:false;
else flag=false;
break;
//字符c，不是括号时，直接返回false。
default:
return false;
}
}
//字符串循环结束后，判断栈是否为空，为空-->即说明匹配成功。
if(strstack.isEmpty()) {
flag=true;
}else flag=false;
return flag;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Parentheses p=new Parentheses();
System.out.print(p.parentheses("[]{{{()[]}}}"));
}
}
下面的代码是直接用JDK自带的栈Stack容器类来实现的，仅供参考——其实都一样的。
简单说就是对 [栈——后进先出] 的相关知识的理解和运用。
import java.util.Stack;
/*
* 对于给定的一个由括号组成的字符串，判定其中的括号是否配对完整。
* 例如，对于 [()]{}{[()()]()} 程序应该打印 true，对于 [(]) 则打印 false。
*
*/
//核心思想就是用栈satck的后进先出原则，来实现这个功能。
//程序比较简单，这里就不再赘述了，直接上代码。
public class Parentheses {
//利用java的泛型，创建一个存储char的栈--->strstack
private Stack<Character> strstack;
//构造函数，对strstack栈进行初始化。
Parentheses(){
this.strstack=new Stack<Character>();
}
//判断函数parentheses（str），对str字符串是否符合规则，进行判断，并返回boolean值。
public boolean parentheses(String str) {
boolean flag=false;
char c;
//如果传入的字符串为空串，直接返回false。
if(str.length()==0) {
return false;
}
//判断功能的核心代码
for(int i=0; i<str.length(); i++) {
//逐个获取字符串str中的字符
c=str.charAt(i);
//用switch多分枝选择结构实现规则判定
switch(c) {
//字符c都为左括弧时，做入栈操作。
case '(':
case '[':
case '{':
strstack.push(c);
break;
//字符c为右括弧时,做出栈操作，分情况判断，三种情况--->),],}，看出栈字符和c是否匹配。
case ')':
if(!strstack.isEmpty()) flag=strstack.pop()=='('?true:false;
else flag=false;
break;
case ']':
if(!strstack.isEmpty()) flag=strstack.pop()=='['?true:false;
else flag=false;
break;
case '}':
if(!strstack.isEmpty()) flag=strstack.pop()=='{'?true:false;
else flag=false;
break;
//字符c，不是括号时，直接返回false。
default:
return false;
}
}
//字符串循环结束后，判断栈是否为空，为空-->即说明匹配成功。
if(strstack.isEmpty()) {
flag=true;
}else flag=false;
return flag;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Parentheses p=new Parentheses();
System.out.print(p.parentheses("[]{{()[]}}"));
}
}
内容总结
以上是互联网集市为您收集整理的算法实例练习记录——括号匹配是否完整问题 [链表实现栈 + 栈的应用]（JAVA实现）全部内容，希望文章能够帮你解决算法实例练习记录——括号匹配是否完整问题 [链表实现栈 + 栈的应用]（JAVA实现）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】