当前位置： 首页 > news >正文

【2024年华为OD机试】 (C卷,100分)- 括号匹配（Java JS PythonC/C++）

news 2025/7/3 9:51:02

在这里插入图片描述

一、问题描述

题目描述

给定一个字符串，里边可能包含“()”、“[]”、“{}”三种括号，请编写程序检查该字符串中的括号是否成对出现，且嵌套关系正确。
若括号成对出现且嵌套关系正确，或该字符串中无括号字符，输出：true；
若未正确使用括号字符，输出：false。
实现时，无需考虑非法输入。

输入描述

无

输出描述

无

用例

用例 1

输入:

(1+2)/(0.5+1)

输出:

true

解题思路

  1. 使用栈：

    • 使用一个栈来跟踪未匹配的左括号。
    • 遍历字符串，对于每个字符：
      • 如果是左括号（(, [, {），将其压入栈中。
      • 如果是右括号（), ], }），检查栈顶是否有对应的左括号：
        • 如果有，弹出栈顶的左括号。
        • 如果没有，返回 false。
    • 遍历结束后，如果栈为空，说明所有括号都正确匹配，返回 true。
    • 如果栈不为空，说明有未匹配的左括号，返回 false。

  2. 特殊情况：

    • 如果字符串中没有括号字符，直接返回 true。

详细步骤

  1. 读取输入：

    • 从标准输入读取一个字符串。

  2. 初始化栈：

    • 创建一个空栈 stack，用于存储未匹配的左括号。

  3. 遍历字符串：

    • 遍历字符串中的每个字符 char：
      • 如果 char 是左括号（(, [, {），将其压入栈中。
      • 如果 char 是右括号（), ], }）：
        • 检查栈顶是否有对应的左括号：
          • 如果有，弹出栈顶的左括号。
          • 如果没有，返回 false。

  4. 检查栈是否为空：

    • 遍历结束后，如果栈为空，返回 true。
    • 如果栈不为空，返回 false。

用例解释

用例 1
  • 输入：
    • (1+2)/(0.5+1)
  • 输出：
    • true

