精华内容
下载资源
问答
  • 2021-05-23 02:06:05

    1要求

    编写程序检查该字符串的括号是否成对出现,而且不能交叉出现。

    输入:

    一个字符串,里边可能包含“()”、"{}"、“[]”三种括号,“#”结束

    输出:

    成功:代表括号成对出现并且嵌套正确

    失败:未正确使用括号字符。

    2分析

    用一个栈,就能解决该问题,左括号栈顶字符必须和第一个入栈的右括号字符匹配。

    栈介绍:栈是一种特殊的线性表,仅能在线性表的一端操作。

    栈的特性:后进先出(LIFO)

    由于正在学数据结构,于是栈的定义与操作都是自己编写的,为了巩固概念

    3代码

    #include

    #include

    #define STACK_INT_SIZE 100

    #define STACKINCREMENT 10

    #define bool int //自定义bool变量

    #define SElemType char

    typedef struct {

    SElemType *base; //栈基地址

    SElemType *top; //栈顶地址

    int stacksize;

    } SqStack;

    //------基本操作的算法描述------

    //构建一个空栈

    bool InitStack(SqStack *S) {

    S->base = (SElemType *) malloc(STACK_INT_SIZE * sizeof(SElemType)); //开辟新的空间

    if (!S->base) return 0; //开辟失败返回0

    S->top = S->base;

    S->stacksize = STACK_INT_SIZE;

    return 1;

    }

    //若栈不为空,返回栈顶元素,并返回true 否则返回 false

    bool GetTop(SqStack S) {

    if (S.top == S.base) return 0;

    return *(S.top - 1);

    }

    //插入元素 为新的栈顶元素

    bool Push(SqStack *S, SElemType e) {

    if (S->top - S->base >= S->stacksize) //如果栈满 需要增加空间

    {

    S->base = (SElemType *) realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(SElemType));

    if (!S->base) return 0;

    S->top = S->base + S->stacksize;

    S->stacksize += STACKINCREMENT;

    }

    *(S->top++) = e;

    return 1;

    }

    //若栈不为空,则删除栈顶元素,用e返回其值,返回true, 否则返回false

    bool Pop(SqStack *S, SElemType *e) {

    if (S->top == S->base) return 0;

    *e = *(--S->top);

    return 1;

    }

    //检查括号字符在字符集中的位置

    int CheckChar(char c, char OP[]) {

    int i;

    for (i = 0; i < 3; i++)

    if (c == OP[i])return i;

    return 999;

    }

    int main() {

    SqStack OPTR;

    InitStack(&OPTR);

    Push(&OPTR, '#');

    printf("输入括号以“#”结尾\n");

    char c;

    c = getchar();

    int m = 1; //判断最终是否完全匹配 完全匹配 值为1,否则为0

    char OP1[] = {'[', '(', '{'}; //前置括号字符集

    char OP2[] = {']', ')', '}'}; //后置括号字符集

    while (c != '#') {

    if (CheckChar(c, OP1) < 3) {

    Push(&OPTR, c);

    c = getchar();

    } else {

    if (CheckChar(GetTop(OPTR), OP1) == CheckChar(c, OP2)) {

    //如果需要检验的两个符号在前置和后置括号集中的位置相同则表示配对成功

    //例如[和],[在前置括号集中的位置1,]在后置括号集中的位置1,所以匹配成功

    Pop(&OPTR, &c);

    c = getchar();

    continue;

    } else {

    m = 0;

    break;

    }

    }

    }

    if (GetTop(OPTR) != c)m = 0;

    if (m == 1)printf("\n括号完全匹配!");

    else printf("\n括号匹配失败!");

    return 0;

    }

    遇到此类问题,但看了文章还是未解决,

    评论或加 QQ:781378815

    更多相关内容
  • 括号匹配C语言

    2018-12-05 20:55:34
    3利用栈的操作实现括号匹配的检验。 .括号匹配算法思想 (1)出现的凡是“左括号”,则进栈; (2)出现的是“右括号”, 首先检查栈是否空? 若栈空,则表明该“右括号”多余 否则和栈顶元素比较? 若相...
  • 本文实例讲述了Python实现求解括号匹配问题的方法。分享给大家供大家参考,具体如下: 这个在本科学习数据结构的时候已经接触很多了,主流的思想是借助栈的压入、弹出来进行匹配,至于python的话可以使用列表来完成...
  • 括号配对问题

    2018-12-28 00:04:56
    括号配对问题C++,C++语言括号匹配问题解决方法,给定一个输入的字符串,包含括号(和),能够找出(和)的个数,并指出(或者)不正确的位置。
  • 利用栈编写满足下列要求的括号匹配检验程序:假设表达式中允许包含两种括号:圆括号和方括号,其嵌套的顺序随意,即([]())或[([][])]等为正确的格式,[(]或([())或(()])均为不正确的格式。输入一个包含上述括号的...
  • 使用顺序栈实现括号匹配
  • 顺序栈实现括号配对

    2016-11-06 10:43:09
    顺序栈实现括号配对
  • 这篇文章主要介绍了python实现括号匹配方法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 1.用一个栈【python中可以用List】就可以解决,时间和空间...
  • 本文实例讲述了Python实现的括号匹配判断功能。分享给大家供大家参考,具体如下: 1.用一个栈【python中可以用List】就可以解决,时间和空间复杂度都是O(n) # -*- coding: utf8 -*- # 符号表 SYMBOLS = {'}': '{', ...
  • 括号匹配问题

    2016-04-10 13:33:44
    假设表达式中允许包含3种括号:圆括号,方括号和大括号。设计一个算法采用顺序栈判断表达式中的括号是否正确配对
  • 2、假设一个算术表达式中可以包含三种括号:园...编写判别给定表达式中所含括号是否正确配对出现的算法(已知表达式已存入数据元素为字符的顺序表中)。要求:顺序栈存储;实现顺序栈的基本操作;调用基本操作完成。
  • 括号匹配的检验

    2019-03-24 17:32:03
    假设一个算术表达式中可以包含三种括号:园括号...编写判别给定表达式中所含括号是否正确配对出现的算法(已知表达式已存入数据元素为字符的顺序表中)。要求:顺序栈存储;实现顺序栈的基本操作;调用基本操作完成。
  • c++使用堆栈实现括号匹配问题
  • C++编程,表达式括号匹配配对问题的实验报告
  • 数据结构中括号匹配的更优秀算法。。。。。
  • C语言验证括号匹配

    2018-03-30 18:07:27
    在c语言下,利用栈的结构,判断一个表达式的括号是否合法
  • 题目描述: 给定一个只包括 '(',')','{','}','[',']'...括号匹配是一个很明显的使用栈解决的问题 import java.util.Stack; class Solution { public boolean isValid(String s) { Stack stack = new Stack();
  • 数据结构实验-括号匹配的检验-链栈实现
  • 括号匹配检测工具

    2016-04-08 10:02:50
    目前的工作需要写大量的、很长的、内含很多括号的表达式,需要一个括号匹配检测工具,于是就自己做了一个,也发上来分享一下。 使用说明: 1.将要检查的表达式复制到“请将要检查的表达式复制到该文件.txt”文件内...
  • 表达式括号匹配配对判断实验报告(内附源代码)
  • 栈和队列括号匹配.cpp

    2020-03-19 13:48:29
    数据结构栈和队列的基本应用——括号匹配问题的设计与实现,使用C++实现,包括如何创建栈,进行括号匹配等,思路清晰。
  • 数据结构 c++ 链接栈+顺序对:括号匹配 数据结构 c++ 链接栈+顺序对:括号匹配
  • 判断一个有左括号和右括号、以及其他ASCII字符组成的表达式是合法。...如果有*,则*可作为0个或者1个右括号,如果匹配则输出ok,不匹配则输出不匹配字符所在字符串中的具体位置。资源中包含详细源码+测试+visio流程图
  • 括号匹配程序

    2016-01-29 23:45:40
    假设一个算术表达式中包含圆括号、方括号两种类型的括号,试编写一个判断表达式中括号是否匹配的程序,匹配返回Match succeed!,否则返回Match false!。 例 [1+2*(3+4*(5+6))]括号匹配 (1+2)*(1+2*[(1+2)+3)...
  • 1.用一个栈【python中可以用List】就可以解决,时间和空间复杂度都是O(n)# -*- coding: utf8 -*-# 符号表SYMBOLS = {'}': '{', ']': '[', ')': '(', '>': ''# 映射左右括号便于出栈判断brackets_map = {')': '(', ']...

    1.用一个栈【python中可以用List】就可以解决,时间和空间复杂度都是O(n)

    # -*- coding: utf8 -*-

    # 符号表

    SYMBOLS = {'}': '{', ']': '[', ')': '(', '>': '<'}

    SYMBOLS_L, SYMBOLS_R = SYMBOLS.values(), SYMBOLS.keys()

    def check(s):

    arr = []

    for c in s:

    if c in SYMBOLS_L:

    # 左符号入栈

    arr.append(c)

    elif c in SYMBOLS_R:

    # 右符号要么出栈,要么匹配失败

    if arr and arr[-1] == SYMBOLS[c]:

    arr.pop()

    else:

    return False

    return True

    print(check("3 * {3 +[(2 -3) * (4+5)]}"))

    print(check("3 * {3+ [4 - 6}]"))

    2.

    # 存储左括号和右括号

    open_brackets = '([{<'

    close_brackets = ')]}>'

    # 映射左右括号便于出栈判断

    brackets_map = {')': '(', ']': '[', '}': '{', '>': '<'}

    # 对于每一行数据,进行如下判定若括号为左括号,加入栈,若括号为右括号,判断是否跟栈尾括号对应,

    若对应,弹出栈尾元素,若所有括号均正确闭合,则最后栈为空。

    for row in rows:

    stack = []

    label = True

    for char in row:

    if char in open_brackets:

    stack.append(char)

    elif char in close_brackets:

    if len(stack) < 1:

    label = False

    break

    elif brackets_map[char] == stack[-1]:

    stack.pop()

    else:

    label = False

    break

    else:

    continue

    if stack != []:

    label = False

    print(label)

    rows = [

    '([<^>x[ ]{a}]{/}{t}g<^>)<{x}b>{x}[b][c[c]]{{h}}',

    '[/]{((x)({{*}*}w)w){f}{v}[%(^[z]{u}{ })([[ ]-]h)]{c}(*)[y]}',

    '<<(^)z>>[b]< >[[(c)u[v]{z>}]g][/b[(])v(v)(+)](v)',

    '[[b]][(v)g]([{{<->+}e}[*]d<+>]g[[a] <+>(v){b}]){a}[u]']

    3.

    在长度很大的时候可以尽快判断一些比较明显的错误的模式,节省时间:

    主要的思路:

    首先设置两个列表分别存放的是各种括号的开括号和闭括号,然后遍历给定的字符串,分如下几种情况:

    1.字符串 首字符 出现在闭括号列表中,直接结束,输出错误

    2.字符串长度不为偶数,直接结束,输出错误

    3.对原始字符串列表化去重,如果去重后的列表长度不为偶数直接结束,输出错误

    4.遍历字符串,将属于开括号集合的括号加入到列表中,当遇上一个闭括号的时候计算该闭括号在闭括号列表中的索引与

    当前列表最后一个开括号在开括号列表中的索引是否一致,一致则继续,否则直接结束,输出错误

    #!usr/bin/env python

    # encoding:utf-8

    def bracket_mathch(one_str):

    '''''

    括号匹配

    '''

    tmp_list = []

    open_bracket_list = ['(', '[', '{', '<', '《']

    close_bracket_list = [')', ']', '}', '>', '》']

    one_str_list = list(one_str)

    length = len(one_str_list)

    set_list = list(set(one_str_list))

    num_list = [one_str_list.count(one) for one in set_list]

    if one_str[0] in close_bracket_list:

    return False

    elif length % 2 != 0:

    return False

    elif len(set_list) % 2 != 0:

    return False

    else:

    for i in range(length):

    if one_str[i] in open_bracket_list:

    tmp_list.append(one_str[i])

    elif one_str[i] in close_bracket_list:

    if close_bracket_list.index(one_str[i]) == open_bracket_list.index(tmp_list[-1]):

    tmp_list.pop()

    else:

    return False

    break

    return True

    if __name__ == '__main__':

    one_str_list = ['({})', '({[<《》>]})', '[(]){}', '{{{{{{', '([{}])', '}{[()]']

    for one_str in one_str_list:

    if bracket_mathch(one_str):

    print(one_str, '正确')

    else:

    print(one_str, '错误')

    tmp = '{}[{()()[]<{{[[[[(())()()(){}[]{}[]()<>]]]]}}>}]'

    print(bracket_mathch(tmp))

    PS:下面看下python 匹配格式

    匹配格式

    模式

    描述

    ^

    匹配字符串的开头

    $

    匹配字符串的末尾。

    .

    匹配任意字符,除了换行符,当re.DOTALL标记被指定时,则可以匹配包括换行符的任意字符。

    [...]

    用来表示一组字符,单独列出:[amk] 匹配 'a','m'或'k'

    [^...]

    不在[]中的字符:[^abc] 匹配除了a,b,c之外的字符。

    re*

    匹配0个或多个的表达式。

    re+

    匹配1个或多个的表达式。

    re?

    匹配0个或1个由前面的正则表达式定义的片段,非贪婪方式

    re{ n}

    re{ n,}

    精确匹配n个前面表达式。

    re{ n, m}

    匹配 n 到 m 次由前面的正则表达式定义的片段,贪婪方式

    a| b

    匹配a或b

    (re)

    G匹配括号内的表达式,也表示一个组

    (?imx)

    正则表达式包含三种可选标志:i, m, 或 x 。只影响括号中的区域。

    (?-imx)

    正则表达式关闭 i, m, 或 x 可选标志。只影响括号中的区域。

    (?: re)

    类似 (...), 但是不表示一个组

    (?imx: re)

    在括号中使用i, m, 或 x 可选标志

    (?-imx: re)

    在括号中不使用i, m, 或 x 可选标志

    (?#...)

    注释.

    (?= re)

    前向肯定界定符。如果所含正则表达式,以 ... 表示,在当前位置成功匹配时成功,否则失败。但一旦所含表达式已经尝试,匹配引擎根本没有提高;模式的剩余部分还要尝试界定符的右边。

    (?! re)

    前向否定界定符。与肯定界定符相反;当所含表达式不能在字符串当前位置匹配时成功

    (?> re)

    匹配的独立模式,省去回溯。

    \w

    匹配字母数字

    \W

    匹配非字母数字

    \s

    匹配任意空白字符,等价于 [\t\n\r\f].

    \S

    匹配任意非空字符

    \d

    匹配任意数字,等价于 [0-9].

    \D

    匹配任意非数字

    \A

    匹配字符串开始

    \Z

    匹配字符串结束,如果是存在换行,只匹配到换行前的结束字符串。c

    \z

    匹配字符串结束

    \G

    匹配最后匹配完成的位置。

    \b

    匹配一个单词边界,也就是指单词和空格间的位置。例如, 'er\b' 可以匹配"never" 中的 'er',但不能匹配 "verb" 中的 'er'。

    \B

    匹配非单词边界。'er\B' 能匹配 "verb" 中的 'er',但不能匹配 "never" 中的 'er'。

    \n, \t, 等.

    匹配一个换行符。匹配一个制表符。等

    \1...\9

    匹配第n个分组的子表达式。

    \10

    匹配第n个分组的子表达式,如果它经匹配。否则指的是八进制字符码的表达式。

    总结

    以上所述是小编给大家介绍的python实现括号匹配的思路详解,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对脚本之家网站的支持!

    展开全文
  • c程序括号匹配检查.c

    2019-09-29 14:55:52
    使用C语言实现括号匹配检查,对输入的一段文字进行排查,如果前置括号或者后置括号不存在,则指出改正,对于c语言入门的同学能够巩固所学知识,获得提升。
  • 算法:括号匹配问题

    千次阅读 2021-01-29 05:40:41
    还记得有一次笔试题,有一道括号匹配的算法题,当时没有学习数据结构和算法,思路很模糊,后来了解一些数据结构之后就有思路了,今天将解法写出来。问题描述:给定一个字符串,里边可能包含“()”、"{}"、“[]”三种...

    还记得有一次笔试题,有一道括号匹配的算法题,当时没有学习数据结构和算法,思路很模糊,后来了解一些数据结构之后就有思路了,今天将解法写出来。

    问题描述:

    给定一个字符串,里边可能包含“()”、"{}"、“[]”三种括号,请编写程序检查该字符串的括号是否成对出现。

    输出:

    true:代表括号成对出现并且嵌套正确,或字符串无括号字符。

    false:未正确使用括号字符。

    1、分析

    如果了解数据结构,那么应该知道,简单的采用一个栈的特性,就能解决该问题,左括号栈顶字符必须和第一个入栈的右括号字符匹配。

    栈介绍:栈是一种特殊的线性表,仅能在线性表的一端操作,栈顶允许操作,栈底不允许操作。

    栈的特性:后进先出(LIFO)

    5bf5aecc9cd5?utm_campaign=maleskine&utm_content=note&utm_medium=seo_notes&utm_source=recommendation

    栈示意

    下面用一幅流程图来说明程序运行步骤:

    5bf5aecc9cd5?utm_campaign=maleskine&utm_content=note&utm_medium=seo_notes&utm_source=recommendation

    步骤流程图

    2、代码实现

    2.1 Python实现

    使用list来代替栈实现相同的操作。声明了几个变量:

    BRANKETS:由配对的括号组成的字典,注意使用右括号作为key,因为我们要判断的是右括号是否与左括号匹配,在字典中找出与key对应的value简单,要是找value对应的key要复杂一些。

    BRANKETS_LEFT与BRANKETS_RIGHT分别存放左括号与右括号,用来判断字符属于哪个阵营。

    #-*- coding: utf-8 -*-

    BRANKETS = {'}':'{',']':'[',')':'('}

    BRANKETS_LEFT, BRANKETS_RIGHT = BRANKETS.values(), BRANKETS.keys()

    def bracket_check(string):

    """括号匹配检测函数"""

    stack = []

    for char in string:

    # 如果是左括号

    if char in BRANKETS_LEFT:

    # 入栈

    stack.append(char)

    # 右括号

    elif char in BRANKETS_RIGHT:

    # stack不为空,并且括号匹配成功

    if stack and stack[-1] == BRANKETS[char]:

    # 出栈

    stack.pop()

    # 匹配成功

    else:

    return False

    return not stack

    def main():

    print(bracket_check('{brace*&^[square(round)]end}'))

    print(bracket_check('{brace*&^[square(round])end}'))

    if __name__ == '__main__':

    main()

    输出结果:

    true

    false

    2.2 C++实现

    C++中自带栈数据结构,需要包含头文件。使用string类型的变量bracketLeft和bracketRight来存储左括号和右括号,判断右括号与左括号匹配的方法是:先在bracketRight找到该字符的索引,然后对比栈顶字符和bracketLeft相同索引处的字符是否匹配。

    #include

    #include

    using namespace std;

    string bracketLeft = "{[(";

    string bracketRight = "}])";

    bool BracketCheck(string str)

    {

    stack s;

    // 遍历字符串

    for (int i = 0; i < str.length(); i++)

    {

    char chr = str[i];

    int indexLeft = -1, indexRight = -1;

    indexLeft = bracketLeft.find(chr);

    indexRight = bracketRight.find(chr);

    // 是左括号

    if (indexLeft >= 0)

    s.push(chr); // 入栈

    // 是右括号

    else if (indexRight >= 0)

    {

    // 匹配成功

    if (!s.empty() && s.top() == bracketLeft[indexRight])

    s.pop(); // 出栈

    else

    return false;

    }

    }

    return s.empty();

    }

    int main()

    {

    cout << boolalpha << BracketCheck("{brace*&^[square(round)]end}") << endl;

    cout << boolalpha << BracketCheck("{brace*&^[square(round])end}") << endl;

    return 0;

    }

    输出结果:

    true

    false

    本文通过栈数据结构实现了括号匹配的判断,希望读者通过本文加深对栈的理解,并记住思路,没准下次面试时就会碰到这道题。

    展开全文
  • 使用Visual C++2010软件打开即可,主要是括号匹配的问题的代码

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 368,994
精华内容 147,597
关键字:

括号配对