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

一、问题描述

题目描述

给定一个字符串，里边可能包含“()”、“[]”、“{}”三种括号，请编写程序检查该字符串中的括号是否成对出现，且嵌套关系正确。
若括号成对出现且嵌套关系正确，或该字符串中无括号字符，输出：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. 使用栈检查括号是否匹配。
• 适用场景：需要检查括号匹配的场景，例如代码语法检查。
• 注意事项：
  • 输入字符串可能包含非括号字符，需要先去除。
  • 栈的使用是解决括号匹配问题的经典方法。

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