用 c 中的堆栈检查字符串中的平衡括号

Question

我正在尝试编写一个程序，在其中我使用数组实现堆栈并使用它们来检查给定字符串是否具有平衡括号。

例如。如果输入'(()){}[()]'，程序将输出'Balanced'，否则如果输入'({})['，程序将输出'Not balanced'.

这部分是栈的数组实现

#include <stdio.h>
#include <stdlib.h>

#define MAX 50

int stack[MAX];
int top=-1;

void push(char val){
    if(top==MAX-1){
        printf("stack is already full,error\n");
    
    }else{
        top++;
        stack[top]=val;
    }
}

char pop(){
    if(top==-1){
        printf("not enough elements,error\n");
        exit(1);
    }else{
        top--;
        return stack[top];
    }
}

这部分是解决问题的常用方法的实现。

int isMatching(char c1, char c2){ 
    if(c1=='{' && c2=='}') 
        return 1; 
        
    else if(c1 =='(' && c2==')') 
        return 1; 
        
    else if(c1=='[' && c2==']') 
        return 1; 
    
    return 0; 
} 

int isBalanced(char str[]){
    int i=0;
    
    while(str[i]!='[=11=]'){
        if(str[i]=='{' || str[i]=='[' || str[i]=='('){
            push(str[i]);
        }
        if(str[i]==')' || str[i] == ']' || str[i]=='}'){ 
            if(stack==NULL){
                return 0; 
            }
            if(!isMatching(pop(), str[i])){
                return 0;
            }
        } 
        i++; 

    }
    
    if(stack==NULL){
        return 1; // balanced parenthesis
    }else{
        return 0; // not balanced parenthesis
    }
}

这是主要功能，用户输入字符串并测试它是否为 'Balanced'。

int main(){
    char str[MAX];
    int flag;
    printf("Enter the string with the brackets and etc.\n");
    fgets(str, sizeof(str),stdin); 
    flag=isBalanced(str);
    if(flag==1){
        printf("Balanced\n");
    }
    else{
        printf("Not balanced\n"); 
    }
    
    return 0;
}

当我输入一个非常简单的例子时，我得到了一个错误的答案，例如

Enter the string with the brackets and etc.
()
Not balanced

这应该输出 'Balanced' instead.I 不明白这是怎么发生的。

Answer 1

if (stack==NULL) 是这里的问题，堆栈永远不会为 NULL。您需要通过验证 top > 0

来检查堆栈中是否还有元素

Answer 2

在 pop() 中，您在返回顶部元素之前递减。变化：

    top--;
    return stack[top];

到

    return stack[top--];

此外，在 isBalanced() 中，堆栈永远不会为空，因此删除：

        if(stack==NULL){
            return 0; 
        }

并更改平衡检查以从以下位置查找空堆栈：

if(stack==NULL){
    return 1; // balanced parenthesis
}else{
    return 0; // not balanced parenthesis
}

收件人：

if(top==-1){
    return 1; // balanced parenthesis
}else{
    return 0; // not balanced parenthesis
}

进行这些更改后，您的代码似乎可以在我的盒子上运行。这不是我的编码方式，但这是使其工作的最小更改集。

Answer 3

您实施的 push/pop 组合错误。如果您压入一个字符 top 变为 0。如果您立即弹出它，它最终会执行 top--; return stack[top]，计算结果为堆栈 [-1]。

试试这个 push/pop:

int top=-1; //idx to be popped next; <0 -> invalid

void push(char val)
{
    if(top==MAX-2)
        printf("stack is already full,error\n");
    else
        stack[++top]=val;
}

char pop()
{
    if(top<0) return '[=10=]'; //no abort, just return invalid char
    return stack[top--];
}

Answer 4

您的问题的答案已经得到令人满意的回答，但作为对不同方法的建议，请考虑以下内容。

由于在 C 源代码中只使用了极少数的公共封装，您可以使用递增-递减计数器轻松地跟踪成对的它们。下面使用一个结构体，typedefed to balanced_s 封装成一个函数来简化求值。以下是示例实现：

typedef struct {
    int paren;
    int curly;
    int square;
    bool bBal
}balanced_s;

balanced_s * balanced_enclosures(const char *source);

int main(void)
{
    char in[5000] = {0};//you could improve this by reading file size 
                        //first then creating array sized accordingly
    
    FILE *fp = fopen("C:\play\source.c", "r");//using copy of this source to test
    if(fp)
    {
        size_t bytes = fread(in, 1, sizeof(in), fp);
    }
    
    balanced_s * b = balanced_enclosures(in);
    
    bool balanced = b->bBal;//If not true, inspect the rest of the
                            //members to see where the imbalance has occurred.
    
    free(b);
    
    return 0;
}

balanced_s * balanced_enclosures(const char *source)
{
    balanced_s *pBal = malloc(sizeof(*pBal));
    memset(pBal, 0, sizeof(*pBal));
    
    while(*source)
    {
        switch(*source) {
            case '(':
                pBal->paren++;
                break;
            case ')':
                pBal->paren--;
                break;
            case '{':
                pBal->curly++;
                break;
            case '}':
                pBal->curly--;
                break;
            case '[':
                pBal->square++;
                break;
            case ']':
                pBal->square--;
                break;
        }
        source++;
        pBal->bBal = (!pBal->paren && !pBal->curly && !pBal->square);
    }
    return pBal;
}

用 c 中的堆栈检查字符串中的平衡括号

Checking balanced parentheses in a string with stacks in c

c

stack