监控性能网站模板,免费云服务器主机,2016年做水果行业专业网站,住房城乡建设部官网站一、问题描述
题目描述
给定一个字符串#xff0c;里边可能包含“()”、“[]”、“{}”三种括号#xff0c;请编写程序检查该字符串中的括号是否成对出现#xff0c;且嵌套关系正确。 若括号成对出现且嵌套关系正确#xff0c;或该字符串中无括号字符#xff0c;输出里边可能包含“()”、“[]”、“{}”三种括号请编写程序检查该字符串中的括号是否成对出现且嵌套关系正确。 若括号成对出现且嵌套关系正确或该字符串中无括号字符输出true 若未正确使用括号字符输出false。 实现时无需考虑非法输入。
输入描述
无
输出描述
无
用例
用例 1
输入:
(12)/(0.51)输出:
true解题思路 使用栈 使用一个栈来跟踪未匹配的左括号。遍历字符串对于每个字符 如果是左括号(, [, {将其压入栈中。如果是右括号), ], }检查栈顶是否有对应的左括号 如果有弹出栈顶的左括号。如果没有返回 false。 遍历结束后如果栈为空说明所有括号都正确匹配返回 true。如果栈不为空说明有未匹配的左括号返回 false。 特殊情况 如果字符串中没有括号字符直接返回 true。
详细步骤 读取输入 从标准输入读取一个字符串。 初始化栈 创建一个空栈 stack用于存储未匹配的左括号。 遍历字符串 遍历字符串中的每个字符 char 如果 char 是左括号(, [, {将其压入栈中。如果 char 是右括号), ], } 检查栈顶是否有对应的左括号 如果有弹出栈顶的左括号。如果没有返回 false。 检查栈是否为空 遍历结束后如果栈为空返回 true。如果栈不为空返回 false。
用例解释
用例 1
输入 (12)/(0.51) 输出 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处理步骤
去除非括号字符得到 ({})。遍历字符串 遇到 (压入栈中栈为 [(]。遇到 {压入栈中栈为 [(, {]。遇到 }检查栈顶元素 {匹配成功弹出栈顶元素栈为 [(]。遇到 )检查栈顶元素 (匹配成功弹出栈顶元素栈为 []。 遍历结束栈为空返回 true。
输出
true总结
功能检查输入字符串中的括号是否匹配。核心逻辑 去除非括号字符。使用栈检查括号是否匹配。 适用场景需要检查括号匹配的场景例如代码语法检查。注意事项 输入字符串可能包含非括号字符需要先去除。栈的使用是解决括号匹配问题的经典方法。
如果有其他问题欢迎随时提问
三、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([^\\(\\)\\[\\]\\{\\}], ); // 使用正则表达式去除非括号字符// 定义括号映射关系HashMapCharacter, Character map new HashMap();map.put(), (); // 右圆括号对应左圆括号map.put(], [); // 右方括号对应左方括号map.put(}, {); // 右花括号对应左花括号// 使用栈来检查括号是否匹配LinkedListCharacter 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处理步骤
去除非括号字符得到 ({})。遍历字符串 遇到 (压入栈中栈为 [(]。遇到 {压入栈中栈为 [(, {]。遇到 }检查栈顶元素 {匹配成功弹出栈顶元素栈为 [(]。遇到 )检查栈顶元素 (匹配成功弹出栈顶元素栈为 []。 遍历结束栈为空返回 true。
输出
true总结
功能检查输入字符串中的括号是否匹配。核心逻辑 去除非括号字符。使用栈检查括号是否匹配。 适用场景需要检查括号匹配的场景例如代码语法检查。注意事项 输入字符串可能包含非括号字符需要先去除。栈的使用是解决括号匹配问题的经典方法。
如果有其他问题欢迎随时提问
四、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处理步骤
去除非括号字符得到 ({})。遍历字符串 遇到 (压入栈中栈为 [(]。遇到 {压入栈中栈为 [(, {]。遇到 }检查栈顶元素 {匹配成功弹出栈顶元素栈为 [(]。遇到 )检查栈顶元素 (匹配成功弹出栈顶元素栈为 []。 遍历结束栈为空返回 True。
输出
true总结
功能检查输入字符串中的括号是否匹配。核心逻辑 去除非括号字符。使用栈检查括号是否匹配。 适用场景需要检查括号匹配的场景例如代码语法检查。注意事项 输入字符串可能包含非括号字符需要先去除。栈的使用是解决括号匹配问题的经典方法。
如果有其他问题欢迎随时提问
五、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_mapchar, char map {{), (},{], [},{}, {}};// 使用栈来检查括号是否匹配stackchar 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/falsereturn 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。 总结
功能检查输入字符串中的括号是否匹配。核心逻辑 去除非括号字符。使用栈检查括号是否匹配。 适用场景需要检查括号匹配的场景例如代码语法检查。注意事项 输入字符串可能包含非括号字符需要先去除。栈的使用是解决括号匹配问题的经典方法。
如果有其他问题欢迎随时提问
