c - 平衡的表达

Question

下面是确定符号平衡的代码。

如果表达式是平衡的，那么它应该打印适当的消息。例如:

((A+B))+(C+D)) --> Balanced

((A+B)+(C+D) ---> Unbalanced

((A+B)+(C+D}) --> Unbalanced

这是代码

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

struct Stack {
    char data;
    struct Stack *next;
};

void push(struct Stack **top, char data) {
    struct Stack *new_node;
    if (*top == NULL) {
        new_node = malloc(sizeof(struct Stack));
        new_node->data = data;
        new_node->next = *top;
        *top = new_node;
    } else {
        new_node = malloc(sizeof(struct Stack));
        new_node->data = data;
        new_node->next = *top;
        *top = new_node;
    }
}

char pop(struct Stack **top, int flag) {
    if (*top != NULL && flag == 0) {
        printf("\n Expression is In-Valid  :) \n");
        return '\0';
    }
    if (*top == NULL && flag == 1) {
        printf("\n Unbalanced Expression \n");
        return '\0';
    }
    if (*top != NULL && flag == 1) {
        struct Stack *temp = *top;
        char op;
        op = (*top)->data;
        *top = (*top)->next;
        free(temp);
        return op;
    }
}

/*
void display(struct Stack *top) {
    struct Stack *temp = top;
    while (temp) {
        printf("\n %c", temp->data);
        temp = temp->next;
    }
}
*/

int main(void) {
    struct Stack *top = NULL;
    int i = 0;
    char str[] = "((A+B)+[C+D])", op;
    printf("\n Running the programe to check if the string is balanced or not ");
    for (i = 0; str[i] != '\0'; ++i) {
        if (str[i] == '(' || str[i] == '[' || str[i] == '{' || str[i] == '<')
            push(&top, str[i]);
        else
        if (str[i] == ')' || str[i] == ']' || str[i] == '}' || str[i] == '>') {
            op = pop(&top, 1);
            if ((op == '(' && str[i] == ')') || 
                (op == '[' && str[i] == ']') ||
                (op == '{' && str[i] == '}') ||
                (op == '<' && str[i] == '>')) {
                continue;
            } else {
                printf("\n The expression is un-balanced \n");
                break;
            }
        }
    }
    pop(&top, 0);
    return 0;
}

但它没有给出所需的输出。我调试了代码，但没有找到问题所在。

如何让它打印适当的消息？

Answer 1

一旦检测到不平衡的情况，您应该立即清理堆栈并停止处理，并在到达 return 0 时打印“Balanced”。并且您应该从代码中的一个位置打印“Unbalanced”。

不幸的是，pop 的一个分支在声明返回值时没有返回值。

因此，pop 可能会变成:

char pop(struct Stack **top,int flag)
{
        if(*top!=NULL && flag==0)
        {
                return '\0';
        }
        if(*top==NULL && flag ==1)
        {
                return '\0';
        }
        if(*top!=NULL && flag==1)
        {
                struct Stack *temp=*top;
                char op;
                op=(*top)->data;
                *top=(*top)->next;
                free(temp);
                return op;
        }
        // *top == null && flag == 0
        return 'O'; // for OK
}

我会添加一个 clean 方法 - 不需要，因为程序退出会清理堆栈，但我更喜欢这样做:

void clean(struct Stack *top) {
    struct Stack *next;
    while (top != NULL) {
        next = top->next;
        free(top);
        top = next;
    }
}

主要内容有一些变化:

int main(void)
{
        struct Stack *top=NULL;
        int i=0, err=0;
        ...
                        else
                        {
                                err = 1;
                                break;
                        }

                }
        }
        if (err || (pop(&top,0) == '\0')) {
            printf("\n The expression is un-balanced \n");
            clean(top);
            // return 1; optionally if you want to return a different value to environment
        }
        else {
            printf("\n The expression is balanced \n");
        }
        return 0;
}