JSON парсер на Java без сторонних библиотек

Цель задачи: Создать парсер строки сложного json без использования библиотек.

Вопрос: Подскажите пожалуйста теоретический ход решения задачи. Вероятно потребуется использование рекурсии, но не ясно в каком виде лучше хранить результат. Уровней может быть сколько угодно и каждое поле хранит либо следующий объект либо строку.

Пример json строки:

{
"lvl-1a": "Result 1",
"lvl-1b":{
    "lvl-2a": "Result 2",
    "lvl-2b": {
        "lvl-3a": "Result 3"
        }
    }
}

Ответы (2 шт):

Автор решения: Дмитрий Рихтер

Я бы сделал примерно такой алгоритм и хранил бы все в HashMap.

Из строки json удаляем все переносы строк (/n), что бы дальше было проще работать.

Далее действительно проще пойти через рекурсию с правилами:

  1. Если встречаем {, то создаем новую HashMap<String, Object>, где ключ все что до : без кавычек, а Object остальное
  2. Если встречаем [ то в значение hashMap добавляем массив (но помним, что в нем также могут быть { и их также рекурсивно обрабатываем)
  3. Если просто String, то выходим из рекурсии в этой части записав его в value

Направление, примерно, такое

→ Ссылка
Автор решения: Harvar

На данный момент это самая близкая реализация задумки. Как оказалось для решения моей задачи подходит, но это не универсальное решение в виду недостатков.

Недостатки:

  1. Данный код не поддерживает массивы и другие структуры кроме строк и простых чисел
  2. Результат не хранит данные о глубине, поэтому при обработке следует самостоятельно следить за глубиной.
  3. Вероятно конвертация в строку будет ресурсозатратной так как создаётся новый StringBuilder на каждом этапе рекурсии.

Пояснения:

parseObject - обрабатывает объект проверяя есть ли проход дальше.

parseValue - конвертирует строку в число либо возвращает строку.

levelSeparator - разделяет строку на отдельные объекты. Не углубляется

buildAnswer - конвертирует результат обратно в строку. Вынесен в отдельный метод так как появляется в конце лишняя ',' которую нужно убрать (Не реализовать в рекурсии без ошибок).

import java.util.*;

public final class JsonSerializer {

public static Map<String, Object> fromJson(String json) {
    System.out.println("Input data: " + json);
    return parseObject(json.substring(1, json.length() - 1));
}

private static Map<String, Object> parseObject(String str) {
    Map<String, Object> result = new LinkedHashMap<>();
    List<String> data = levelSeparator(str);

    for (String entry : data) {
        String[] parts = entry.split(":", 2);
        String key = parts[0].trim().replace("\"", "");
        String value = parts[1].trim();

        if (value.startsWith("{")) {
            result.put(key, parseObject(value.substring(1, value.length() - 1)));
        } else {
            result.put(key, parseValue(value));
        }
    }

    return result;
}

private static Object parseValue(String value) {
    value = value.trim();
    if (value.matches("-?\\d+(\\.\\d+)?")) {
        return Integer.parseInt(value);
    }
    return value;
}

private static List<String> levelSeparator(String str) {
    List<String> result = new ArrayList<>();
    boolean isClosed = true;
    boolean isValue = false;
    int level = 0;
    int position = 0;
    int startPosition = 0;

    for (char c : str.toCharArray()) {
        if (c == '"') isClosed = !isClosed;

        if (c == ':' && !isValue && isClosed) {
            isValue = true;
        } else if (isValue && isClosed && c == '{') {
            ++level;
        } else if (isValue && isClosed && c == '}') {
            --level;
        } else if (c == ',' && isValue && level == 0 && isClosed) {
            result.add(str.substring(startPosition, position));
            startPosition = position + 1;
            isValue = false;
        }
        position++;
    }
    result.add(str.substring(startPosition));
    return result;
}

public static String toJson(Map<String, Object> data){
    String unedited = buildAnswer(data);
    StringBuilder builder = new StringBuilder(unedited);

    builder.deleteCharAt(builder.lastIndexOf(","));

    return builder.toString();
}

public static String buildAnswer(Map<String, Object> data) {
    StringBuilder builder = new StringBuilder();
    for (Map.Entry<String, Object> part : data.entrySet()){
        if (part.getValue() instanceof Map<?, ?> map){
            if (map.keySet().stream().allMatch(k -> k instanceof String)) {
                Map<String, Object> stringMap = (Map<String, Object>) map;
                builder.append("\"").append(part.getKey()).append("\":{\n");
                builder.append(toJson(stringMap)).append("},\n");
                continue;
            }
            throw new RuntimeException("Key is not string? " + map);
        }
        System.out.println(part);
        builder.append("\"").append(part.getKey()).append("\":").append(part.getValue().toString()).append(", \n");
    }

    return builder.substring(0, builder.length() - 1);
}
}

P.S. Забыл уточнить условие что входные данные не содержат \n\t.

→ Ссылка