BigFrontEnd Category 10 JSON Implementation Questions

Introduction

This blog post summarizes the JSON implementation related questions found on BigFrontEnd.Dev.

1.implement JSON.stringify()
- 1.1 implement JSON.stringify()
- 1.2 JSON.stringify() Implementation 2633. Convert JSON to string
2.implement JSON.parse()
3.JSON.parse() Implementation
4.serialize and deserialize data types not supported in JSON

1.implement `JSON.stringify()`

1.1 implement `JSON.stringify()`

21.https://bigfrontend.dev/problem/implement-JSON-stringify I believe you've used JSON.stringify() before, do you know the details of how it handles arbitrary data?

Please have a guess on the details and then take a look at the explanation on MDN, it is actually pretty complex.

In this problem, you are asked to implement your own version of JSON.stringify().

In a real interview, you are not expected to cover all the cases, just decide the scope with interviewer. But for a goal of practicing, your code here will be tested against a lot of data types. Please try to cover as much as you can.

Attention to the circular reference.

note

JSON.stringify() support two more parameters which is not required here.

Don't use JSON.stringify() in your code here, it doesn't help you practicing coding skills.

/**
 * @param {any} data
 * @return {string}
 */
function stringify(data) {
  const typeOfData = detectDataType(data);

  if (typeOfData === "array") {
    return stringifyArr(data);
  }

  if (typeOfData === "object" || typeOfData === "map") {
    return stringifyObj(data);
  }

  return _stringify(typeOfData, data);
}

function stringifyObj(data) {
  let stringifiedData = [];

  for (const key of Object.keys(data)) {
    const val = data[key];
    const typeOfVal = detectDataType(val);

    if (
      typeOfVal === "symbol" ||
      typeOfVal === "function" ||
      typeOfVal === "undefined"
    ) {
      continue;
    }

    let stringifiedKey = `\"${key}\":`;

    switch (typeOfVal) {
      case "array":
        stringifiedKey += stringifyArr(val);
        break;
      case "object":
      case "map":
        stringifiedKey += stringifyObj(val);
        break;
      default:
        stringifiedKey += _stringify(typeOfVal, val);
    }

    stringifiedData.push(stringifiedKey);
  }

  return `{${stringifiedData.join(",")}}`;
}

function stringifyArr(data) {
  let stringifiedData = [];

  for (const [index, val] of data.entries()) {
    if (isNaN(index)) {
      continue;
    }

    const typeOfVal = detectDataType(val);

    switch (typeOfVal) {
      case "array":
        stringifiedData.push(stringifyArr(val));
        break;
      case "object":
      case "map":
        stringifiedData.push(stringifyObj(val));
        break;
      default:
        stringifiedData.push(_stringify(typeOfVal, val));
    }
  }

  return `[${stringifiedData.join(",")}]`;
}

function _stringify(typeOfData, data) {
  switch (typeOfData) {
    case "string":
      return `\"${data}\"`;
    case "number":
    case "boolean":
      return String(data);
    case "function":
      return undefined;
    case "date":
      return `"${data.toISOString()}"`;
    case "set":
    case "map":
    case "weakSet":
    case "weakMap":
      return "{}";
    case "bigint":
      throw new Error("TypeError: BigInt value can't be serialized in JSON");
    default:
      return "null";
  }
}

function detectDataType(data) {
  if (typeof data === "number" && isNaN(data)) {
    return "NaN";
  }

  if (data === Infinity) {
    return "infinity";
  }

  if (typeof data !== "object") {
    return typeof data;
  }

  if (data === null) {
    return "null";
  }
  const dataTypes = new Map([
    [Number, "number"],
    [String, "string"],
    [Boolean, "boolean"],
    [Array, "array"],
    [ArrayBuffer, "arraybuffer"],
    [Date, "date"],
    [Set, "set"],
    [Map, "map"],
    [WeakSet, "weakSet"],
    [WeakMap, "weakMap"],
  ]);
  for (const [type, name] of dataTypes.entries()) {
    if (data instanceof type) {
      return name;
    }
  }

  return "object";
}

