前言

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

例题

题目来自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<T>

/**
 * 栈类，这里使用链栈
 */
class MyStack{
    private int num;
    private LinkedList<Character> data;
<span class="token keyword">public</span> <span class="token function">MyStack</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
    <span class="token keyword">this</span><span class="token punctuation">.</span>num <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    data <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">LinkedList</span><span class="token generics function"><span class="token punctuation">&lt;</span>Character<span class="token punctuation">&gt;</span></span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token comment">/**
 * 判断栈是否为空
 * @return
 */</span>
<span class="token keyword">public</span> <span class="token keyword">boolean</span> <span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
    <span class="token keyword">return</span> num <span class="token operator">==</span> <span class="token number">0</span> <span class="token operator">?</span> <span class="token boolean">true</span> <span class="token operator">:</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token comment">/**
 * 入栈
 * @param ch
 */</span>
<span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">push</span><span class="token punctuation">(</span>Character ch<span class="token punctuation">)</span><span class="token punctuation">{</span>
    <span class="token keyword">this</span><span class="token punctuation">.</span>data<span class="token punctuation">.</span><span class="token function">add</span><span class="token punctuation">(</span>ch<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">this</span><span class="token punctuation">.</span>num<span class="token operator">++</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token comment">/**
 * 出栈
 * @return
 */</span>
<span class="token keyword">public</span> Character <span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
	 <span class="token comment">//栈为空时，返回' '</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token string">' '</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    Character ch <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>data<span class="token punctuation">.</span><span class="token function">remove</span><span class="token punctuation">(</span>data<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">this</span><span class="token punctuation">.</span>num<span class="token operator">--</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> ch<span class="token punctuation">;</span>
<span class="token punctuation">}</span>

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

括号匹配核心算法

    /**
     * 核心方法
     * @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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

完整代码

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 {
<span class="token comment">/**
 * 判定左右括号是否匹配
 * @param left
 * @param right
 * @return
 */</span>
<span class="token keyword">private</span> <span class="token keyword">boolean</span> <span class="token function">check</span><span class="token punctuation">(</span><span class="token keyword">char</span> left <span class="token punctuation">,</span> <span class="token keyword">char</span> right<span class="token punctuation">)</span><span class="token punctuation">{</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>left <span class="token operator">==</span> <span class="token string">'('</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token keyword">return</span> right <span class="token operator">==</span> <span class="token string">')'</span> <span class="token operator">?</span> <span class="token boolean">true</span> <span class="token operator">:</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">if</span><span class="token punctuation">(</span>left <span class="token operator">==</span> <span class="token string">'['</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token keyword">return</span> right <span class="token operator">==</span> <span class="token string">']'</span> <span class="token operator">?</span> <span class="token boolean">true</span> <span class="token operator">:</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">if</span><span class="token punctuation">(</span>left <span class="token operator">==</span> <span class="token string">'{'</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token keyword">return</span> right <span class="token operator">==</span> <span class="token string">'}'</span> <span class="token operator">?</span> <span class="token boolean">true</span> <span class="token operator">:</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

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

}
public class Main {
<span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">main</span><span class="token punctuation">(</span>String<span class="token punctuation">[</span><span class="token punctuation">]</span> args<span class="token punctuation">)</span> <span class="token punctuation">{</span>
<span class="token comment">// write your code here</span>
    Solution solution <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Solution</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    System<span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span>solution<span class="token punctuation">.</span><span class="token function">isValid</span><span class="token punctuation">(</span><span class="token string">"(({[]})"</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

运行结果

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

false
Process finished with exit code 0
1
2

与我们之前预测的一致。

                                </div>

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: 2020/03/13 15:12