首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

括号匹配算法js

括号匹配算法是一种用于检查字符串中的括号是否正确配对的算法。在JavaScript中,这种算法通常使用栈(Stack)数据结构来实现。

基础概念

  1. 栈(Stack):是一种后进先出(LIFO, Last In First Out)的数据结构,只允许在一端(称为栈顶)进行插入和删除操作。
  2. 括号匹配:指的是检查字符串中的左括号和右括号是否一一对应,并且符合正确的嵌套顺序。

算法步骤

  1. 初始化一个空栈。
  2. 遍历字符串中的每个字符:
    • 如果字符是左括号(如 ([{),则将其压入栈中。
    • 如果字符是右括号(如 )]}),则检查栈顶元素:
      • 如果栈为空,或者栈顶元素不是对应的左括号,则字符串不匹配。
      • 否则,弹出栈顶元素。
  • 遍历结束后,如果栈为空,则字符串匹配;否则,字符串不匹配。

示例代码

代码语言:txt
复制
function isBracketMatched(str) {
    const stack = [];
    const brackets = {
        ')': '(',
        ']': '[',
        '}': '{'
    };
    
    for (let char of str) {
        if (char === '(' || char === '[' || char === '{') {
            stack.push(char);
        } else if (char === ')' || char === ']' || char === '}') {
            if (stack.length === 0 || stack.pop() !== brackets[char]) {
                return false;
            }
        }
    }
    
    return stack.length === 0;
}

// 测试示例
console.log(isBracketMatched("({[]})")); // 输出: true
console.log(isBracketMatched("({[}])")); // 输出: false

优势

  • 时间复杂度为 O(n),其中 n 是字符串的长度。
  • 空间复杂度为 O(n),在最坏情况下,栈可能需要存储所有的左括号。

应用场景

  • 在编程语言的解析器中,用于检查代码中的括号是否匹配。
  • 在文本编辑器中,用于提供括号匹配的实时反馈。
  • 在数学表达式或算术表达式的验证中。
页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

括号匹配算法的JS简单实现

