括号匹配

题目

一个字符串内部可能包含 { } ( ) [ ] 三种括号，判断该字符串是否是括号匹配的。
如 (a{b}c) 就是匹配的， {a(b 和 {a(b}c) 就是不匹配的。

栈 Stack

该题目的考察目的很明确 —— 栈

栈，先进后出，基本的 API

• push
• pop
• length

和栈相关的数据结构（后面讲）

• 队列，先进先出
• 堆，如常说的“堆栈模型”

逻辑结构和物理结构

栈和数组有什么区别？—— 没有可比性，两者不一个级别。就像：房子和石头有什么区别？

栈是一种逻辑结构，一种理论模型，它可以脱离编程语言单独讲。
数组是一种物理结构，代码的实现，不同的语言，数组语法是不一样的。

栈可以用数组来表达，也可以用链表来表达，也可以自定义 class MyStack {...} 自己实现…
在 JS 中，栈一般情况下用数组实现。

思路

• 遇到左括号 { ( [ 则压栈
• 遇到右括号 } ) ] 则判断栈顶，相同的则出栈
• 最后判断栈 length 是否为 0

答案

参考 match-brackets.ts 和 match-brackets.test.ts

• match-brackets.ts

/**
 * 判断左右括号是否匹配
 * @param left 左括号
 * @param right 右括号
 */
function isMatch(left: string, right: string): boolean {
    if (left === '{' && right === '}') return true
    if (left === '[' && right === ']') return true
    if (left === '(' && right === ')') return true
    return false
}

/**
 * 判断是否括号匹配
 * @param str str
 */
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
}

// // 功能测试
// const str = '{a(b[c]d)e}f'
// console.info(123123, matchBracket(str))

• match-brackets.test.ts

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

划重点

• 栈
• 逻辑结构和物理结构