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

华为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在线答疑。

在这里插入图片描述

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

相关文章:

  • 打破欧美10年芯片垄断,杨振宁教授关门弟子,仅用三年创造奇迹
  • OpenCV视频I/O(20)视频写入类VideoWriter之用于将图像帧写入视频文件函数write()的使用
  • 音视频入门基础:FLV专题(14)——FFmpeg源码中,解码Script Tag的实现
  • 小猿口算APP脚本(协议版)
  • 【长文梳理webserver核心】核心类篇
  • [实用工具]Docker安装nextcloud实现私有云服务和onlyoffice
  • 基于STM32设计的生猪健康检测管理系统(NBIOT+OneNet)(240)
  • springboot kafka多数据源,通过配置动态加载发送者和消费者
  • 【华为】基于华为交换机的VLAN配置与不同VLAN间通信实现
  • 力扣题11~20
  • 更美观的HTTP性能监测工具:httpstat
  • 在2024 VDC,听一曲“蓝心智能”的江河协奏
  • Python编写的数字光刻仿真程序,使用了Hopkins光刻模型和粒子群优化(PSO)算法来优化掩模设计
  • 【AD那些事 11】绘制PCB板时“隔离” 的那些事(笔记摘抄)
  • sublime配置(竞赛向)
  • 双向数据库迁移工具:轻松实现 MySQL 与 SQLite 数据互导
  • oracle查询表空间信息
  • 使用Python编写你的第一个算法交易程序
  • 点进HTML初步了解
  • 幸运的沈抖,进击的百度智能云
  • android广播实现PIN码设置
  • Mac 需要杀毒软件?
  • Java | Leetcode Java题解之第472题连接词
  • CUDA Graphs学习与实验
  • 【自注意力与Transformer架构在自然语言处理中的演变与应用】
  • LabVIEW交直流接触器动态检测系统
  • Unity3D中基于四叉树的范围检测算法详解
  • k8s网络通信
  • 07 欢乐的跳
  • 【韩顺平Java笔记】第8章:面向对象编程(中级部分)【262-271】