我正试图编写一个程序，在该程序中，我用数组实现堆栈，并使用它们来检查给定字符串是否有平衡的括号。
例如，如果输入"((((｛｝[((]"，程序将输出"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,errorn");
}else{
top++;
stack[top]=val;
}
}
char pop(){
if(top==-1){
printf("not enough elements,errorn");
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]!=' '){
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
}
}
这是用户输入字符串并测试其是否"平衡"的主要功能。
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("Balancedn");
}
else{
printf("Not balancedn");
}
return 0;
}
当我输入一个非常简单的例子时，我得到了一个错误的答案，例如
Enter the string with the brackets and etc.
()
Not balanced
这应该改为输出"Balanced"。我不明白这是怎么发生的。
在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
}
进行这些更改后，您的代码似乎可以在我的盒子上工作。这不是我对它的编码方式，但这是使它工作的最小更改集。
if (stack==NULL)是这里的问题，堆栈永远不会为NULL。您需要通过验证top > 0来检查堆栈中是否仍有元素
您错误地实现了推/弹出组合。如果按下一个字符，则top变为0。如果您立即弹出它，它最终会执行top--; return stack[top]，计算结果为stack[-1]。
试试这个推/弹出：
int top=-1; //idx to be popped next; <0 -> invalid
void push(char val)
{
if(top==MAX-2)
printf("stack is already full,errorn");
else
stack[++top]=val;
}
char pop()
{
if(top<0) return ' '; //no abort, just return invalid char
return stack[top--];
}
您的问题的答案已经得到了令人满意的回答，但作为一种不同方法的建议，请考虑以下内容。
由于在C源代码中使用的通用外壳数量非常少，您可以使用递增-递减计数器轻松地跟踪它们的对。下面使用一个结构typedefed到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;
}