Java解决括号匹配算法问题

有效字符串需满足：

左括号必须用相同类型的右括号闭合。包括：“( )”,“[ ]”,“{ }”。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。

思路：在这里我们使用栈来实现。遍历字符串时判断：如果是左括号，那么我们将其入栈；如果为右括号，我们先判断栈是否为空（有可能字符串刚开始就是一个右括号呢），为空的话直接返回false，不为空时判断：栈顶元素和下一个要入栈的元素是否相匹配，若匹配就出栈元素，若不匹配，返回false。

又因括号种类比较多，且存在${}这种括号不是单个字符的问题， 所以引入双向map,增强其扩展性。

代码如下：

1import org.apache.commons.collections4.BidiMap;
2import org.apache.commons.collections4.bidimap.DualHashBidiMap;
3import org.junit.Assert;
4import org.junit.Test;
5
6import java.util.HashMap;
7import java.util.Map;
8import java.util.Stack;
9
10/**
11 * @author : 杨松<yangsong158@qq.com>
12 * @date : 2020/4/3
13 * @desc :
14 */
15public class BracketPairTest {
16
17    public boolean pairCheck(Map<String,String> pairMap,String expr) {
18        if (expr == null || expr == "") throw new NullPointerException("表达式为空");
19        //双向Map解决括号匹配问题
20        BidiMap<String,String> bracketMap = new DualHashBidiMap();
21        bracketMap.putAll(pairMap);
22
23        Stack<String> stack = new Stack<String>();
24
25        StringBuffer overlap = new StringBuffer();  //叠加器，解决括号不为一个字符的问题
26        int overlapMaxLen = 2;                      //叠加器，最大叠加字符数
27        for (int i = 0; i < expr.length(); i++) {
28            String word = expr.substring(i,i+1);
29            overlap.append(word);
30            String overlapWord = overlap.toString();
31            if(bracketMap.containsKey(word)){
32                stack.push(word);
33            }else if(bracketMap.containsKey(overlapWord)){
34                stack.push(overlapWord);
35            }else{
36                if(bracketMap.containsValue(word)){             //右半部分括号
37                    String left = bracketMap.getKey(word);      //找左半部分括号
38                    if (!stack.empty() && stack.peek().equals(left)) {  //栈顶元素和括号对中的左半括号相同，则匹配，出栈
39                        stack.pop();
40                    }
41                }else if(bracketMap.containsValue(overlapWord)){ //单独处理下叠加器中涉及括号有多个字符的问题
42                    String left = bracketMap.getKey(overlapWord);
43                    if (!stack.empty() && stack.peek().equals(left)) {
44                        stack.pop();
45                    }
46                }
47            }
48            //叠加器超过满最大个数，清空最前面的字符
49            if(overlap.length()==overlapMaxLen) overlap.deleteCharAt(0);
50        }
51
52        if (stack.empty())
53            return true;
54        return false;
55    }
56
57    @Test
58    public void pairCheckTest(){
59        //1.设置括号对
60        Map<String,String> bracketMap = new HashMap(){{
61            put("{", "}");
62            put("[", "]");
63            put("(", ")");
64            put("<$", ">");
65            put("【※", "※】");
66        }};
67        //2.验证是否通过
68        Assert.assertTrue(pairCheck(bracketMap,"()"));
69        Assert.assertTrue(pairCheck(bracketMap,"()[]"));
70        Assert.assertTrue(pairCheck(bracketMap,"()[]{}"));
71        Assert.assertTrue(pairCheck(bracketMap,"{[]}"));
72        Assert.assertTrue(pairCheck(bracketMap,"{[()]}"));
73        Assert.assertTrue(pairCheck(bracketMap,"{((1+3)+2+4)+9*7}"));
74        Assert.assertTrue( pairCheck(bracketMap,"{[(<$这是一段内容>)]}"));
75        Assert.assertFalse(pairCheck(bracketMap,"{[(<$这是一段内容)]}"));
76        Assert.assertTrue(pairCheck(bracketMap,"{[(【※变量测试※】)]}"));
77        Assert.assertFalse(pairCheck(bracketMap,"{[(【※变量测试】)]}"));
78    }
79
80}