1.2 `JSON.stringify()` Implementation 2633. Convert JSON to string

Array
Object (except null)
String
Other: null, boolean, number.

type JSONValue = null | boolean | number | string | JSONValue[] | { [key: string]: JSONValue };

function jsonStringify(object: JSONValue): string {
    if (Array.isArray(object)) {
        return "[" + object.map(item => jsonStringify(item)).join(",") + "]";
    }
    if (typeof object === 'object' && object !== null) {
        return "{" + Object.entries(object).map(([key, val]) => `"${key}":${jsonStringify(val)}`).join(",") + "}";
    }
    if (typeof object === 'string') {
        return `"${object}"`
    }
    return String(object);
};

2.implement `JSON.parse()`

22.https://bigfrontend.dev/problem/implement-JSON-parse

Believe you are already familiar with JSON.parse(), could you implement your own version?

In case you are not sure about the spec, MDN here might help.

JSON.parse() support a second parameter reviver, you can ignore that.

note

Don't use JSON.parse() in your code here It doesn't help you practicing your skills.

Solution:

/**
 * @param {string} str
 * @return {object | Array | string | number | boolean | null}
 */
function parse(str) {
    let i = 0;

    function parseValue() {
        skipWhitespace();
        const char = str[i];

        if (char === '{') return parseObject();
        if (char === '[') return parseArray();
        if (char === '"') return parseString();
        if (char === 't') return parseTrue();
        if (char === 'f') return parseFalse();
        if (char === 'n') return parseNull();
        return parseNumber();
    }

    function skipWhitespace() {
        while (i < str.length && /\s/.test(str[i])) i++;
    }

    function parseObject() {
        const obj = {};
        i++; // Skip opening brace
        skipWhitespace();
        while (i < str.length && str[i] !== '}') {
            const key = parseString();
            skipWhitespace();
            i++; // Skip colon
            skipWhitespace();
            const value = parseValue();
            if (Number.isNaN(value)) {
              throw new Error("Fail to parse Object!");
            }
            obj[key] = value;
            skipWhitespace();
            if (str[i] === ',') {
              i++;
            }

            skipWhitespace();
        }

        i++; // Skip closing brace
        return obj;
    }

    function parseArray() {
        const arr = [];
        i++; // Skip opening bracket
        skipWhitespace();
        let startNumber = true;
        while (i < str.length && str[i] !== ']') {
            const value = parseValue();
            arr.push(value);
            startNumber = false;
            skipWhitespace();
            if (str[i] === ',') {
              startNumber = true;
              i++;
            }
            skipWhitespace();
        }
        if (startNumber) {
          throw new Error("End with comma");
        }
        i++; // Skip closing bracket
        return arr;
    }

    function parseString() {
        let result = '';
        i++; // Skip opening quote

        while (i < str.length && str[i] !== '"') {
            if (str[i] === '\\') {
                i++;
                if (str[i] === 'n') result += '\n';
                else if (str[i] === 'r') result += '\r';
                else if (str[i] === 't') result += '\t';
                else result += str[i];
            } else {
                result += str[i];
            }
            i++;
        }

        i++; // Skip closing quote
        return result;
    }

    function parseNumber() {
        let numStr = '';
        while (i < str.length && /[-0-9.eE+]/.test(str[i])) {
            numStr += str[i];
            i++;
        }
        return parseFloat(numStr);
    }

    function parseTrue() {
        i += 4; // Skip 'true'
        return true;
    }

    function parseFalse() {
        i += 5; // Skip 'false'
        return false;
    }

    function parseNull() {
        i += 4; // Skip 'null'
        return null;
    }

    return parseValue();
}

3.`JSON.parse()` Implementation

value       ::= object | array | string | number | "true" | "false" | "null"
object      ::= "{" [ pair ("," pair)* ] "}"
pair        ::= string ":" value
array       ::= "[" [ value ("," value)* ] "]"
string      ::= '"' characters '"'
characters  ::= "" | character characters
character   ::= "any Unicode character, except for \", \, and control characters" | escape
escape      ::= "\" ("\"" | "\\" | "/" | "b" | "f" | "n" | "r" | "t" | "u" hex hex hex hex)
number      ::= ["-"] int [frac] [exp]
int         ::= "0" | digit1-9 digits
frac        ::= "." digits
exp         ::= ("e" | "E") ["+" | "-"] digits
digit       ::= "0" | digit1-9
digits      ::= digit | digit digits

