Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
sisterAn opened this issue Jan 24, 2021 · 3 comments

Comments

@sisterAn
Copy link
Owner

sisterAn commented Jan 24, 2021

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

  • 异常输入
    ${{(3+5)*2+(5/(24)}
    
  • 输出
    {
        1: '{',    
        11: '(',    
    }
    
  • 正常输入
    [a+b]/${x}
    
  • 输出
    {}
    
@sisterAn
Copy link
Owner Author

解答:利用栈结构

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

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

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

代码实现:

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
Copy link

/**
 * 力扣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
Copy link

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

3 participants