找出一个字符串中的不匹配括号的位置，以json形式输出，位置index从0开始

[sisterAn]

找出一个字符串中的不匹配括号（ {[()]} ）的位置，以json形式输出，位置index从0开始。

• 异常输入

  ${{(3+5)*2+(5/(24)}

• 输出

  {
      1: '{',    
      11: '(',    
  }

• 正常输入

  [a+b]/${x}

• 输出

  {}

[sisterAn]

解答：利用栈结构

解题思路： 将字符串中的字符依次入栈，遍历字符依次判断：

• 首先判断该元素是否括号，不是则遍历下一个字符
• 是 { 、 ( 、 [ ，直接入栈
• 否则该字符为 } 、 ) 、 ] 中的一种，
  • 如果栈为空，则当前右括号无匹配左括号，直接写进结果数组，并遍历下一个字符
  • 栈顶元素出栈，判断当前元素是否与出栈元素匹配，例如栈中元素有 ({， 如果继续遍历到的元素为 ), 那么当前元素序列为 ({) 是不可能有效的，所以此时与出栈元素匹配失败，将出栈元素写进结果数组，并继续匹配当前元素

当遍历完成时，所有已匹配的字符都已匹配出栈，如果栈不为空，说明字符串中还有未匹配的左括号字符，则将栈元素直接写进结果数组

代码实现：

let getUnmatchJson = function(s) {
    let map = {
        '{': '}',
        '(': ')',
        '[': ']'
    }
    let stack = [], 
        brackets = '{[()]}', 
        result = {}
    for(let i = 0; i < s.length ; i++) {
        // 如果不是括号，跳过
        if(brackets.indexOf(s[i]) === -1) continue
        // 如果是左括号，则进栈
        if(map[s[i]]) {
            stack.push({
                char: s[i],
                index: i
            })
        } else {
            // 如果是右括号，则出栈匹配
            if(!stack.length) {
                //如果栈为 null ，则表示没有匹配的左括号，则当前有括号直接进结果数组
                result[i] = s[i]
                continue
            }
            // 出栈
            let temp = stack.pop()
            // 括号不匹配
            if (s[i] !== map[temp.char]) {
                // 不匹配左括号进结果数组，并i--，继续匹配当前字符
                result[temp.index] = temp.char
                i --
            }
        }
    }
    // 如果匹配结束，依然有剩余的左括号，则直接进结果数组
    while(stack.length) {
        let temp = stack.pop()
        result[temp.index] = temp.char
    }
    return result
};

let s1 = '${{(3+5)*2+(5/(24)}'
let s2 = '[a+b]/${x}'
let s3 = '${(3+5)*2+(5/(24)}(}'
console.log(getUnmatchJson(s1)) // {1: "{", 11: "("}
console.log(getUnmatchJson(s2)) // {}
console.log(getUnmatchJson(s3)) // {10: "(", 18: "(", 19: "}"}

时间复杂度：O(n)

空间复杂度：O(n)

相关题目：图解腾讯&哔哩哔哩&leetcode20：有效的括号

[xllpiupiu]

/**
 * 力扣20 是字符串匹配判断
 * 输入：${{(3+5)*2+(5/(24)}
 * 输出：
 * {
 *   1: '{',    
 *   11: '(',    
 * }
 */
let str = '${{(3+5)*2+(5/(24)}'
const getUnmatchJson = function (s) {
    let stack = []
    const res = {}
    let map = {
        '{': '}',
        '(': ')',
        '[': ']'
    }
    let reg = /[^\{\[\(\)\]\}]/
    for (let i = 0, len = s.length; i < len; i++) {
        if (reg.test(s[i])) continue
        if(map[s[i]]) {
            stack.push({
                char:s[i],
                index:i
            })
        } else {
            //右括号
            if(stack.length===0) {
                //没有匹配的左括号
                res[i] = s[i]
                continue
            }
            let temp = stack.pop()
            if(s[i]!==map[temp.char]) {
                res[temp.index] = temp.char
                i--
            }
        }
    }
    //字符串匹配结束
    while(stack.length) {
        let temp = stack.pop()
        res[temp.index] = temp.char
    }
    return res
}
let str2 = '[a+b]/${dg'
console.log(getUnmatchJson(str))
console.log(getUnmatchJson(str2))
console.log(/[^\{\[\(\)\]\}]/.test(str[1]))

[AlexZhang11]

let map={
    '}':'{',
    ']':'[',
    ')':'(',
}
function fn(str){
    let stack = []
    let stack2 = []
    let res = {}
    for(let i = 0;i<str.length;i++){
        let c = str.charAt(i)
        if(['{','(','[',')',']','}'].includes(c)){
            if(['{','(','['].includes(c)){
                let it = i+'-'+c
                stack.push(c)
                stack2.push(it)
               }else if(stack.length&&stack[stack.length-1]!==map[c]){
                let k = stack.length-1
                    while(stack[k]!==map[c]){
                       k--
                    }
                    stack.splice(k,1)
                    stack2.splice(k,1)
               }else if(stack.length&&stack[stack.length-1]===map[c]){
                stack.pop()
                stack2.pop()
               }
        }
    }
    stack2.map(it=>{
        let list = it.split('-')
        res[list[0]] = list[1]
    })
    return res
}
console.log(fn('${{(3+5)*2+(5/(24)}'))