C语言算法-解答有效的括号问题的C语言实现
题目
给定一个只包含 '(', ')', '{', '}', '[' 和 ']' 的字符串 s，判断 s 是否有效。有效字符串需满足以下条件：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
引言
有效的括号问题可以使用栈来解决，我们需要将左括号入栈，每次遇到右括号时，判断栈顶的左括号是否与之匹配。如果匹配，则将栈顶的左括号出栈，继续处理下一个字符；如果不匹配，或者栈为空，说明括号无效。解决这个问题需要使用栈数据结构和字符处理。
算法思路
我们将使用栈的方法来解决有效的括号问题。
算法的步骤如下：
- 创建一个栈
stack，用于存储左括号。 遍历字符串
s中的每个字符：- 如果当前字符是左括号 '(', '{' 或 '[', 将其入栈。
如果当前字符是右括号 ')', '}' 或 ']', 判断栈是否为空：
- 如果栈为空，返回 false，因为没有匹配的左括号。
如果栈不为空，判断栈顶的左括号与当前右括号是否匹配：
- 如果匹配，将栈顶的左括号出栈，继续处理下一个字符。
- 如果不匹配，返回 false，因为括号无效。
在遍历完字符串
s后，判断栈是否为空：- 如果栈为空，说明所有括号都有匹配的右括号，返回 true。
- 如果栈不为空，说明还有未匹配的左括号，返回 false。
代码实现
下面是使用C语言实现的代码：
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
typedef struct Stack {
char* data;
int top;
} Stack;
Stack* createStack(int capacity) {
Stack* stack = (Stack*)malloc(sizeof(Stack));
stack->data = (char*)malloc(sizeof(char) * capacity);
stack->top = -1;
return stack;
}
void push(Stack* stack, char ch) {
stack->top++;
stack->data[stack->top] = ch;
}
char pop(Stack* stack) {
char ch = stack->data[stack->top];
stack->top--;
return ch;
}
bool isValid(char* s) {
int length = strlen(s);
Stack* stack = createStack(length);
for (int i = 0; i < length; i++) {
char ch = s[i];
if (ch == '(' || ch == '{' || ch == '[') {
push(stack, ch);
} else if (ch == ')' || ch == '}' || ch == ']') {
if (stack->top == -1) {
return false;
}
char top = pop(stack);
if ((ch == ')' && top != '(') || (ch == '}' && top != '{') || (ch == ']' && top != '[')) {
return false;
}
}
}
if (stack->top != -1) {
return false;
}
return true;
}
int main() {
char* s1 = "()";
char* s2 = "()[]{}";
char* s3 = "(]";
char* s4 = "([)]";
char* s5 = "{[]}";
printf("%s is %s\n", s1, isValid(s1) ? "valid" : "invalid");
printf("%s is %s\n", s2, isValid(s2) ? "valid" : "invalid");
printf("%s is %s\n", s3, isValid(s3) ? "valid" : "invalid");
printf("%s is %s\n", s4, isValid(s4) ? "valid" : "invalid");
printf("%s is %s\n", s5, isValid(s5) ? "valid" : "invalid");
return 0;
}算法分析
该算法只需要对字符串进行一次遍历，并在栈上进行入栈和出栈操作，所以时间复杂度为 O(n)，其中 n 是字符串的长度。
空间复杂度为 O(n)，算法使用了额外的栈来存储左括号。
示例和测试
示例输入1:
s = "()"示例输出1:
valid示例输入2:
s = "()[]{}"示例输出2:
valid示例输入3:
s = "(]"示例输出3:
invalid示例输入4:
s = "([)]"示例输出4:
invalid示例输入5:
s = "{[]}"示例输出5:
valid总结
本文使用C语言实现了解答有效的括号问题的代码。通过使用栈数据结构和字符处理，我们能够判断给定的括号字符串是否有效。该算法的时间复杂度为 O(n)，空间复杂度为 O(n)。
