c中关于使用堆栈的括号平衡的程序不起作用

Question

我用c编写了这个程序，用堆栈的概念检查括号是否平衡。

#include<stdio.h>
#include<string.h>
#define MAX 100
int top = -1;
int arr[MAX];

void push(int x)
{
if (top == (MAX - 1))
{
printf("error:stack overflow n");
return;
}
top++;
arr[top] = x;
}
void pop()
{
top--;
}
int empty()
{

if (top == -1)
{
printf("The stack is empty n ");
return 1;
}
else{
return 0;
}
}
int main()
{
char str[30];int len;int i;int temp;
printf("Enter he expression n ");
scanf("%d",str);
len=strlen(str);
for(i=0;i<len;i++)
{
if (str[i] == '(' || str[i] == '{' || str[i] == '[')
{
push(str[i]);
}
if (str[i] == ')' || str[i] == '}' || str[i] == ']')
{
temp=empty();
if((empty())==1)
{
printf("Unbalancedn ");
return;
}
else if(str[i]==arr[top])
{
pop();
}
}
}
if((empty())==1)
{
printf("Balancedn");

}
else {
printf("unbalancedn");
}


return 0;
}

然而，无论我给出什么输入，我得到的结果都是

Enter he expression
{{{]])
empty happend
Balanced

我已经隔离了一个问题，即我的push和pop函数没有被调用，并且无论输入如何，堆栈都是空的。知道如何修复代码吗？

Answer 1

