Java解决括号匹配算法问题

原创
2020/04/04 12:17
阅读数 2.1K

有效字符串需满足:

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

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

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

代码如下:


import org.apache.commons.collections4.BidiMap;
import org.apache.commons.collections4.bidimap.DualHashBidiMap;
import org.junit.Assert;
import org.junit.Test;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @author : 杨松<yangsong158@qq.com>
 * @date : 2020/4/3
 * @desc :
 */
public class BracketPairTest {

    public boolean pairCheck(Map<String,String> pairMap,String expr) {
        if (expr == null || expr == "") throw new NullPointerException("表达式为空");
        //双向Map解决括号匹配问题
        BidiMap<String,String> bracketMap = new DualHashBidiMap();
        bracketMap.putAll(pairMap);

        Stack<String> stack = new Stack<String>();

        StringBuffer overlap = new StringBuffer();  //叠加器,解决括号不为一个字符的问题
        int overlapMaxLen = 2;                      //叠加器,最大叠加字符数
        for (int i = 0; i < expr.length(); i++) {
            String word = expr.substring(i,i+1);
            overlap.append(word);
            String overlapWord = overlap.toString();
            if(bracketMap.containsKey(word)){
                stack.push(word);
            }else if(bracketMap.containsKey(overlapWord)){
                stack.push(overlapWord);
            }else{
                if(bracketMap.containsValue(word)){             //右半部分括号
                    String left = bracketMap.getKey(word);      //找左半部分括号
                    if (!stack.empty() && stack.peek().equals(left)) {  //栈顶元素和括号对中的左半括号相同,则匹配,出栈
                        stack.pop();
                    }
                }else if(bracketMap.containsValue(overlapWord)){ //单独处理下叠加器中涉及括号有多个字符的问题
                    String left = bracketMap.getKey(overlapWord);
                    if (!stack.empty() && stack.peek().equals(left)) {
                        stack.pop();
                    }
                }
            }
            //叠加器超过满最大个数,清空最前面的字符
            if(overlap.length()==overlapMaxLen) overlap.deleteCharAt(0);
        }

        if (stack.empty())
            return true;
        return false;
    }

    @Test
    public void pairCheckTest(){
        //1.设置括号对
        Map<String,String> bracketMap = new HashMap(){{
            put("{", "}");
            put("[", "]");
            put("(", ")");
            put("<$", ">");
            put("【※", "※】");
        }};
        //2.验证是否通过
        Assert.assertTrue(pairCheck(bracketMap,"()"));
        Assert.assertTrue(pairCheck(bracketMap,"()[]"));
        Assert.assertTrue(pairCheck(bracketMap,"()[]{}"));
        Assert.assertTrue(pairCheck(bracketMap,"{[]}"));
        Assert.assertTrue(pairCheck(bracketMap,"{[()]}"));
        Assert.assertTrue(pairCheck(bracketMap,"{((1+3)+2+4)+9*7}"));
        Assert.assertTrue( pairCheck(bracketMap,"{[(<$这是一段内容>)]}"));
        Assert.assertFalse(pairCheck(bracketMap,"{[(<$这是一段内容)]}"));
        Assert.assertTrue(pairCheck(bracketMap,"{[(【※变量测试※】)]}"));
        Assert.assertFalse(pairCheck(bracketMap,"{[(【※变量测试】)]}"));
    }

}
展开阅读全文
打赏
0
0 收藏
分享
加载中
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部