// https://medium.com/@anchen.li/writing-a-json-parser-in-typescript-72c90fe6df8c

type JSONValue = string | number | boolean | null | JSONObject | JSONArray;
type JSONObject = { [key: string]: JSONValue };
type JSONArray = JSONValue[];

export class JSONParser {
  private pos = 0;
  private input: string;

  constructor(input: string) {
    this.input = input;
  }

  public parse(): JSONValue {
    this.consumeWhitespace();

    const result = this.parseValue();

    this.consumeWhitespace();

    if (this.hasNext()) {
      throw new Error(
        `Unexpected token at position ${this.pos}-${this.currentToken()}`,
      );
    }

    return result;
  }

  private consumeWhitespace(): void {
    while (/\s/.test(this.currentToken())) {
      this.consume();
    }
  }

  private hasNext(): boolean {
    return this.currentToken() !== "";
  }

  private currentToken(): string {
    return this.input.charAt(this.pos);
  }

  private consume(expected?: string): void {
    if (expected && this.currentToken() !== expected) {
      throw new Error(`Expected ${expected} at position ${this.pos}`);
    }

    this.pos++;

    // Skip over any whitespace characters
    while (
      this.currentToken() === " " ||
      this.currentToken() === "\t" ||
      this.currentToken() === "\n" ||
      this.currentToken() === "\r"
    ) {
      this.pos++;
    }
  }

  private optionalConsume(expected: string): boolean {
    if (this.currentToken() === expected) {
      this.pos++;
      // Skip over any whitespace characters
      while (
        this.currentToken() === " " ||
        this.currentToken() === "\t" ||
        this.currentToken() === "\n" ||
        this.currentToken() === "\r"
      ) {
        this.pos++;
      }

      return true;
    }

    return false;
  }

  private parseValue(): JSONValue {
    switch (this.currentToken()) {
      // If the current token is an opening brace, parse an object
      case "{":
        return this.parseObject();
      // If the current token is an opening bracket, parse an array
      case "[":
        return this.parseArray();
      // If the current token is a string literal, parse a string
      case '"':
        return this.parseString();
      // If the current token is a minus sign or a digit, parse a number
      case "-":
      case "0":
      case "1":
      case "2":
      case "3":
      case "4":
      case "5":
      case "6":
      case "7":
      case "8":
      case "9":
        return this.parseNumber();
      // If the current token is the 'true' literal, return true
      case "t":
        return this.parseTrue();
      // If the current token is the 'false' literal, return false
      case "f":
        return this.parseFalse();
      // If the current token is the 'null' literal, return null
      case "n":
        return this.parseNull();
      // Otherwise, the JSON value is invalid
      default:
        throw new Error(`Invalid JSON value at position ${this.pos}`);
    }
  }

  private parseObject(): JSONObject {
    const obj: JSONObject = {};

    // Consume opening curly brace
    this.consume("{");

    // Parse key-value pairs
    while (this.currentToken() !== "}") {
      const pair = this.parsePair();
      obj[pair.key] = pair.value;

      // Check if there is another pair
      if (this.currentToken() === ",") {
        this.consume(",");
      } else if (this.currentToken() !== "}") {
        throw new Error(`Invalid object at position ${this.pos}`);
      }
    }

    // Consume closing curly brace
    this.consume("}");

    return obj;
  }

  private parsePair(): { key: string; value: JSONValue } {
    const key = this.parseString();

    // Consume colon
    this.consume(":");

    const value = this.parseValue();

    return { key, value };
  }

