华为OD机试 - 括号匹配 - 栈（Python/JS/C/C++ 2024 E卷 100分）

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

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

二、输入描述

无

三、输出描述

无

四、测试用例

测试用例1：

1、输入

(1+2)/(0.5+1)

2、输出

true

3、说明

测试用例2：

1、输入

([{}])

2、输出

true

3、说明

五、解题思路

1、栈

栈的先进后出（LIFO）特性非常适合用于括号匹配问题，因为每一个右括号都需要与最近的未匹配的左括号进行配对。

栈用于跟踪左括号的出现。当遇到一个左括号时，将其压入栈中；当遇到一个右括号时，从栈中弹出一个左括号并检查是否匹配。如果在弹出时栈为空，说明有多余的右括号，匹配错误。

2、具体步骤：

1. 遍历字符串： 从左到右逐个字符遍历字符串。
2. 处理左括号： 遇到左括号 (、[、{ 时，将其压入栈中。
3. 处理右括号：
   • 如果栈不为空，弹出栈顶的左括号，检查是否与当前右括号匹配。
   • 如果栈为空，说明有多余的右括号，返回false。
     最终检查： 遍历结束后，检查栈是否为空。如果栈为空，说明所有括号都匹配正确，返回true；否则，说明有未匹配的左括号，返回false。

3、复杂度分析

时间复杂度： O(n)，其中n是字符串的长度，遍历一次字符串即可完成匹配检查。

空间复杂度： O(n)，最坏情况下，所有字符都是左括号，需要将它们全部压入栈中。

六、Python算法源码

# 导入所需的模块
import sysdef check_brackets(expr):# 使用列表模拟栈stack = []# 定义括号对应关系bracket_map = {')': '(', ']': '[', '}': '{'}# 遍历表达式中的每个字符for ch in expr:if ch in bracket_map.values():# 如果是左括号，压入栈中stack.append(ch)elif ch in bracket_map:# 如果是右括号if not stack:# 栈为空，说明没有对应的左括号return Falseif stack[-1] == bracket_map[ch]:# 栈顶的左括号与当前右括号匹配，弹出栈顶stack.pop()else:# 栈顶的左括号与当前右括号不匹配return False# 其他字符忽略# 最后检查栈是否为空return not stackdef main():# 读取输入字符串并去除前后空格expression = sys.stdin.readline().strip()# 调用检查函数is_valid = check_brackets(expression)# 输出结果print(str(is_valid).lower())if __name__ == "__main__":main()

七、JavaScript算法源码

// 定义一个函数来检查括号匹配
function checkBrackets(expr) {const stack = []; // 使用数组模拟栈// 定义括号对应关系const bracketMap = {')': '(',']': '[','}': '{'};// 遍历表达式中的每个字符for (let ch of expr) {if (['(', '[', '{'].includes(ch)) {// 如果是左括号，压入栈中stack.push(ch);} else if ([')', ']', '}'].includes(ch)) {// 如果是右括号if (stack.length === 0) {// 栈为空，说明没有对应的左括号return false;}if (stack[stack.length - 1] === bracketMap[ch]) {// 栈顶的左括号与当前右括号匹配，弹出栈顶stack.pop();} else {// 栈顶的左括号与当前右括号不匹配return false;}}// 其他字符忽略}// 最后检查栈是否为空return stack.length === 0;
}// 读取标准输入并处理
const readline = require('readline');// 创建接口以读取输入
const rl = readline.createInterface({input: process.stdin,output: process.stdout
});// 读取输入后处理
rl.on('line', (input) => {const expression = input.trim(); // 去除前后空格const isValid = checkBrackets(expression); // 调用检查函数console.log(isValid); // 输出结果（true 或 false）rl.close(); // 关闭输入流
});

八、C算法源码

#include <stdio.h>
#include <string.h>// 定义栈的最大容量
#define MAX 100// 定义一个栈结构
typedef struct {char data[MAX]; // 存储栈内字符int top;        // 栈顶指针
} Stack;// 初始化栈
void initStack(Stack *s) {s->top = -1; // 栈顶初始化为-1，表示栈为空
}// 判断栈是否为空
int isEmpty(Stack *s) {return s->top == -1;
}// 判断栈是否满
int isFull(Stack *s) {return s->top == MAX - 1;
}// 入栈操作
void push(Stack *s, char ch) {if (!isFull(s)) {s->data[++(s->top)] = ch; // 将字符压入栈中，并移动栈顶指针}
}// 出栈操作
char pop(Stack *s) {if (!isEmpty(s)) {return s->data[(s->top)--]; // 弹出栈顶字符，并移动栈顶指针}return '\0'; // 如果栈为空，返回空字符
}// 判断左右括号是否匹配
int isMatchingPair(char left, char right) {if (left == '(' && right == ')')return 1;if (left == '[' && right == ']')return 1;if (left == '{' && right == '}')return 1;return 0;
}// 检查括号匹配函数
int checkBrackets(char *expr) {Stack stack;initStack(&stack); // 初始化栈// 遍历表达式中的每个字符for (int i = 0; i < strlen(expr); i++) {char ch = expr[i];if (ch == '(' || ch == '[' || ch == '{') {push(&stack, ch); // 如果是左括号，压入栈中}else if (ch == ')' || ch == ']' || ch == '}') {if (isEmpty(&stack)) {// 栈为空，说明没有对应的左括号return 0; // false}char top = pop(&stack); // 弹出栈顶的左括号if (!isMatchingPair(top, ch)) {// 左右括号不匹配return 0; // false}}// 其他字符忽略}// 最后检查栈是否为空if (isEmpty(&stack)) {return 1; // true}else {return 0; // false}
}int main() {char expression[101]; // 定义表达式字符串，最多100字符// 读取输入表达式if (fgets(expression, sizeof(expression), stdin) != NULL) {// 移除末尾的换行符size_t len = strlen(expression);if (len > 0 && expression[len - 1] == '\n') {expression[len - 1] = '\0';}// 调用检查函数int isValid = checkBrackets(expression);// 输出结果if (isValid)printf("true\n");elseprintf("false\n");}return 0;
}

九、C++算法源码

#include <iostream>
#include <stack>
#include <string>
using namespace std;// 检查括号匹配函数
bool checkBrackets(const string &expr) {stack<char> s; // 使用标准库中的栈// 定义括号对应关系// 不需要显式定义，因为可以直接在判断中处理// 遍历表达式中的每个字符for (char ch : expr) {if (ch == '(' || ch == '[' || ch == '{') {// 如果是左括号，压入栈中s.push(ch);}else if (ch == ')' || ch == ']' || ch == '}') {if (s.empty()) {// 栈为空，说明没有对应的左括号return false;}char top = s.top(); // 获取栈顶的左括号// 判断是否匹配if ((ch == ')' && top == '(') ||(ch == ']' && top == '[') ||(ch == '}' && top == '{')) {s.pop(); // 匹配，弹出栈顶}else {// 不匹配return false;}}// 其他字符忽略}// 最后检查栈是否为空return s.empty();
}int main() {string expression;// 读取整行输入getline(cin, expression);// 调用检查函数bool isValid = checkBrackets(expression);// 输出结果（小写 true 或 false）if (isValid)cout << "true" << endl;elsecout << "false" << endl;return 0;
}

🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）

🏆本文收录于，华为OD机试真题（Python/JS/C/C++）

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。