用 C 语言实现判断给定字符串是否平衡的算法:
时间: 2024-09-25 22:16:45 浏览: 45
PHP实现求两个字符串最长公共子串的方法示例
在C语言中,判断一个给定的字符串是否是平衡字符串(也称为有效括号字符串),可以使用栈的数据结构来实现。平衡字符串是指由 '(', ')' 和 '{}' 这样的左闭合括号和右闭合括号组成,且每个打开的括号都有一个匹配的关闭括号。
这里是一个简单的算法步骤:
1. 定义一个空栈 `stack` 用于存储遍历过程中的开括号。
2. 遍历输入字符串中的每一个字符,如果遇到左括号 ('(', '{', '['),将其压入栈中。
3. 如果遇到右括号 (')', '}', ']'),检查栈顶元素是否是对应的左括号。如果是,弹出栈顶元素;如果不是,则返回 false,因为找到了不匹配的括号对。
4. 遍历完成后,如果栈为空,说明所有括号都已配对完成,返回 true;否则,返回 false,表示存在未关闭的括号。
下面是一个简单的C语言函数实现:
```c
#include <stdbool.h>
#include <stdio.h>
bool isBalanced(char str[]) {
stack_t *stack = (stack_t *)malloc(sizeof(stack_t));
int i = 0;
// 定义一个结构体来表示括号
typedef struct _stack_t {
char symbol;
bool exists;
} stack_t;
stack_t node;
node.symbol = '\0';
node.exists = false;
stack->top = -1;
while (str[i] != '\0') {
switch (str[i]) {
case '(':
case '{':
case '[':
node.symbol = str[i];
stack->top++;
stack->items[stack->top] = node;
break;
case ')':
case '}':
case ']':
if (stack->top == -1) return false; // 空栈,直接返回错误
node = stack->items[stack->top]; // 获取栈顶节点
if (node.symbol == '(' && str[i] == ')') {
stack->top--;
} else if (node.symbol == '{' && str[i] == '}') {
stack->top--;
} else if (node.symbol == '[' && str[i] == ']') {
stack->top--;
} else {
return false; // 匹配失败
}
break;
}
i++;
}
if (stack->top == -1) return true; // 括号都配对了
else return false; // 有剩余的括号
}
// 示例
int main() {
char str[] = "(({}))";
if (isBalanced(str))
printf("%s is a balanced string.\n", str);
else
printf("%s is not a balanced string.\n", str);
return 0;
}
```
阅读全文