平衡括号中的堆栈溢出

Question

我正在尝试编写一个程序来检查一串括号是否平衡。如果平衡，我不想要任何输出。但如果它不平衡，那么我希望它 return 平衡它所需的括号。例如，'([])' 应该是平衡的，'({}' 应该是不平衡的并且应该 return "open: )"。在我打开两个或更多括号之前，代码似乎可以正常工作。因此，如果我输入'({'，我的代码可以工作，但是当我添加更多字符（如'([])(['时，它会因为堆栈溢出而失败。我不明白错误可能是什么或如何解决它.

这是我的代码：

void push(struct sNode** top_ref, int new_data){
    struct sNode* new_node = (struct sNode*)malloc(sizeof(struct sNode));

    if (new_node == NULL) {
        printf("Stack overflow \n");
        getchar();
        exit(0);
    }

    new_node->data = new_data;
    new_node->next = (*top_ref);
    (*top_ref) = new_node;
}
int pop(struct sNode** top_ref){
    char res;
    struct sNode* top;
    
    if (*top_ref == NULL) {
        printf("Stack overflow \n");
        getchar();
        exit(0);
    }else {
        top = *top_ref;
        res = top->data;
        *top_ref = top->next;
        free(top);
        return res;
    }
}

// Returns 1 if character1 and character2 are matching left and right Brackets
bool isMatchingPair(char character1, char character2)
{
    if (character1 == '(' && character2 == ')')
        return 1;
    else if (character1 == '{' && character2 == '}')
        return 1;
    else if (character1 == '[' && character2 == ']')
        return 1;
    else
        return 0;
}

// Return 1 if expression is balanced
int areBracketsBalanced(char exp[]){
    int i = 0;
    struct sNode* stack = NULL;

    while (exp[i]){
        if (exp[i] == '{' || exp[i] == '(' || exp[i] == '[')
            push(&stack, exp[i]);

        if (exp[i] == '}' || exp[i] == ')' || exp[i] == ']') {

            if (stack == NULL){
                printf("%d:%c\n",i,exp[i]);
                return 0;
            }else if (!isMatchingPair(pop(&stack), exp[i])){
                printf("%d:%c\n",i,exp[i]);
                return 0;
            }
        }
        i++;
    }

    if (stack != NULL){
        printf("open: ");
        while(stack!=NULL){
            if(pop(&stack)=='('){
                printf("%c",')');
            }else if(pop(&stack)=='['){
                printf("%c",']');
            }else if(pop(&stack)=='{'){
                printf("%c",'}');
            }
        }
        printf("\n");
        return 0;
    }
    
    return 0;
}

int main(int argc, char* argv[])
{
    char *exp = (char *)malloc(strlen(argv[1]) * sizeof(char));
    for(int i = 0; i<strlen(argv[1]); i++){
        exp[i] = argv[1][i];
    }
    
    //char exp[] = "([])([";
    areBracketsBalanced(exp);
    
    return 0;
}

Answer 1

正如评论中指出的那样，main 中的 exp 是错误的，因为它最终没有零终止。实际上不需要它...只需将 argv[1] 传递给函数即可。

int main(int argc, char* argv[])
{
    if (argc > 1)
    {
        areBracketsBalanced(argv[1]);
    }
    else
    {
        puts("Missing argument");
    }
    
    return 0;
}

除此之外，你还有一个问题：

    while(stack!=NULL){
        if(pop(&stack)=='('){
            printf("%c",')');
        }else if(pop(&stack)=='['){
            printf("%c",']');
        }else if(pop(&stack)=='{'){
            printf("%c",'}');
        }
    }

这些 pop(&stack) 中的每一个都会更改 stack 并且可能导致它为 NULL。在最坏的情况下，您在检查 NULL 之前执行 3 次弹出操作。这样不好。

更改代码，以便在 if 语句之前有一个弹出操作。将结果保存在用于 if 语句的局部变量中。喜欢：

    while(stack!=NULL){
        int value = pop(&stack);
        if(value == '('){
            printf("%c",')');
        }else if(value == '['){
            printf("%c",']');
        }else if(value == '{'){
            printf("%c",'}');
        }
    }

平衡括号中的堆栈溢出

Stack Overflow in Balanced Parenthesis

c

stack-overflow

stack