求解添加最少括号数问题。括号序列由()、{}、[]组成,例如“(([{}]))()”是合法的,而“(}{)”、“({({”和“({)}”都是不合法的。如果一个序列不合法,可以通过添加合适的括号,使这个序列变成合法的。对于一个不合法的序列,编写一个程序求需添加的最少括号数。(C语言)
时间: 2024-02-09 16:07:50 浏览: 23
这个问题可以使用栈来解决。我们从左到右遍历括号序列,遇到左括号就将其推入栈中,遇到右括号就将栈顶的左括号弹出,如果弹出的左括号和右括号不匹配,则需要添加一个括号使得它们匹配。最后,如果栈为空,则括号序列合法,否则需要添加括号使得栈为空。
下面是代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct {
char *data;
int top;
int capacity;
} Stack;
Stack *createStack(int capacity) {
Stack *stack = (Stack *)malloc(sizeof(Stack));
stack->data = (char *)malloc(capacity * sizeof(char));
stack->top = -1;
stack->capacity = capacity;
return stack;
}
bool isStackEmpty(Stack *stack) {
return stack->top == -1;
}
void push(Stack *stack, char c) {
stack->top++;
stack->data[stack->top] = c;
}
char pop(Stack *stack) {
char c = stack->data[stack->top];
stack->top--;
return c;
}
void destroyStack(Stack *stack) {
free(stack->data);
free(stack);
}
int getMatchingParenthesis(char c) {
switch (c) {
case ')':
return '(';
case '}':
return '{';
case ']':
return '[';
default:
return 0;
}
}
int getMinParenthesisCount(char *s) {
int count = 0;
Stack *stack = createStack(100);
for (int i = 0; s[i] != '\0'; i++) {
if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
push(stack, s[i]);
} else if (s[i] == ')' || s[i] == '}' || s[i] == ']') {
if (isStackEmpty(stack) || pop(stack) != getMatchingParenthesis(s[i])) {
count++;
}
}
}
if (!isStackEmpty(stack)) {
count += stack->top + 1;
}
destroyStack(stack);
return count;
}
int main() {
char s[100];
printf("请输入括号序列:");
scanf("%s", s);
int count = getMinParenthesisCount(s);
printf("需要添加的最少括号数为:%d\n", count);
return 0;
}
```
这个程序的时间复杂度是 O(n),其中 n 是括号序列的长度。