解释：

  • 遍历字符串：
    • 遇到 (，压入栈中。
    • 遇到 )，检查栈顶是否有 (，有则弹出。
    • 遇到 (，压入栈中。
    • 遇到 )，检查栈顶是否有 (，有则弹出。
  • 遍历结束后，栈为空，说明所有括号都正确匹配，返回 true。

通过上述步骤，我们可以高效地检查字符串中的括号是否成对出现且嵌套关系正确。这种方法的时间复杂度为 O(n)，其中 n 是字符串的长度。

二、JavaScript算法源码

以下是 JavaScript 代码 的详细中文注释和逻辑讲解：

JavaScript 代码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");// 创建 readline 接口，用于从控制台读取输入
const rl = readline.createInterface({input: process.stdin,  // 输入流output: process.stdout, // 输出流
});// 监听输入事件
rl.on("line", (line) => {// 调用 getResult 函数处理输入，并输出结果console.log(getResult(line));
});// 算法入口
function getResult(line) {// 定义正则表达式，匹配非括号字符const regExp = /[^\(\)\[\]\{\}]/g;// 去除非括号字符line = line.replace(regExp, "");// 定义括号映射关系const map = {")": "(", // 右圆括号对应左圆括号"]": "[", // 右方括号对应左方括号"}": "{", // 右花括号对应左花括号};// 使用栈来检查括号是否匹配const stack = [];// 遍历处理后的字符串for (let c of line) {// 如果栈不为空，且当前字符是右括号if (stack.length && map[c]) {// 检查栈顶元素是否是对应的左括号if (stack.at(-1) === map[c]) {stack.pop(); // 匹配成功，弹出栈顶元素continue;} else {return false; // 匹配失败，返回 false}}// 将当前字符压入栈中stack.push(c);}// 如果栈为空，说明所有括号都匹配成功return stack.length == 0;
}

代码逻辑讲解

1. 输入获取
  • 使用 readline 模块从控制台读取输入。
  • 监听 line 事件，当用户输入一行内容时，调用 getResult 函数处理。
2. 算法入口
  • 步骤 1：定义正则表达式 regExp，用于匹配非括号字符。
    • 正则表达式 /[^\(\)\[\]\{\}]/g 表示匹配所有非括号字符。
  • 步骤 2：使用 replace 方法去除非括号字符。
    • 例如，输入 "a(b{c}d)e"，处理后得到 "({})"。
  • 步骤 3：定义括号映射关系 map。
    • 右括号作为键，左括号作为值。
  • 步骤 4：使用栈 stack 来检查括号是否匹配。
    • 遍历处理后的字符串：
      • 如果当前字符是右括号，检查栈顶元素是否是对应的左括号。
        • 如果匹配成功，弹出栈顶元素。
        • 如果匹配失败，返回 false。
      • 如果当前字符是左括号，直接压入栈中。
  • 步骤 5：遍历结束后，检查栈是否为空。
    • 如果栈为空，说明所有括号都匹配成功，返回 true。
    • 如果栈不为空，说明有未匹配的括号，返回 false。

示例运行

输入
a(b{c}d)e
处理步骤
  1. 去除非括号字符，得到 "({})"。
  2. 遍历字符串：
    • 遇到 "("，压入栈中，栈为 ["("]。
    • 遇到 "{"，压入栈中，栈为 ["(", "{"]。
    • 遇到 "}"，检查栈顶元素 "{"，匹配成功，弹出栈顶元素，栈为 ["("]。
    • 遇到 ")"，检查栈顶元素 "("，匹配成功，弹出栈顶元素，栈为 []。
  3. 遍历结束，栈为空，返回 true。
输出
true

总结

  • 功能：检查输入字符串中的括号是否匹配。
  • 核心逻辑：
    1. 去除非括号字符。
    2. 使用栈检查括号是否匹配。
  • 适用场景：需要检查括号匹配的场景，例如代码语法检查。
  • 注意事项：
    • 输入字符串可能包含非括号字符，需要先去除。
    • 栈的使用是解决括号匹配问题的经典方法。

如果有其他问题，欢迎随时提问！

三、Java算法源码

以下是 Java 代码 的详细中文注释和逻辑讲解：

Java 代码

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Scanner;public class Main {// 输入获取public static void main(String[] args) {Scanner sc = new Scanner(System.in); // 创建 Scanner 对象，用于从控制台读取输入String s = sc.nextLine(); // 读取一行输入System.out.println(getResult(s)); // 调用 getResult 方法处理输入，并输出结果}// 算法入口public static boolean getResult(String s) {// 去除非括号字符s = s.replaceAll("[^\\(\\)\\[\\]\\{\\}]", ""); // 使用正则表达式去除非括号字符// 定义括号映射关系HashMap<Character, Character> map = new HashMap<>();map.put(')', '('); // 右圆括号对应左圆括号map.put(']', '['); // 右方括号对应左方括号map.put('}', '{'); // 右花括号对应左花括号// 使用栈来检查括号是否匹配LinkedList<Character> stack = new LinkedList<>();// 遍历处理后的字符串for (int i = 0; i < s.length(); i++) {char c = s.charAt(i); // 获取当前字符// 如果栈不为空，且当前字符是右括号if (stack.size() > 0 && map.containsKey(c)) {// 检查栈顶元素是否是对应的左括号if (stack.getLast() == map.get(c)) {stack.removeLast(); // 匹配成功，弹出栈顶元素continue;} else {return false; // 匹配失败，返回 false}}// 将当前字符压入栈中stack.add(c);}// 如果栈为空，说明所有括号都匹配成功return stack.size() == 0;}
}

代码逻辑讲解

1. 输入获取
  • 使用 Scanner 类从控制台读取输入。
  • 调用 sc.nextLine() 读取一行输入，并将其存储在字符串 s 中。
2. 算法入口
  • 步骤 1：使用正则表达式去除非括号字符。
    • 正则表达式 [^\\(\\)\\[\\]\\{\\}] 表示匹配所有非括号字符。
    • 例如，输入 "a(b{c}d)e"，处理后得到 "({})"。
  • 步骤 2：定义括号映射关系 map。
    • 使用 HashMap 存储右括号和左括号的对应关系。
  • 步骤 3：使用栈 stack 来检查括号是否匹配。
    • 遍历处理后的字符串：
      • 如果当前字符是右括号，检查栈顶元素是否是对应的左括号。
        • 如果匹配成功，弹出栈顶元素。
        • 如果匹配失败，返回 false。
      • 如果当前字符是左括号，直接压入栈中。
  • 步骤 4：遍历结束后，检查栈是否为空。
    • 如果栈为空，说明所有括号都匹配成功，返回 true。
    • 如果栈不为空，说明有未匹配的括号，返回 false。

示例运行

输入
a(b{c}d)e
处理步骤
  1. 去除非括号字符，得到 "({})"。
  2. 遍历字符串：
    • 遇到 "("，压入栈中，栈为 ["("]。
    • 遇到 "{"，压入栈中，栈为 ["(", "{"]。
    • 遇到 "}"，检查栈顶元素 "{"，匹配成功，弹出栈顶元素，栈为 ["("]。
    • 遇到 ")"，检查栈顶元素 "("，匹配成功，弹出栈顶元素，栈为 []。
  3. 遍历结束，栈为空，返回 true。
输出
true

总结

  • 功能：检查输入字符串中的括号是否匹配。
  • 核心逻辑：
    1. 去除非括号字符。
    2. 使用栈检查括号是否匹配。
  • 适用场景：需要检查括号匹配的场景，例如代码语法检查。
  • 注意事项：
    • 输入字符串可能包含非括号字符，需要先去除。
    • 栈的使用是解决括号匹配问题的经典方法。

如果有其他问题，欢迎随时提问！

四、Python算法源码

以下是 Python 代码 的详细中文注释和逻辑讲解：

Python 代码

import re  # 导入正则表达式模块# 输入获取
s = input()  # 从控制台读取一行输入# 算法入口
def getResult(s):# 去除非括号字符s = re.sub(r"[^\(\)\[\]\{\}]", "", s)  # 使用正则表达式去除非括号字符# 定义括号映射关系map = {")": "(",  # 右圆括号对应左圆括号"]": "[",  # 右方括号对应左方括号"}": "{",  # 右花括号对应左花括号}# 使用栈来检查括号是否匹配stack = []# 遍历处理后的字符串for i in range(len(s)):c = s[i]  # 获取当前字符# 如果栈不为空，且当前字符是右括号if len(stack) > 0 and map.get(c) is not None:# 检查栈顶元素是否是对应的左括号if stack[-1] == map[c]:stack.pop()  # 匹配成功，弹出栈顶元素continueelse:return False  # 匹配失败，返回 False# 将当前字符压入栈中stack.append(c)# 如果栈为空，说明所有括号都匹配成功return len(stack) == 0# 算法调用
print(str(getResult(s)).lower())  # 调用 getResult 方法处理输入，并输出结果（转换为小写）

代码逻辑讲解

1. 输入获取
  • 使用 input() 函数从控制台读取一行输入，并将其存储在变量 s 中。
2. 算法入口
  • 步骤 1：使用正则表达式去除非括号字符。
    • 正则表达式 r"[^\(\)\[\]\{\}]" 表示匹配所有非括号字符。
    • 例如，输入 "a(b{c}d)e"，处理后得到 "({})"。
  • 步骤 2：定义括号映射关系 map。
    • 使用字典存储右括号和左括号的对应关系。
  • 步骤 3：使用栈 stack 来检查括号是否匹配。
    • 遍历处理后的字符串：
      • 如果当前字符是右括号，检查栈顶元素是否是对应的左括号。
        • 如果匹配成功，弹出栈顶元素。
        • 如果匹配失败，返回 False。
      • 如果当前字符是左括号，直接压入栈中。
  • 步骤 4：遍历结束后，检查栈是否为空。
    • 如果栈为空，说明所有括号都匹配成功，返回 True。
    • 如果栈不为空，说明有未匹配的括号，返回 False。
3. 算法调用
  • 调用 getResult(s) 方法处理输入，并将结果转换为字符串后输出（转换为小写）。

示例运行

输入
a(b{c}d)e
处理步骤
  1. 去除非括号字符，得到 "({})"。
  2. 遍历字符串：
    • 遇到 "("，压入栈中，栈为 ["("]。
    • 遇到 "{"，压入栈中，栈为 ["(", "{"]。
    • 遇到 "}"，检查栈顶元素 "{"，匹配成功，弹出栈顶元素，栈为 ["("]。
    • 遇到 ")"，检查栈顶元素 "("，匹配成功，弹出栈顶元素，栈为 []。
  3. 遍历结束，栈为空，返回 True。
输出
true

总结

  • 功能：检查输入字符串中的括号是否匹配。
  • 核心逻辑：
    1. 去除非括号字符。
    2. 使用栈检查括号是否匹配。
  • 适用场景：需要检查括号匹配的场景，例如代码语法检查。
  • 注意事项：
    • 输入字符串可能包含非括号字符，需要先去除。
    • 栈的使用是解决括号匹配问题的经典方法。

如果有其他问题，欢迎随时提问！

五、C/C++算法源码：

以下是 C++ 代码 和 C 语言代码 的实现，并附带详细的中文注释和逻辑讲解。

C++ 代码

#include <iostream>
#include <stack>
#include <unordered_map>
#include <string>
using namespace std;// 算法入口
bool getResult(string s) {// 去除非括号字符string filtered;for (char c : s) {if (c == '(' || c == ')' || c == '[' || c == ']' || c == '{' || c == '}') {filtered += c; // 只保留括号字符}}// 定义括号映射关系unordered_map<char, char> map = {{')', '('},{']', '['},{'}', '{'}};// 使用栈来检查括号是否匹配stack<char> stack;// 遍历处理后的字符串for (char c : filtered) {// 如果栈不为空，且当前字符是右括号if (!stack.empty() && map.count(c)) {// 检查栈顶元素是否是对应的左括号if (stack.top() == map[c]) {stack.pop(); // 匹配成功，弹出栈顶元素continue;} else {return false; // 匹配失败，返回 false}}// 将当前字符压入栈中stack.push(c);}// 如果栈为空，说明所有括号都匹配成功return stack.empty();
}int main() {// 输入获取string s;getline(cin, s); // 读取一行输入// 算法调用cout << boolalpha << getResult(s) << endl; // 输出结果（boolalpha 用于输出 true/false）return 0;
}

C++ 代码逻辑讲解

1. 输入获取
  • 使用 getline(cin, s) 从控制台读取一行输入，并将其存储在字符串 s 中。
2. 算法入口
  • 步骤 1：去除非括号字符。
    • 遍历字符串 s，只保留括号字符（(, ), [, ], {, }）。
    • 将过滤后的字符存储在 filtered 字符串中。
  • 步骤 2：定义括号映射关系 map。
    • 使用 unordered_map 存储右括号和左括号的对应关系。
  • 步骤 3：使用栈 stack 来检查括号是否匹配。
    • 遍历处理后的字符串 filtered：
      • 如果当前字符是右括号，检查栈顶元素是否是对应的左括号。
        • 如果匹配成功，弹出栈顶元素。
        • 如果匹配失败，返回 false。
      • 如果当前字符是左括号，直接压入栈中。
  • 步骤 4：遍历结束后，检查栈是否为空。
    • 如果栈为空，说明所有括号都匹配成功，返回 true。
    • 如果栈不为空，说明有未匹配的括号，返回 false。
3. 算法调用
  • 调用 getResult(s) 方法处理输入，并输出结果（boolalpha 用于输出 true/false 而不是 1/0）。

C 语言代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>// 定义栈结构
typedef struct {char data[1000]; // 栈数据int top;         // 栈顶指针
} Stack;// 初始化栈
void initStack(Stack *stack) {stack->top = -1;
}// 压栈
void push(Stack *stack, char c) {stack->data[++stack->top] = c;
}// 弹栈
char pop(Stack *stack) {return stack->data[stack->top--];
}// 获取栈顶元素
char top(Stack *stack) {return stack->data[stack->top];
}// 判断栈是否为空
bool isEmpty(Stack *stack) {return stack->top == -1;
}// 算法入口
bool getResult(char *s) {// 去除非括号字符char filtered[1000];int j = 0;for (int i = 0; s[i] != '\0'; i++) {if (s[i] == '(' || s[i] == ')' || s[i] == '[' || s[i] == ']' || s[i] == '{' || s[i] == '}') {filtered[j++] = s[i]; // 只保留括号字符}}filtered[j] = '\0'; // 字符串结束符// 定义括号映射关系char map[256] = {0};map[')'] = '(';map[']'] = '[';map['}'] = '{';// 使用栈来检查括号是否匹配Stack stack;initStack(&stack);// 遍历处理后的字符串for (int i = 0; filtered[i] != '\0'; i++) {char c = filtered[i];// 如果栈不为空，且当前字符是右括号if (!isEmpty(&stack) && map[c] != 0) {// 检查栈顶元素是否是对应的左括号if (top(&stack) == map[c]) {pop(&stack); // 匹配成功，弹出栈顶元素continue;} else {return false; // 匹配失败，返回 false}}// 将当前字符压入栈中push(&stack, c);}// 如果栈为空，说明所有括号都匹配成功return isEmpty(&stack);
}int main() {// 输入获取char s[1000];fgets(s, sizeof(s), stdin); // 读取一行输入// 算法调用printf("%s\n", getResult(s) ? "true" : "false"); // 输出结果return 0;
}

C 语言代码逻辑讲解

1. 输入获取
  • 使用 fgets(s, sizeof(s), stdin) 从控制台读取一行输入，并将其存储在字符数组 s 中。
2. 算法入口
  • 步骤 1：去除非括号字符。
    • 遍历字符串 s，只保留括号字符（(, ), [, ], {, }）。
    • 将过滤后的字符存储在 filtered 字符数组中。
  • 步骤 2：定义括号映射关系 map。
    • 使用字符数组 map 存储右括号和左括号的对应关系。
  • 步骤 3：使用栈 stack 来检查括号是否匹配。
    • 遍历处理后的字符串 filtered：
      • 如果当前字符是右括号，检查栈顶元素是否是对应的左括号。
        • 如果匹配成功，弹出栈顶元素。
        • 如果匹配失败，返回 false。
      • 如果当前字符是左括号，直接压入栈中。
  • 步骤 4：遍历结束后，检查栈是否为空。
    • 如果栈为空，说明所有括号都匹配成功，返回 true。
    • 如果栈不为空，说明有未匹配的括号，返回 false。
3. 算法调用
  • 调用 getResult(s) 方法处理输入，并输出结果（true 或 false）。

总结

  • 功能：检查输入字符串中的括号是否匹配。
  • 核心逻辑：
    1. 去除非括号字符。
    2. 使用栈检查括号是否匹配。
  • 适用场景：需要检查括号匹配的场景，例如代码语法检查。
  • 注意事项：
    • 输入字符串可能包含非括号字符，需要先去除。
    • 栈的使用是解决括号匹配问题的经典方法。

如果有其他问题，欢迎随时提问！

http://www.lryc.cn/news/519880.html

相关文章：

  • 解锁企业数字化转型新力量：OpenCoze（开源扣子）
  • 【网络云SRE运维开发】2025第2周-每日【2025/01/12】小测-【第12章 rip路由协议】理论和实操考试题解析
  • 【微服务】8、分布式事务 ( XA 和 AT )
  • CVE-2025-22777 (CVSS 9.8)：WordPress | GiveWP 插件的严重漏洞
  • TypeScript Jest 单元测试 搭建
  • 基于 SSH 的任务调度系统
  • filestream安装使用全套+filebeat的模块用法
  • java项目之房屋租赁系统源码（springboot+mysql+vue）
  • sap mm学习笔记
  • 代码随想录_链表
  • EF Code 并发控制
  • ceph fs status 输出详解
  • FFmpeg Muxer HLS
  • 如何用SQL语句来查询表或索引的行存/列存存储方式｜OceanBase 用户问题集锦
  • 回归预测 | MATLAB实GRU多输入单输出回归预测
  • 【OpenGL/Assimp】渲染模型、半透明材质与封装光源
  • pandas与sql对应关系【帮助sql使用者快速上手pandas】
  • Linux WEB漏洞
  • 音视频入门基础：RTP专题（2）——使用FFmpeg命令生成RTP流
  • 大语言模型预训练、微调、RLHF
  • vue3后台系统动态路由实现
  • 解决idea中无法拖动tab标签页的问题
  • WMS仓库管理系统，Vue前端开发，Java后端技术源码（源码学习）
  • 25/1/12 嵌入式笔记 学习esp32
  • 【NLP】ELMO、GPT、BERT、BART模型解读及对比分析
  • go语言学习(数组,切片,字符串)
  • PM 实战 - 智能药盒PRD + 市场规模分析
  • SQL刷题快速入门（二）
  • hive迁移后修复分区慢，怎么办？
  • 代码随想录算法训练营day27