Pop 在特定函数中只工作一次

Question

我将堆栈实现为链表，我想制作一个函数来判断括号是否井然有序，例如：(()) 好 ())( 不好。函数逻辑现在不好但我不知道为什么 pop() 只工作 once.Here 是我的代码（stog 是堆栈，下一个是 sljedeci）：

struct stog {
    int x;
    stog *sljedeci;
};

typedef struct stog stog;

stog *top;
char pop() {
    stog *temp;
    temp = (stog*)malloc(sizeof(stog));
    temp = top;
    char n = temp->x;
    top = temp->sljedeci;
    top->x = temp->sljedeci->x;
    free(temp);
    return n;
}



void init() {
    top = NULL;
}

void push(char x) {
        stog *temp;
        temp=(stog*)malloc(sizeof(stog));
        temp->x = x;
        temp->sljedeci = top;
        top = temp;
    }

 void Brackets(const char* msg) {
    char z;
    for (int i = 0; i < strlen(msg); i++) {
        if (msg[i] == '(') {
            push('(');
        }
        if (msg[i]==')'){
            z = pop();
            printf("Bad\n");    
        }       
    }
}

int main() {

    const char* msg = "(())";
    init(); 
    Brackets(msg);
    return 0;
}

输出为：

不好

应该是：

不好不好

编辑：添加了 init() 和 push() 函数

Answer 1

我们初学者应该互相帮助。:)

我有生以来第一次做你的作业。:)

首先，始终使用英文单词作为标识符。否则程序文本可能无法读取。

不清楚为什么数据成员 x 的类型是 int 而不是 char，尽管堆栈处理字符串的字符。

struct stog {
    int x;
    stog *sljedeci;
};

尽管如此，您并未显示所有堆栈实现，例如函数 pop 无效。它会产生内存泄漏。

首先你分配了内存并将它的地址分配给了指针 temp 并且在下一行你立即重新分配了指针。所以分配的内存不会被释放。

temp = (stog*)malloc(sizeof(stog));
temp = top;

此声明

top->x = temp->sljedeci->x;

如果 top 等于 NULL，则可以调用未定义的行为。

同样在函数Brackets这个if语句

    if (msg[i]==')'){
        z = pop();
        printf("Bad\n");    
    }

没有意义。一旦遇到字符 ')'，该函数将始终输出 "Bad"。

这是我做过的解决方案。

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

struct stack
{
    char c;
    struct stack *next;
};

char * top( struct stack **stack )
{
    return *stack == NULL ? NULL : &( *stack )->c;
}

int push( struct stack **stack, char c )
{
    struct stack *current = malloc( sizeof( struct stack ) );
    int success = current != NULL;

    if ( success )
    {
        current->c = c;
        current->next = *stack;

        *stack = current;
    }

    return success;
}

void pop( struct stack **stack )
{
    if ( *stack )
    {
        struct stack *current = *stack;
        *stack = ( *stack )->next;

        free( current );
    }
}

int empty( struct stack **stack )
{
    return *stack == NULL;
}

void clear( struct stack **stack )
{
    while ( *stack ) pop( stack );
}

int bracket_balance( const char *s )
{
    struct stack *stack = NULL;

    int balanced = 1;

    for ( ; *s && balanced; ++s )
    {
        if ( *s == '(' )
        {
            push( &stack, *s );
        }
        else if ( *s == ')' )
        {
            if ( ( balanced = !empty( &stack ) && *top( &stack ) == '(' ) )
            {
                pop( &stack );
            }
        }
    }

    balanced = balanced && empty( &stack );

    clear( &stack );

    return balanced;
}

int main(void) 
{
    const char * s[] = 
    {
        "", "(", ")", "()", ")(", "( ( ) )", "( )( )", "( ) ) (", "Hello"
    };

    for ( size_t i = 0; i < sizeof( s ) / sizeof( *s ); i++ )
    {
        if ( bracket_balance( s[i] ) )
        {
            printf( "\"%s\" has balanced brackets\n", s[i] );
        }
        else
        {
            printf( "\"%s\" does not have balanced brackets\n", s[i] );
        }
    }       

    return 0;
}

程序输出为

"" has balanced brackets
"(" does not have balanced brackets
")" does not have balanced brackets
"()" has balanced brackets
")(" does not have balanced brackets
"( ( ) )" has balanced brackets
"( )( )" has balanced brackets
"( ) ) (" does not have balanced brackets
"Hello" has balanced brackets

Answer 2

pop 中的这一行没有意义：

top->x = temp->sljedeci->x;

在前一行中，您将 temp->sljedeci 分配给 top。所以这里引用的 x 成员实际上在两边都是同一个成员，所以假设 top 和 temp->sljedeci 都不为 null 它什么都不做。如果其中一个为 NULL，则调用 undefined behavior 因为取消了对空指针的引用。所以去掉这一行。

您在 pop 中也有内存泄漏：

temp = (stog*)malloc(sizeof(stog));
temp = top;

您分配内存并将其地址分配给 temp，但您立即用 top 的值覆盖该地址。

此处不需要分配更多内存，因此删除 malloc 调用。

Pop 在特定函数中只工作一次

Pop works only once in specific function

c

stack

memory-management

c-strings

singly-linked-list