如果希望(, [, {不可区分，就不需要O(length)空间。一个O(1)计数器可以计算字符串位置当前有多少括号/大括号/方括号。你可以在存储arr队列时做更多的工作；也就是说，在大括号的类型中查找不匹配。我写了自己的快速括号检查器，发现：

我认为传递有效输入有4个异常条件。除了通过测试，我会确保为所有四个失败的测试设计一个测试，

• 堆栈溢出：对于固定大小的堆栈，嵌套级别太多
• 下溢：右大括号太多
• 不匹配：一种类型的支撑打开，但另一种类型关闭；这在原始代码中是完全缺失的
• 未关闭：堆栈中还有大括号，但输入已结束

人们可能想要自动化这个过程，但输入必须是抽象的。使用#include <assert.h>。

assert(check("([{}({}[])]())") != 0);
assert(check("(") == 0);
assert(check("]") == 0);
...
printf("Enter he expression n ");
if(!fgets(str, sizeof str, stdin)) return perror("input"), EXIT_FAILURE;
printf("%sn", check(str) ? "Balanced" : "unbalanced");

我使用了所期望的队列；每个角色的情况都不一样。我使用了一个switch语句，而不是一系列的ifs。我更改了pop()的原型，以返回前一个顶部元素，push()返回一个布尔值，表示它成功了(也就是说，不是堆栈溢出(

expect = 0;
switch(str[i]) {
case '':
if(!empty()) raise unclosed;
return;
case '(': expect = ')'; break;
case '[': expect = ']'; break;
case '{': expect = '}'; break;
case ')': case ']': case '}':
if(empty()) raise underflow;
if(pop() != str[i]) raise mismatch;
default: ; /* sic, everything else ignored */
}
if(expect && !push(expect)) raise overflow;

其中raise取决于所需的特异性。是否立即报告？对于#include <stdbool.h>、raise->return false；CCD_ 16->return true。如果希望更具体，可以返回一个异常值enum { okay, unclosed, underflow, mismatch, overflow }。或者使用goto获取有关上下文的更多信息。

Answer 2

有两个问题。

• 第一个是扫描应该是%s而不是%d
• 第二个是如果(str[i]==arr[Top](，它总是false，所以堆栈将保持满

下面的代码应该可以正常工作

#include <stdio.h>
#include <string.h>
#define MAX 100
int top = -1;
int arr[MAX];
void push(int x)
{
if (top == (MAX - 1))
{
printf("error:stack overflow n");
return;
}
top++;
arr[top] = x;
}
void pop()
{
top--;
}
int empty()
{
if (top == -1)
{
printf("The stack is empty n ");
return 1;
}
return 0;   
}
int main()
{
char str[30];
int len;
int i;
int temp;
printf("Enter he expression n ");
scanf("%s", str);
len = strlen(str);
for (i = 0; i < len; i++)
{
if (str[i] == '(' || str[i] == '{' || str[i] == '[')
{
push(str[i]);
continue;
}
if (str[i] == ')' || str[i] == '}' || str[i] == ']')
{
if (empty())
{
printf("Unbalancedddn ");
return;
}
pop();
}
}
if (empty())
{
printf("Balancedn");
}
else
{
printf("unbalancedn");
}
return 0;
}

编辑：

上面的代码只是修复堆栈的错误。下面的一个将检查三对中的每一对。

#include <stdio.h>
#include <string.h>
#define STACK_MAX 100
int stack[STACK_MAX];
int top = -1;
void push(int x);
int pop();
int peek();
int isEmpty();
int main()
{
char str[STACK_MAX * 2];
printf("Enter he expression n ");
scanf("%s", str);
int len = strlen(str);
for (int i = 0; i < len; i++)
{
if (str[i] == '(' || str[i] == '{' || str[i] == '[')
{
push(str[i]);
continue;
}
if (str[i] == ')' || str[i] == '}' || str[i] == ']')
{
if (isEmpty())
{
printf("unbalancedn");
return 0;
}
const char left = peek();
const char peek[3];
sprintf(peek, "%c%c", left, str[i]);
if (!(strcmp(peek, "()") == 0 || strcmp(peek, "[]") == 0 || strcmp(peek, "{}") == 0))
break;
pop();
}
}
if (isEmpty())
{
printf("Balancedn");
}
else
{
printf("unbalancedn");
}
return 0;
}
// --------------------------------------
// Stack Implementation
// --------------------------------------
void push(int x)
{
if (top + 1 == STACK_MAX)
{
printf("error:stack overflow n");
return;
}
stack[++top] = x;
}
int pop()
{
if (top == -1)
{
printf("error: stack is empty n");
return -1;
}
return stack[top--];
}
int peek()
{
if (top == -1)
{
printf("error: stack is emptyn");
return -1;
}
return stack[top];
}
int isEmpty()
{
return top == -1;
}

Answer 3

一个有趣的项目！

从堆栈中推送/弹出值的函数调用的另一种选择是使用变量的32(或64(位来跟踪3对不同的括号/方括号。。。

2个比特可以表示4个值。0b00没有用处，因为它不能与null(数据(区分，但0b01，0b10&0b11可以用来表示三对感兴趣的每一对。

在下面的代码中，unsigned int是堆栈将两个位推到堆栈上涉及左移位和"或">Popping首先测试堆栈的两个LSB与字符流作为右括号的内容，然后对堆栈进行右移。

在我的32位编译器上，这被限制为16个并发嵌套级别，但在64位编译器上可以达到32个级别。实际上，这应该适用于大多数情况。

该代码确实检测/防止堆栈溢出/溢出，并在检测到时退出。

#include <stdio.h>
#include <limits.h> // to determine 32 bit v. 64 bit
#if UINT_MAX = 0xffffffff // not sure this is right...???
typedef uint32_t stk_t;
#define FULL 0xC0000000 // b31 & b30 set
#else
typedef uint64_t stk_t;
#define FULL 0xC000000000000000 // b63 & b62 set
#endif
int balChk( char *str ) {
stk_t stk = 0;
char *sel = "(){}[]";
int ret = 0;
for( char *cp = str; !ret && *cp; cp++ ) {
for( char *bp = sel; *bp && *bp != *cp; bp++ ) {} // loop
if( !*bp ) continue; // not interesting character
if( (bp-sel)%2 == 0 ) { // 0,2,4 means push
if( stk & FULL ) {
printf( "Stack full - " );
ret = -1;
}
// pushes encoded matching close ')', '}' or ']'
stk = stk<<2 | ((bp-sel)+2)>>1; // use [2,4,6]/2 = 1,2,3
}
else // 1,3,5 means pop
{
// have stk item AND two LSBs match ([1,3,5]+1)/2 = 1,2,3
// compare encoded close with "top of stack" (ie: 2 LSBs )
if( !stk || (stk&3) != (bp-sel+1)>>1 ) {
printf( !stk ? "Stack empty - " : "Unmatched '%c' - ", *cp );
ret = -1;
}
stk >>= 2;
}
}
return ret + stk; // 0 means good
}
int main() { // test a few variations
char *strs[] = {
"()", "{}", "[]", "((()))", "(([()]))",
"(((([ (((([ (((([", // 15
"(((([ (((([ (((([ [", // 16
"(((([ (((([ (((([ [{", // 17 too many for my 32bit compiler
"(((([ (((([ (((([ []{", // 16-1+1
"{ ({()}) ((())) []        }",
"{ ({()}) ((())) [] missing!",
"{ ({()}) ((())) []          }",
"{ ({()}) ((())) [] too many }}",
};
for( int i = 0; i < sizeof strs/sizeof strs[0]; i++ )
printf( "'%s' - %sn", strs[i], balChk( strs[i] ) ? "Bad" : "Good" );
return 0;
}

输出

'()' - Good
'{}' - Good
'[]' - Good
'((()))' - Good
'(([()]))' - Good
'(((([ (((([ (((([' - Bad // but 15 passed
'(((([ (((([ (((([ [' - Bad // but 16 passed
Stack full - '(((([ (((([ (((([ [{' - Bad // 17 popped the stack
'(((([ (((([ (((([ []{' - Bad // 16 - 1 + 1 passed
'{ ({()}) ((())) []        }' - Good
'{ ({()}) ((())) [] missing!' - Bad
'{ ({()}) ((())) []          }' - Good
Stack empty - '{ ({()}) ((())) [] too many }}' - Bad // Excessive popping

总而言之，这是一个有趣的项目。。。