  private parseArray(): JSONArray {
    const arr: JSONArray = [];

    // Consume opening square bracket
    this.consume("[");

    // Parse values
    while (this.currentToken() !== "]") {
      const value = this.parseValue();
      arr.push(value);

      // Check if there is another value
      if (this.currentToken() === ",") {
        this.consume(",");
      } else if (this.currentToken() !== "]") {
        throw new Error(`Invalid array at position ${this.pos}`);
      }
    }

    // Consume closing square bracket
    this.consume("]");

    return arr;
  }
  private parseString(): string {
    let str = "";

    // Consume opening quote
    this.consume('"');

    // Parse string characters
    while (this.currentToken() !== '"') {
      if (this.currentToken() === "\\") {
        str += this.parseEscape();
      } else {
        str += this.currentToken();
        this.pos++;
      }
    }

    // Consume closing quote
    this.consume('"');

    return str;
  }

  private parseNumber(): number {
    let str = "";

    // If the number is negative, add the minus sign to the string and consume the token
    if (this.currentToken() === "-") {
      str += "-";
      this.consume("-");
    }

    // Parse the integer part of the number
    str += this.parseDigits();

    // If the number has a fractional part, parse it
    if (this.currentToken() === ".") {
      str += ".";
      this.consume(".");
      str += this.parseDigits();
    }

    // If the number has an exponent, parse it
    if (this.currentToken() === "e" || this.currentToken() === "E") {
      str += this.currentToken();
      this.consume();

      if (this.currentToken() === "+" || this.currentToken() === "-") {
        str += this.currentToken();
        this.consume();
      }

      str += this.parseDigits();
    }

    // Convert the parsed string to a number and return it
    return parseFloat(str);
  }

  private parseDigits(): string {
    let str = "";

    // If the first digit is zero, add it to the string and consume the token
    if (this.currentToken() === "0") {
      str += this.currentToken();
      this.consume();
    }
    // If the first digit is between 1 and 9, parse the rest of the digits
    else if (this.currentToken() >= "1" && this.currentToken() <= "9") {
      str += this.currentToken();
      this.consume();

      while (this.currentToken() >= "0" && this.currentToken() <= "9") {
        str += this.currentToken();
        this.consume();
      }
    }
    // Otherwise, the JSON number is invalid
    else {
      throw new Error(`Invalid JSON number at position ${this.pos}`);
    }

    // Return the parsed string of digits
    return str;
  }

  private parseEscape(): string {
    // Consume the backslash
    this.consume("\\");

    switch (this.currentToken()) {
      // If the escape sequence is a double quote, backslash, or forward slash, return the corresponding character
      case '"':
      case "\\":
      case "/":
        const c = this.currentToken();
        this.consume();
        return c;
      // If the escape sequence is a backspace, return the corresponding character
      case "b":
        this.consume();
        return "\b";
      // If the escape sequence is a form feed, return the corresponding character
      case "f":
        this.consume();
        return "\f";
      // If the escape sequence is a newline, return the corresponding character
      case "n":
        this.consume();
        return "\n";
      // If the escape sequence is a carriage return, return the corresponding character
      case "r":
        this.consume();
        return "\r";
      // If the escape sequence is a tab, return the corresponding character
      case "t":
        this.consume();
        return "\t";
      // If the escape sequence is a Unicode code point, parse it and return the corresponding character
      case "u":
        this.consume();
        const code = parseInt(this.input.substr(this.pos, 4), 16);

        if (isNaN(code)) {
          throw new Error(
            `Invalid Unicode escape sequence at position ${this.pos}`,
          );
        }

        this.pos += 4;

        return String.fromCharCode(code);
      // Otherwise, the JSON escape sequence is invalid
      default:
        throw new Error(`Invalid escape sequence at position ${this.pos}`);
    }
  }

  private parseTrue(): true {
    this.consume("t");
    this.consume("r");
    this.consume("u");
    this.consume("e");
    return true;
  }

  private parseFalse(): false {
    this.consume("f");
    this.consume("a");
    this.consume("l");
    this.consume("s");
    this.consume("e");
    return false;
  }

  private parseNull(): null {
    this.consume("n");
    this.consume("u");
    this.consume("l");
    this.consume("l");
    return null;
  }
}

