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

Activity

1. sisterAn

   added

   达摩院

   on Jan 24, 2021
2. sisterAn commented on Jan 25, 2021

   

   sisterAn

   on Jan 25, 2021

   OwnerAuthor

   More actions

   解答：利用栈结构

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

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

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

   代码实现：

   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：有效的括号

   👍React with 👍2Reacted by hyyabc123 and Ryan
3. xllpiupiu commented on Oct 6, 2021

   

   xllpiupiu

   on Oct 6, 2021

   More actions

   /**
    * 力扣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]))
4. AlexZhang11 commented on May 24, 2024

   

   AlexZhang11

   on May 24, 2024

   More actions

   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)}'))