完整示例 See the Pen 括号匹配算法演示 by 戴兜 (@DaiDR) on CodePen....花了大概一早上写了这个示例,没有使用任何第三方库,完成度也算是比较高,除本文所讲的括号匹配算法有效性判定算法以外,涉及不依赖覆盖层的canvas点击位置判定、canvas绘制文字间距自定义,蛮有意思。...括号匹配算法 (1)(2)(3)(4)(5) 观察上面这组括号,不难发现当 ) 的左侧不存在另一个 ) 时(即未发生嵌套时),最靠近它的 ( 便是和它所对应的括号。...我们通过递归来匹配内部嵌套的括号并将其跳过。...逻辑相似,我们只需要校验每对括号是否都被匹配就行了。从左向右遍历字串,如果当前位置是 ( 时,将其压入数组。

5.4K50

算法:括号匹配问题

还记得有一次笔试题,有一道括号匹配的算法题,当时没有学习数据结构和算法,思路很模糊,后来了解一些数据结构之后就有思路了,今天将解法写出来。...false:未正确使用括号字符。 1、分析 如果了解数据结构,那么应该知道,简单的采用一个栈的特性,就能解决该问题,左括号栈顶字符必须和第一个入栈的右括号字符匹配。...声明了几个变量: BRANKETS:由配对的括号组成的字典,注意使用右括号作为key,因为我们要判断的是右括号是否与左括号匹配,在字典中找出与key对应的value简单,要是找value对应的key要复杂一些...使用string类型的变量bracketLeft和bracketRight来存储左括号和右括号,判断右括号与左括号匹配的方法是:先在bracketRight找到该字符的索引,然后对比栈顶字符和bracketLeft...相同索引处的字符是否匹配。

1.9K10
  • 实现括号匹配算法(括号匹配的检验算法完整程序)

    实现括号匹配算法(顺序表) 括号匹配问题 假设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号,编写一个函数,用来判别表达式中的括号是否正确配对,并设计一个测试主函数。...【算法思想】 在算术表达式中,右括号和左括号匹配的次序正好符合后到的括号要最先被匹配的“后进先出”堆栈操作特点,因此可以借助一个堆栈来进行判断。...括号匹配共有以下4种情况: 左、右括号配对次序不正确; 右括号多于左括号; 左括号多于右括号: 左、右括号匹配正确。...当扫描到某一种类型的右括号时,比较当前栈顶括号是否与之匹配,若匹配,则退栈继续进行判断:若当前栈顶括号与当前扫描的括号不相同,则左、右括号配对次序不正确;若字符串当前为某种类型右括号而堆栈已空,则右括号多于左括号...\n"); else printf("左右括号匹配正确!

    1.9K20

    括号匹配算法「建议收藏」

    概述 ​ 括号匹配在很多字符串处理的场景中时常被用到,诸如各大IDE括号不匹配的错误提示,编译器编译时检查应该成对出现的括号是否符合要求等,在这里我们就直接使用一种比较常规,但效率不差的方法去解决括号匹配的问题就行了...栈方法匹配问题 ​ 为了方便描述,对于需要做匹配的两个符号,比如’(‘和’)’,前者可称为左侧符号,后者可称为右侧符号。...在做符号匹配时,如果以左侧符号为标准,左侧符号需要右侧符号来完成匹配,但是由于诸如括号这类的符号可以做嵌套,所以左侧符号之后既能有左侧符号,也能有右侧符号,处理起来很麻烦。...以右侧符号为标准就没有这个问题了,每一个右侧符号都需要一个左侧符号来匹配,并且要求该右侧符号之前最近的一个符号必须是相匹配的左侧符号,这样处理起来就方便多了。 ​...定义一个栈,用以记录遍历到当前位置时,所遇到的左侧符号,处理方式是这样的,每当遇到一个右侧符号时,检查栈是否为空,若此时栈不为空,则对栈进行pop操作表明顶部元素已被匹配,否则为不匹配情况,直接返回false

    70610

    C语言括号匹配(栈括号匹配c语言)

    给定一串字符,不超过100个字符,可能包括括号、数字、字母、标点符号、空格,编程检查这一串字符中的( ) ,[ ],{ }是否匹配。...输入样例1: sin(10+20) 输出样例1: yes 输入样例2: {[}] 输出样例2: no 思路:题目输入一些字符串,我们就先保留括号之类的,判断是否匹配。...如果遇到左括号,就入栈,如果遇到一个右括号,就与栈顶元素比较,如果匹配,出栈,就继续重复操作,直到字符串没有了。期间一旦出现不匹配的括号对就直接输出no ,如果栈空了,说明匹配了,就输出yes。...return 1; } else { return 0; } } int check(char left,char right)//判断是否左右括号匹配...因为不是在for循环中结束,说明都匹配成功了,但会出现特殊情况比如((()),令栈不为空。所以是否括号匹配成功不仅要判断是否右括号都有左括号使其匹配,还需要判断栈是否为空。

    2.7K20

    【JavaScript 算法】栈与队列:解决括号匹配问题

    在编程中,括号匹配问题是一类常见的算法题,通常用于验证括号的正确性,即检查括号是否成对出现且嵌套正确。栈(Stack)是一种非常适合解决括号匹配问题的数据结构。...本文将详细介绍如何使用栈来解决括号匹配问题的原理、实现及其应用。 一、算法原理 括号匹配问题可以通过栈的数据结构来解决。...如果遇到右括号,检查栈顶元素是否为对应的左括号。如果是,则将栈顶元素弹出;否则,括号不匹配。 最终,栈应为空。如果栈不为空,则括号不匹配。...二、算法实现 以下是使用栈解决括号匹配问题的JavaScript实现: /** * 检查括号是否匹配 * @param {string} s - 包含括号的字符串 * @return {boolean...四、总结 栈是一种非常适合解决括号匹配问题的数据结构,通过将左括号压入栈中,并在遇到右括号时进行匹配,可以有效地检查括号是否匹配。

    16510

    【数据结构与算法 经典例题】括号匹配问题

    有效的括号 - 力扣(LeetCode) ​ 二、解题思路 破解之道 括号匹配问题是一个比较有实际意义的问题, 问题要求将三种类型括号匹配,其中包括顺序匹配和数量匹配 使用栈的后进先出结构可以很好的解决这个问题...: 遍历字符串 遇到左括号则压栈等待右括号匹配; 遇到右括号先进行判断,首先判断栈是否为空,如果为空则不可能完成匹配,直接判定无效 上述判定不成立再进行下列判断 如果此时栈顶的数据是与右括号匹配的左括号...,则出栈,否则直接判定无效(顺序不匹配) 当字符串遍历完成时,如果栈为空,则说明括号全部匹配上了;否则说明数量不匹配 关于栈的问题可以阅读前置文章 【数据结构/C语言】使用数组实现栈:原理...、步骤与应用-CSDN博客 画图举例说明: 第一种情况:数量顺序完全匹配时 第二种情况:数量匹配,顺序不匹配时 第三种情况:数量不匹配时 三、C语言实现代码 C语言需要自己实现栈的数据结构,轮子之前已经造好了...StackDestroy(Stack* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; } //括号匹配问题

    12600
    领券