将 JSON 字符串转换为对象

2759. 将 JSON 字符串转换为对象

给定一个字符串 str ，返回 JSON 解析后的 parsedStr 。你可以假设 str 是一个有效的 JSON 字符串，因此它只包含字符串、数字、数组、对象、布尔值和 null。str 不会包含不可见字符和转义字符。JSON 中的字符串值只包含字母数字字符。

请在不使用内置的 JSON.parse 方法的情况下解决此问题。

示例 1：

输入：str = '{"a":2,"b":[1,2,3]}'
输出：{"a":2,"b":[1,2,3]}
解释：返回由 JSON 字符串表示的对象。

示例 2：

输入：str = 'true'
输出：true
解释：原始类型是有效的 JSON。

示例 3：

输入：str = '[1,5,"false",{"a":2}]'
输出：[1,5,"false",{"a":2}]
解释：返回由 JSON 字符串表示的数组。

提示：

str 是一个有效的 JSON 字符串
1 <= str.length <= 10⁵

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

/** * @param {string} str * @return {null|boolean|number|string|Array|Object} */ var jsonParse = function(str) { };

javascript 解法, 执行用时: 684 ms, 内存消耗: 57.3 MB, 提交时间: 2023-10-15 14:37:36

class Parser {
    constructor(parserFn) {
        this.parserFn = parserFn
    }

    parse(target) {
        const initState = { target, index: 0, isError: false }
        const nextState = this.parserFn(initState)
        if (nextState.index !== target.length) nextState.isError = true
        return nextState
    }

    map(fn) {
        return new Parser(state => {
            const nextState = this.parserFn(state)
            if (nextState.isError) return nextState
            return { ...nextState, result: fn(nextState.result) }
        })
    }
}

const str = s =>
    new Parser(state => {
        if (state.isError) return state
        const { target, index } = state
        if (target.substring(index, index + s.length) !== s) return { ...state, isError: true }
        return { ...state, index: index + s.length, result: s }
    })

const regExp = pattern =>
    new Parser(state => {
        if (state.isError) return state
        const { target, index } = state
        const slicedTarget = target.slice(index)
        const match = slicedTarget.match(pattern)
        if (!match) return { ...state, isError: true }
        const [ result ] = match
        return { ...state, index: index + result.length, result }
    })

const zeroOrMore = parser =>
    new Parser(state => {
        if (state.isError) return state
        const results = []
        let nextState = state
        while (true) {
            const testState = parser.parserFn(nextState)
            if (testState.isError) break
            nextState = testState
            results.push(nextState.result)
        }
        return { ...nextState, result: results }
    })

const oneOf = (...parsers) =>
    new Parser(state => {
        if (state.isError) return state
        for (const parser of parsers) {
            const nextState = parser.parserFn(state)
            if (!nextState.isError) return nextState
        }
        return { ...state, isError: true }
    })

const seqOf = (...parsers) =>
    new Parser(state => {
        if (state.isError) return state
        const results = []
        let nextState = state
        for (const parser of parsers) {
            nextState = parser.parserFn(nextState)
            if (nextState.isError) return { ...state, isError: true }
            results.push(nextState.result)
        }
        return { ...nextState, result: results }
    })

const between = (left, right) => content =>
    seqOf(left, content, right)
        .map(([_left, content, _right]) => content)

const sepBy = sep => value =>
    new Parser(state => {
        if (state.isError) return state
        const results = []
        let nextState = state
        while (true) {
            const valueState = value.parserFn(nextState)
            if (valueState.isError) break
            results.push(valueState.result)
            nextState = valueState
            const sepState = sep.parserFn(nextState)
            if (sepState.isError) break
            nextState = sepState
        }
        return { ...nextState, result: results }
    })

const lazy = thunk =>
    new Parser(state => thunk().parserFn(state))



const whitespace = regExp(/^\s/)
const ignored = zeroOrMore(whitespace)

const token = s =>
    seqOf(ignored, str(s)).map(([_, res]) => res)
const regexToken = pattern =>
    seqOf(ignored, regExp(pattern)).map(([_, res]) => res)

const betweenBrackets = between(token("["), token("]"))
const betweenBraces = between(token("{"), token("}"))
const sepByComma = sepBy(token(","))



const stringLit = regexToken(/^"[^"]*"/)
    .map(res => res.substring(1, res.length - 1))

const numberLit = regexToken(/^[+-]?[0-9]+(\.[0-9]*)?/)
    .map(res => Number(res))

const nullLit = token("null")
    .map(() => null)

const booleanLit = oneOf(token("true"), token("false"))
    .map(res => res === "true" ? true : false)

const arrayLit = lazy(() =>
    betweenBrackets(sepByComma(jsonLit)))

const kvPair = lazy(() =>
    seqOf(stringLit, token(":"), jsonLit))
        .map(([k, _colon, v]) => [k, v])

const objectLit = lazy(() =>
    betweenBraces(sepByComma(kvPair)))
        .map(res => res.reduce((acc, [key, val]) => (acc[key] = val, acc), {}))

const jsonLit = lazy(() =>
    oneOf(booleanLit, nullLit, stringLit, numberLit, arrayLit, objectLit))

/**
 * @param {string} str
 * @return {*}
 */
var jsonParse = function(str) {
    return jsonLit.parse(str).result
};

javascript 解法, 执行用时: 156 ms, 内存消耗: 59 MB, 提交时间: 2023-10-15 14:36:42

/**
 * @param {string} str
 * @return {null|boolean|number|string|Array|Object}
 */
var jsonParse = function(str) {
  const n = str.length;
  let index = 0;
  // 解析字符串
  function parseString() {
    let curStr = "";
    // ++index 是为了直接跳过首个 `"` 字符
    while(++index < n && str.charAt(index) !== '"') {
      curStr += str.charAt(index);
    }
    // 跳过结束双引号 `"`
    index++;
    return curStr
  }
  // 解析数值
  function parseNumber(){
    let num = '';
    while(index < n) {
      cur = str.charAt(index);
      // 判断是否是数值，包含小数、负数
      if(!/[\d.\-]/.test(cur)) break;
      num += cur;
      index++;
    }
    return parseFloat(num)
  }
  // 解析数组
  function parseArray(){
    let arr = [];
    // 跳过数组开始括号 `[`
    index++;
    while(index < n && str.charAt(index) !==']') {
      arr.push(parseValue());
      // 跳过数组中的逗号 
      if (str.charAt(index) === ',') {
        index++;
      }
    }
    // 跳过数组结束括号 `]` 
    index++;
    return arr;
  }
  // 解析对象
  function parseObject(){
    let obj = {}
    // 跳过对象开始括号 `{`
    index ++;
    while(index < n && str.charAt(index) !=='}') {
      const key = parseString();
      index++;
      const value = parseValue();
      obj[key] = value;
      // 跳过对象中的逗号 
      if(str.charAt(index) === ',') {
        index++;
      }
    }
    // 跳过对象结束括号 `}` 
    index++;
    return obj;
  }
  // 解析值
  function parseValue() {
    const first = str.charAt(index);
    if(first === '"') {
      return parseString();
    }else if (first === '[') {
      return parseArray();
    }else if (first === '{') {
      return parseObject();
    }else if (first === 'f') {
      index += 5;
      return false;
    }else if (first === 't') {
      index += 4;
      return true;
    }else if (first === 'n') {
      index += 4;
      return null;
    }else {
      return parseNumber();
    }
  }

  return parseValue();
};

上一题

下一题

详情