我正在努力解决括号匹配的问题，即给定一个左括号和右括号exp的序列，由(或)、方括号[或]或大括号}或{组成，我需要判断给定的序列是否平衡。
Sample Input1:
exp = "[]{}()"
Sample Output1:
Match Successfull....!
----------
Sample Input2:
exp = "[]{(]}()"
Sample Output1:
Match not Successfull....!
PS：空字符串被认为是平衡字符串
下面是用C编写的代码，我试图用struct实现一个堆栈。我实现了堆栈的所有必要功能，即pop()、push()、isFull()等。
然而，我遇到了分段错误。请帮我纠正这个错误。
#include <stdio.h>
#include <stdlib.h>
struct stack {
int size;
int top;
char *arr;
};
int isEmpty(struct stack *ptr) {
if (ptr->top == -1)
{
return 1;
}
return 0;
}
int isFull(struct stack *ptr) {
if (ptr->top == ptr->size - 1)
{
return 1;
}
return 0;
}
int push(struct stack *ptr, char val) {
if (isFull(ptr))
{
return 1;
}
else
{
ptr->top++;
ptr->arr[ptr->top] = val;
}
}
int pop(struct stack *ptr) {
char val;
if (isEmpty(ptr))
{
return 1;
}
else
{
ptr->top--;
val = ptr->arr[ptr->top];
return val;
}
}
int match(char a, char b) {
if (a == '{' && b == '}' || a == '(' && b == ')' || a == '[' && b == ']')
{
return 1;
}
else
{
return 0;
}
}
int parMatch(char *exp) {
struct stack *s = malloc(sizeof(struct stack));
s->arr = (char *)malloc(s->size * sizeof(char));
s->size = 100;
s->top = -1;
char char_pop;
for (int i = 0; exp[i] = ' '; i++)
{
if (exp[i] == '(' || exp[i] == '{' || exp[i] == '[')
{
push(s, exp[i]);
}
else if (exp[i] == ')' || exp[i] == '}' || exp[i] == ']')
{
return 0;
}
char_pop = pop(s);
if (!match(char_pop, exp[i]))
{
return 0;
}
}
if (isEmpty(s))
{
return 1;
}
else
{
return 0;
}
}
int main() {
char *exp = "[]{}()";
if (parMatch(exp))
{
printf("Match Successfull....!");
}
else
{
printf("Match not Successfull....!");
}
return 0;
}
代码导致错误的原因是由于for循环条件中的语句exp[i] = ' ';。这在逻辑上是不正确的(如下所述(，并且您不能修改使用char*声明的字符串。
你为什么这么问？阅读为什么在写入用字符串文字初始化的"char*s"而不是"chars[]"时出现分段错误？
您的代码中也有其他几个错误：
-
这不是在c、
char *exp = "[]{}()";中分配字符串的方式。虽然它确实有效，但它会生成警告，不推荐使用。已阅读将字符串分配给字符数组。 -
您尚未初始化
s->size，但正在s->arr = (char *)malloc(s->size * sizeof(char));行的malloc()中使用它。 -
您将
push()函数的返回类型声明为int，但在else条件之后没有返回任何内容。这是未来的一个潜在错误。它也会导致警告。 -
pop()函数的实现既有逻辑缺陷，也有语法缺陷。pop()函数的返回类型是int，但您返回的是char类型。此外，您首先递减ptr->top，然后在新的ptr->top位置返回字符，即，您最终返回当前顶部以下的字符。 -
这不是
exp[i] = ' '如何检查for循环的终止条件以结束c中的char*字符串。您应该改为编写exp[i] != ' '。 -
您在遇到
)或}或]时立即使用return 0;。相反，您应该检查是否可以从堆栈中弹出相应的大括号，如果是，则检查是否有其他字符else return 0;
以下是修复了上述所有错误的代码。
#include <stdio.h>
#include <stdlib.h>
struct stack {
int size;
int top;
char *arr;
};
int isEmpty(struct stack *ptr) {
if (ptr->top == -1)
{
return 1;
}
return 0;
}
int isFull(struct stack *ptr) {
if (ptr->top == ptr->size - 1)
{
return 1;
}
return 0;
}
int push(struct stack *ptr, char val) {
if (isFull(ptr))
{
return 1;
}
else
{
ptr->top++;
ptr->arr[ptr->top] = val;
}
return 0;
}
char pop(struct stack *ptr) {
char val;
if (isEmpty(ptr))
{
return ' ';
}
else
{
val = ptr->arr[ptr->top];
ptr->top--;
return val;
}
}
int match(char a, char b) {
if ((a == '{' && b == '}') || (a == '(' && b == ')') || (a == '[' && b == ']'))
{
return 1;
}
else
{
return 0;
}
}
int parMatch(char exp[]) {
struct stack *s = malloc(sizeof(struct stack));
s->size = 100;
s->arr = (char *)malloc(s->size * sizeof(char));
s->top = -1;
char char_pop;
for (int i = 0; exp[i] != ' '; i++)
{
if (exp[i] == '(' || exp[i] == '{' || exp[i] == '[')
{
push(s, exp[i]);
}
else if (exp[i] == ')' || exp[i] == '}' || exp[i] == ']')
{ // You have one closing brace but your stack is empty, then return 0
if (isEmpty(s))
{
return 0;
}
else
{ // If you reach here then it ensures that stack is not empty.
char_pop = pop(s);
if (!match(char_pop, exp[i]))
{
return 0;
}
}
}
}
if (isEmpty(s))
{
return 1;
}
else
{
return 0;
}
}
int main() {
char exp[100] = "{}}[](";
if (parMatch(exp))
{
printf("Match Successfull....!");
}
else
{
printf("Match not Successfull....!");
}
return 0;
}