记录一到当时没做出来的 “解析Json计算表达式值” 的算法题

转载请以链接形式标明出处：

本文出自:103style的博客

题目描述

给定表达式
A = [
"${a.b.c}",
"${not a.b.c}",
"${a.b.d} AND {m.n}",
"${a.b.d} OR {m.n}","${a.b.c} OR ((${not a.b.d} AND ${a.b.e}) AND ${not a.b.f})"
];

1 代表 true, 0 代表 false.

给定 json 字符串 B = {"a":{"b":{"c":"0","d":"1","e":"1","f":"0"}},"m":{"n":"0"}};

请返回一个 长度为 A长度 的 boolean 数组，对应位置为表达式的值。

个人算法

仅仅是保证题目做出来， 如果有描述错误的地方，或者更好的建议请留言告诉我。谢谢。

public class LeetCodeTest {

    private final String T = "True";
    private final String F = "False";
    private final String AND = "AND";
    private final String OR = "OR";
    private int curIndex = 1;

    public static void main(String[] args) {
        String[] A = new String[]{
                "${a.b.c}",
                "${not a.b.c}",
                "${a.b.d} AND {m.n}",
                "${a.b.d} OR {m.n}",
                "${a.b.c} OR ((${not a.b.d} AND ${a.b.e}) AND ${not a.b.f})"
        };
        //0:false  1:true
        String B = "{\"a\":{\"b\":{\"c\":\"0\",\"d\":\"1\",\"e\":\"1\",\"f\":\"0\"}},\"m\":{\"n\":\"0\"}}";
        
        boolean[] res = new LeetCodeTest().getFormatRes(A, B);
        
        StringBuilder sb = new StringBuilder();
        for (boolean r : res) sb.append(r).append(" ");

        System.out.println(sb.toString());
    }

    //{
//  a:{
//     b:{
//         c:0,
//         d:1,
//         e:1,
//         f:0
//       }
//    },
//  m:{
//     n:0
//    }
//}
    boolean[] getFormatRes(String[] arr, String json) {
        char[] jArr = json.toCharArray();
        //去掉开始的 {
        HashMap<String, Object> map = getDecodeMap(jArr, 1);
        HashMap<String, Boolean> regMap = new HashMap<>();
        getRegMap(map, regMap, "");

        boolean[] res = new boolean[arr.length];
        for (int i = 0; i < arr.length; i++) {
            String t = arr[i].replaceAll("\\$", "");
            res[i] = getRegRes(regMap, t);
        }
        return res;
    }

    /**
     * 计算表达式的结果
     *
     * @param mapReg 记录表达式的集合
     * @param s      当前解析的表达式
     */
    boolean getRegRes(HashMap<String, Boolean> mapReg, String s) {
        if (T.equals(s)) return true;
        else if (F.equals(s)) return false;

        if (s.contains("(")) {
            int e = s.indexOf(")");
            int f = s.substring(0, e).lastIndexOf("(");
            String item = s.substring(f, e + 1);
            boolean res = getRegRes(mapReg, item.substring(1, item.length() - 1));
            return getRegRes(mapReg, s.replace(item, res ? T : F));
        } else if (s.contains(OR)) {
            String[] arr = s.split(OR);
            for (String a : arr) {
                if (getRegRes(mapReg, a.trim())) return true;
            }
            return false;
        } else if (s.contains(AND)) {
            String[] arr = s.split(AND);
            for (String a : arr) {
                if (!getRegRes(mapReg, a.trim())) return false;
            }
            return true;
        } else {
            return mapReg.get(s.trim());
        }
    }

    /**
     * 记录所有的表达式
     *
     * @param map    json解析之后的数据
     * @param regMap 保存表达式的集合
     * @param reg    当前的表达式
     */
    private void getRegMap(HashMap<String, Object> map, HashMap<String, Boolean> regMap, String reg) {
        for (Map.Entry<String, Object> item : map.entrySet()) {
            if (item.getValue() instanceof HashMap) {
                getRegMap((HashMap<String, Object>) item.getValue(), regMap, reg + item.getKey() + ".");
            } else {
                boolean res = "1".equals(item.getValue());
                regMap.put("{" + reg + item.getKey() + "}", res);
                regMap.put("{not " + reg + item.getKey() + "}", !res);
            }
        }
    }

    /**
     * 解析json字符传   暂时不支持 数组[]
     *
     * @param jArr  jsonString的 char数组
     * @param start 开始的下标
     */
    private HashMap<String, Object> getDecodeMap(char[] jArr, int start) {
        HashMap<String, Object> map = new HashMap<>();
        StringBuilder keyBuild = new StringBuilder();
        StringBuilder valueBuild = new StringBuilder();
        //记录冒号的个数 "":""
        // colonCount = 1 表示开始记录key
        // colonCount = 3 表示开始记录value
        int colonCount = 0;
        for (int i = start; i < jArr.length; i++) {
            if (jArr[i] == '}') {
                //记录当前走到的位置
                curIndex = i;
                return map;
            } else if (jArr[i] == '{') {
                map.put(keyBuild.toString(), getDecodeMap(jArr, i + 1));
                //更新到最新的位置
                i = curIndex;
            } else if (jArr[i] == '"') {
                colonCount++;
                if (colonCount % 4 == 0) {
                    map.put(keyBuild.toString(), valueBuild.toString());
                }
            } else if (jArr[i] == ',') {
                //重置变量
                colonCount = 0;
                keyBuild = new StringBuilder();
                valueBuild = new StringBuilder();
            } else {
                if (colonCount % 4 == 1) {
                    keyBuild.append(jArr[i]);
                } else if (colonCount % 4 == 3) {
                    valueBuild.append(jArr[i]);
                }
            }
        }
        return map;
    }

}

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=1uzczhff706sm