🌱本专栏将会从基础开始,循序渐进,每天刷一道算法题,也请大家多多支持。数据结构虽然难,但只要肯坚持,一定能学好,希望大家都能够从中获益。
📫专栏地址: 🍇每天一道算法题专栏 🍉数据结构专栏
📫本专栏的所有代码都将更新在Gitee上,项目地址:项目地址
📫相关数据结构演示软件:链接地址
📫数据结构在线演示地址:https://visualgo.net/zh https://algorithm-visualizer.org/
准备好了吗
Let’s go!
- 栈在括号匹配中的应用
所谓括号校验匹配就是对多种类型的括号进行正确配对的校验(包括:()、[]、{})即([])或者[()]为正确的表达式,如果出现交叉则匹配失败,如[(])或([())则为不正确格式。下图是括号匹配的示意图,相同的数字表示所配对的括号:
从上图可以发现:
1️⃣:每出现一个右括号,就消耗一个左括号
2️⃣:最后出现的左括号最先被匹配
所以可以用栈的特点来解决该问题,算法演示如下:
代码如下:
public static boolean bracketCheck(String str){
LinkedStack<Character> S = new LinkedStack<Character>(); //初始化一个栈
for(int i=0;i<str.length();i++){
//如果扫描到左括号,则入栈
if(str.charAt(i) == '(' || str.charAt(i) == '[' || str.charAt(i) == '{' ){
S.push(str.charAt(i));
}else{
//扫描到右括号,且当前栈空
if(S.isEmpty()){
return false;
}
//栈顶元素出栈
char topElem = S.pop();
//判断是否匹配
if(str.charAt(i) == ')' && topElem != '('){
return false;
}
if(str.charAt(i) == ']' && topElem != '['){
return false;
}
if(str.charAt(i) == '}' && topElem != '{'){
return false;
}
}
}
//检索完全部括号后,栈空说明匹配成功
return S.isEmpty();
}
完整代码如下:
//链栈
import java.util.Scanner;
//结点
class LinkedNode<T>{
public T iData; //数据域
public LinkedNode<T> next; //指向下一个结点
public LinkedNode(T iData) {
this.iData = iData;
this.next = null;
}
public LinkedNode(T iData, LinkedNode<T> next) {
this.iData = iData;
this.next = next;
}
//输出用
@Override
public String toString() {
return "LinkedNode{" +
"iData=" + iData +
", next=" + next +
'}';
}
}
//链栈
class LinkedStack<T> {
public LinkedNode<T> first; //链表的第一个结点
//构造函数
public void LinkList() {
first = null;
}
//判断链栈是否为空
public boolean isEmpty() {
return first == null;
}
//push
public void push(T data){
LinkedNode newNode = new LinkedNode(data);
newNode.next = first;
first = newNode;
}
//pop
public T pop(){
if (first == null){
System.out.println("链表为空");
return null;
}
T front = first.iData;
first = first.next;
return front;
}
}
public class _002LinkStackTest {
public static boolean bracketCheck(String str){
LinkedStack<Character> S = new LinkedStack<Character>(); //初始化一个栈
for(int i=0;i<str.length();i++){
//如果扫描到左括号,则入栈
if(str.charAt(i) == '(' || str.charAt(i) == '[' || str.charAt(i) == '{' ){
S.push(str.charAt(i));
}else{
//扫描到右括号,且当前栈空
if(S.isEmpty()){
return false;
}
//栈顶元素出栈
char topElem = S.pop();
//判断是否匹配
if(str.charAt(i) == ')' && topElem != '('){
return false;
}
if(str.charAt(i) == ']' && topElem != '['){
return false;
}
if(str.charAt(i) == '}' && topElem != '{'){
return false;
}
}
}
//检索完全部括号后,栈空说明匹配成功
return S.isEmpty();
}
public static void main(String[] args) {
// LinkedStack integerLinkedNode = new LinkedStack();
//
// integerLinkedNode.push(1);
// integerLinkedNode.push(2);
// integerLinkedNode.push(3);
//
// while(!integerLinkedNode.isEmpty()){
// System.out.println(integerLinkedNode.pop());
// }
Scanner scanner = new Scanner(System.in);
String str = scanner.nextLine(); //测试案例:[(())[]]
System.out.println(bracketCheck(str));
}
}
代码的运行结果如下:
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)