【经典问题】括号匹配问题

小鱼儿 2022-01-26 02:21 342阅读 0赞

### 文章目录 ###

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

# 前言 #

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

# 例题 #

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

> 输入: “()”  
> 输出: true

**示例 2:**

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

**示例 3:**

> 输入: “(\]”  
> 输出: false

**示例 4:**

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

**示例 5:**

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

# 算法思想 #

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

# 算法举例 #

下面以`(({[]})` 序列为例说明算法过程：  
1、首先将这个字符串转换成字符数组，并初始化一个空栈。  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21nc2t5MQ_size_16_color_FFFFFF_t_70][]  
2、遍历到第0个元素，`(`，为左括号，入栈  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21nc2t5MQ_size_16_color_FFFFFF_t_70 1][]  
3、后面以此类推，遍历完第3个元素`[`后，栈空间应该是这样的  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21nc2t5MQ_size_16_color_FFFFFF_t_70 2][]  
4、遍历到第4个元素`]`时，发现为右括号，此时，从栈顶出栈一个左括号，即`[`，刚好`[`与`]`，匹配成一对  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21nc2t5MQ_size_16_color_FFFFFF_t_70 3][]  
5、以此类推，直到第6个元素`)`，都是匹配的  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21nc2t5MQ_size_16_color_FFFFFF_t_70 4][]  
6、此时，序列已经遍历完毕，但是栈不是空的，所以原序列匹配失败。

# 代码 #

## 栈类 ##

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

/** * 栈类，这里使用链栈 */
    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 here
            Solution solution = new Solution();
            System.out.println(solution.isValid("(({[]})"));
        }
    }

## 运行结果 ##

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

false
    Process finished with exit code 0

与我们之前预测的一致。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21nc2t5MQ_size_16_color_FFFFFF_t_70]: /images/20220126/3fa4bd8764284c8cb3dcc25fb778fcce.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21nc2t5MQ_size_16_color_FFFFFF_t_70 1]: /images/20220126/6001580a79af475c983499ecbc34f41c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21nc2t5MQ_size_16_color_FFFFFF_t_70 2]: /images/20220126/af2e6a20d52b4e59af506f7f7c35efd1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21nc2t5MQ_size_16_color_FFFFFF_t_70 3]: /images/20220126/8225c903c4d14a739bc7782dd815695d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21nc2t5MQ_size_16_color_FFFFFF_t_70 4]: /images/20220126/85d4e46c49134911867e0694d26054b9.png