判断字符串是否括号匹配

发表于 更新于 分类于
判断字符串是否括号匹配

题目如下：

  • 一个字符串 S 可能包含 {} () [] 三种括号，判断S是否是括号匹配的
  • 如 (a{b}c) 匹配，而 {a(b 或 {a(b}c) 就不匹配

补充

  • 栈，逻辑结构。理论模型，不管如何实现，不受任何语言的限制
  • 数组，物理结构。真实的功能实现，受限于编程语言

思路如下

  • 遇到左括号 {([ 就压栈
  • 遇到右括号 })] 就判断栈顶，匹配则出栈
  • 最后判断length是否为0即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

function isMatch(left:string,right:string):boolean {
  if (left === '{' && right === '}') return true
  if (left === '[' && right === ']') return true
  if (left === '(' && right === ')') return true
  return false
}

export function matchBracket(str:string):boolean {
  const length = str.length
  if(length === 0) return true
  
  const stack = []
  
  const leftSymbols = '{[('
  const rightSymbols = ')]}'
  
  for(let i = 0;i < length;i++){
    const s = str[i]
    if(leftSymbols.includes(s)){
      // 左括号 压栈
      stack.push(s)
    }else if(rightSymbols.includes(s)){
      // 右括号 判断栈顶（是否出栈）
      const top = stack[stack.length - 1]
      if(isMatch(top,s)){
        stack.pop()
      }else {
        return false
      }
    }
  }
  return stack.length === 0
}

单元测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * @description 括号匹配 test
 * @author sola-grj
 */

import { matchBracket } from './match-bracket'

describe('括号匹配', () => {
    it('正常情况', () => {
        const str = '{a(b[c]d)e}f'
        const res = matchBracket(str)
        expect(res).toBe(true)
    })

    it('不匹配', () => {
        const str = '{a(b[(c]d)e}f'
        const res = matchBracket(str)
        expect(res).toBe(false)
    })

    it('顺序不一致的', () => {
        const str = '{a(b[c]d}e)f'
        const res = matchBracket(str)
        expect(res).toBe(false)
    })

    it('空字符串', () => {
        const res = matchBracket('')
        expect(res).toBe(true)
    })
})