const parser = new JSONParser(
  '{"name": "John John", "age": 30, "test": {"test": 1}}',
);
console.log(parser.parse());

4.serialize and deserialize data types not supported in JSON

144.https://bigfrontend.dev/problem/serialize-and-deserialize-data-types-not-supported-in-JSON

Obviously, JSON.parse() and JSON.stringify() are unable to handle data types that are not supported in JSON.

JSON.stringify({a:1n}) // Error

Also undefined is ignored in object properties or changed to null.

JSON.stringify([undefined]) // "[null]"
JSON.stringify({a: undefined }) // "{}"

NaN and Infinity are also treated as null

JSON.stringify([NaN, Infinity]) // "[null,null]"
JSON.stringify({a: NaN, b:Infinity}) // "{"a":null,"b":null}"

for more info, please refer to MDN.

But sometimes we might want to be able to serialize these data types.

Now please implement functions to serialize and deserialize following data types:

primitives (symbol is exluded)
object literals
array Object literals and arrays are consisting of primitives and might be nested

Code below is expected to work:

parse(stringify([1n, null, undefined, NaN])) // [1n, null, undefined, NaN]
parse(stringify({a: undefined, b: NaN}) // {a: undefined, b: NaN}

You can use JSON.stringify() and JSON.parse() in your code or write your own.

Solution: We can utilize the reviver parameter in JSON.stringify() and JSON.parse() to customize how data is serialized and deserialized. By checking typeof value === "bigint", typeof value === "undefined", Number.isNaN(value), value === Infinity, or value === "__-infinity__", we can determine if a value is BigInt, undefined, NaN, Infinity, or -Infinity. However, there's a challenge: when parsing, any undefined values are automatically dropped. To address this, we can use a placeholder string, such as UNDEFINED_PLACEHOLDER, to represent undefined. After parsing, we can replace this placeholder with the actual undefined value.

/**
 * type SerializablePrimitives = undefined | null | number | string | bigint | boolean

  * type Serializable = {
    [index: string]: Serializable
  } | Serializable[] | SerializablePrimitives
*/

/**
 * @params {Serializable} data
 * @returns {string}
 */
function stringify(data) {
  return JSON.stringify(data, (key, value) => {
    if (typeof value === "bigint") {
      return `__bigint__${value.toString()}`;
    } else if (typeof value === "undefined") {
      return "__undefined__";
    } else if (Number.isNaN(value)) {
      return "__nan__";
    } else if (value === Infinity) {
      return "__infinity__";
    } else if (value === -Infinity) {
      return "__-infinity__";
    }
    return value;
  });
}

/**
 * @params {string} data
 * @returns {Serializable}
 */
function parse(json) {
  const UNDEFINED_PLACEHOLDER = "__undefined_placeholder__";
  const parsedData = JSON.parse(json, (key, value) => {
    if (typeof value === "string") {
      if (value.startsWith("__bigint__")) {
        return BigInt(value.slice(10));
      } else if (value === "__undefined__") {
        return UNDEFINED_PLACEHOLDER;
      } else if (value === "__nan__") {
        return NaN;
      } else if (value === "__infinity__") {
        return Infinity;
      } else if (value === "__-infinity__") {
        return -Infinity;
      }
    }
    return value;
  });

  // Convert placeholders back to undefined
  function restoreUndefined(obj) {
    if (Array.isArray(obj)) {
      return obj.map((item) =>
        item === UNDEFINED_PLACEHOLDER ? undefined : restoreUndefined(item),
      );
    } else if (obj && typeof obj === "object") {
      for (const key in obj) {
        if (obj[key] === UNDEFINED_PLACEHOLDER) {
          obj[key] = undefined;
        } else {
          obj[key] = restoreUndefined(obj[key]);
        }
      }
    }
    return obj === UNDEFINED_PLACEHOLDER ? undefined : obj;
  }

  return restoreUndefined(parsedData);
}

Introduction

1.implement JSON.stringify()

1.1 implement JSON.stringify()

1.2 JSON.stringify() Implementation 2633. Convert JSON to string

2.implement JSON.parse()

3.JSON.parse() Implementation