文章目录

• 前言
• 例题
• 算法思想
• 算法举例
• 代码
• • 栈类
  • 括号匹配核心算法
  • 完整代码
  • 运行结果

前言

括号匹配问题算是栈应用中比较经典的问题了，在数据结构的书中还有各种考试中会出现。最近刷题的时候也遇到了，就想写一篇文章整理一下。

例题

题目来自Leetcode中国
给定一个只包括 (，)，{，}，[，] 的字符串，判断字符串是否有效。
有效字符串需满足：
1、左括号必须用相同类型的右括号闭合。
2、左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:

输入: “()”
输出: true

示例 2:

输入: “()[]{}”
输出: true

示例 3:

输入: “(]”
输出: false

示例 4:

输入: “([)]”
输出: false

示例 5:

输入: “{[]}”
输出: true

算法思想

S1：遍历输入的括号序列，如果是左括号，进入S2，如果是右括号，进入S3
S2：如果当前遍历到左括号，则入栈
S3：如果当前遍历到右括号，则出栈一个元素，看其是否与当前的右括号组成一对，如果不是，则匹配失败。或者在出栈过程中发生异常(从空栈中出栈)，也匹配失败
S4：若能顺利遍历完成，检查栈中是否还有剩余元素，如果有，则匹配失败；如果没有，则匹配成功。

算法举例

下面以(({[]}) 序列为例说明算法过程：
1、首先将这个字符串转换成字符数组，并初始化一个空栈。

2、遍历到第0个元素，(，为左括号，入栈

3、后面以此类推，遍历完第3个元素[后，栈空间应该是这样的

4、遍历到第4个元素]时，发现为右括号，此时，从栈顶出栈一个左括号，即[，刚好[与]，匹配成一对

5、以此类推，直到第6个元素)，都是匹配的

6、此时，序列已经遍历完毕，但是栈不是空的，所以原序列匹配失败。

代码

栈类

这里我使用了链栈，链表就没有自己写了，用了Java现成的LinkedList

/*** 栈类，这里使用链栈*/
class MyStack{private int num;private LinkedList<Character> data;public MyStack(){this.num = 0;data = new LinkedList<Character>();}/*** 判断栈是否为空* @return*/public boolean isEmpty(){return num == 0 ? true : false;}/*** 入栈* @param ch*/public void push(Character ch){this.data.add(ch);this.num++;}/*** 出栈* @return*/public Character pop(){//栈为空时，返回' 'if(this.isEmpty()){return ' ';}Character ch = this.data.remove(data.size()-1);this.num--;return ch;}
}

括号匹配核心算法

    /*** 核心方法* @param s* @return*/public boolean isValid(String s) {char[] temp = s.toCharArray();MyStack stack = new MyStack();boolean flag = true;for(int i = 0 ; i < temp.length ; i++){//左括号，入栈if(temp[i] == '(' || temp[i] == '{' || temp[i] == '['){stack.push(temp[i]);}else{//右括号，出栈char left = stack.pop();//如果从栈中取出空值，说明栈已空，但还有右括号存在，肯定不匹配if(left == ' ') {flag = false;}//如果左右括号不匹配，则失败if(!check(left,temp[i])){flag = false;}}}//循环完毕后，若栈不空，说明左括号个数大于右括号，不匹配if(flag){if(!stack.isEmpty()){flag = false;}}return flag;}
}

完整代码

import java.util.LinkedList;/*** 括号匹配问题(Blog)*//*** 栈类，这里使用链栈*/
class MyStack{private int num;private LinkedList<Character> data;public MyStack(){this.num = 0;data = new LinkedList<Character>();}/*** 判断栈是否为空* @return*/public boolean isEmpty(){return num == 0 ? true : false;}/*** 入栈* @param ch*/public void push(Character ch){this.data.add(ch);this.num++;}/*** 出栈* @return*/public Character pop(){//栈为空时，返回' 'if(this.isEmpty()){return ' ';}Character ch = this.data.remove(data.size()-1);this.num--;return ch;}
}class Solution {/*** 判定左右括号是否匹配* @param left* @param right* @return*/private boolean check(char left , char right){if(left == '('){return right == ')' ? true : false;}if(left == '['){return right == ']' ? true : false;}if(left == '{'){return right == '}' ? true : false;}return false;}/*** 核心方法* @param s* @return*/public boolean isValid(String s) {char[] temp = s.toCharArray();MyStack stack = new MyStack();boolean flag = true;for(int i = 0 ; i < temp.length ; i++){//左括号，入栈if(temp[i] == '(' || temp[i] == '{' || temp[i] == '['){stack.push(temp[i]);}else{//右括号，出栈char left = stack.pop();//如果从栈中取出空值，说明栈已空，但还有右括号存在，肯定不匹配if(left == ' ') {flag = false;}//如果左右括号不匹配，则失败if(!check(left,temp[i])){flag = false;}}}//循环完毕后，若栈不空，说明左括号个数大于右括号，不匹配if(flag){if(!stack.isEmpty()){flag = false;}}return flag;}
}public class Main {public static void main(String[] args) {// write your code hereSolution solution = new Solution();System.out.println(solution.isValid("(({[]})"));}
}

运行结果

(({[]})的运行结果

false
Process finished with exit code 0

与我们之前预测的一致。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！