c - 在 C 中使用堆栈数据类型平衡括号

Question

我有这个堆栈数据结构，其中我将数据存储在一个数组中。堆栈在结构堆栈中定义，类型定义为 Stack。因此，我正在使用此堆栈数据类型来检查给定字符串中的括号是否平衡。

我正在使用 get line 函数读取值。但不知何故，如果我将读取字符串的总长度输入函数 isBalanced(buffer,strlen(buffer))，我会得到正确的答案，但输出错误。我得到这个作为输出: 堆栈下溢:堆栈中没有元素 表情平衡

第一行不应该在那里，因为在 isBalanced 函数中，我已经放置了很多检查。即使它设法通过了这个条件匹配(peek(s),exp[i])，虽然它不应该通过，但它仍然必须通过 if (isEmpty(s)) return 0;这个测试条件，应该确保程序退出并且不会给出堆栈下溢消息， 这是我的代码，请帮助我在较早的实现中找到问题所在。虽然我现在有了正确的答案，但通过传递比 get line 函数读取的字符总数少一个。我猜 '\0' 是问题所在，但我不确定为什么这种行为如此奇怪:

// This is the stack data struct definition
typedef struct stack{
    int top; //keeps track of top most element in the stack
    int capacity; //keeps track of number of elements that could be stored
                  // in the stack
    int *array;
} Stack;



// This is the stackInterface.h file
#include "stack.h"

//To create a stack
Stack *createStack(int);

//Queries about the status of stack
int isEmpty(Stack *);
int isFull(Stack *);

//Methods to update stack
void push(Stack *, int);
int pop(Stack *);

//Method to look at the top element of the stack
int peek(Stack *);



// This is the linking file to the main executable file
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include "stack.h"

Stack *createStack(int capacity){
    Stack *s = malloc(sizeof *s); //new stack is created
    s->top = -1; // initially top position is empty and hence initialised
                // to -1.
    s->capacity = capacity;
    s->array = malloc(sizeof int*capacity);
    // an array with required capacity is created
    return s;  // pointer to newly created stack is returned

}

int isFull(Stack *s){
    return s->top == s->capacity - 1;
    //A short-hand of way of writing that if the top is equal to the
    //number of elements in the stack return 1.

}

int isEmpty(Stack *s){
    return s->top == -1;
    //top value being -1 signifies that there are no elements in the stack
}

void push(Stack *s, int value){
    if (!isFull(s))
            s->array[++s->top] = value;
       //Incrementing the top position and placing the value at that position
    else
            printf("Stack overflow : the stack is at capacity \n");
}

int pop(Stack *s){
    if (!isEmpty(s))
            return s->array[s->top--];
    //returning the value at top position and decrementing the top position
    printf("Stack underflow: there are no elements in the stack\n");
    return INT_MIN; // some sentinel value is returned to signify failure
}

int peek(Stack *s){
    if (!isEmpty(s))
            return s->array[s->top];  
    printf("Stack underflow : there are no elements in the stack\n");
    return INT_MIN;   // some sentinel value is returned to signify failure
}


// This is the main file
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stackInterface.h"

int matching(char ch1, char ch2){
  return (ch1=='{'&&ch2=='}')||(ch1=='['&&ch2==']')||(ch1=='('&&ch2==')');
    // both ch1 and ch2 should be of matching types

}

int isBalanced(char exp[], int size){
    int i = 0;
    Stack *s = createStack(size);
    while (i < size){
            if (exp[i] == '{' || exp[i] == '[' || exp[i] == '('){
                    push(s, exp[i]);
            }
            else{
                    if (matching(peek(s),exp[i])){
                            if (isEmpty(s)) return 0;
                            pop(s);
                    }
            }
            i++;
    }
    return isEmpty(s);
}

int main(){
    size_t buf_size = 32;
    ssize_t characters;
    char *buffer = NULL;
    characters = getline(&buffer, &buf_size, stdin);
    puts(buffer);


    if (isBalanced(buffer,strlen(buffer)-1))
            printf("The expression is balanced \n");
    else
            printf("The expression is not balanced \n");
    return 0;
}

如果我删除 -1 形式的 isBalanced 函数，我得到的输出根本不应该存在: “堆栈下溢:堆栈中没有元素”作为第一行。又“神情平衡”为下联。第二行没问题，但是查看代码，可以看到第一行不应该存在，因为那里有很多检查。

Answer 1

getline() 在缓冲区中包含换行符 (\n)，它不匹配任何内容。此时堆栈为空，因此出现下溢错误，但由于堆栈为空，isBalanced() 仍会返回 true。通过传递 strlen(buffer) - 1，您将省略换行符，这就是为什么事情似乎有效的原因。

此外，在调用 getline() 之前，您需要将 buffer 和 buf_size 初始化为零。