在c中使用stack检查表达式的平衡括号

Question

堆栈的应用

最近我们遇到了一个问题，在这个问题中，一个表达式带有一些括号，我们被告知要检查这个表达式是否平衡。

这是我到目前为止所做的，但我似乎无法从堆栈中弹出元素。当我把它放在函数的其他部分时，我似乎可以正确地比较它。

我如何使我的代码工作，是什么原因导致简单的比较条件不起作用？

#include <stdio.h>
#include <stdbool.h>
char stack[30];
int top = 0;
bool spec = 0;
void push(char x){
if (top == 30)
printf("Fulln");
else{
stack[top] = x;
top++;
}
}
void pop(char x){
if (top == 0)
spec = 1;
else{
if (x == stack[top-1])
top--;
}
}
int main()
{
char temp[30];
scanf("%s", temp);
for (int i = 0; temp[i] != ''; i++)
{
if (temp[i] == '(' || temp[i] == '{' || temp[i] == '[')
push(temp[i]);
else if (temp[i] == ')' || temp[i] == '}' || temp[i] == ']')
pop(temp[i]);
}
for (int i = 0; i < top; i++){
printf("%c", stack[i]);
}
if (top != 0)
printf("Unbalanced");
else
printf("Balanced");
return 0;
}

Answer 1

当您读取右括号或大括号时，您不仅应该弹出堆栈，还应该比较弹出的值，看看它是对应的左括号还是大括号。

因此，您首先需要修改pop函数以返回弹出值：

char pop(void)
{
if (top > 0)
{
return stack[--top];
}
else
{
return 0;  // Error: Stack underflow
}
}

然后你需要得到弹出的字符并检查它：

if (temp[i] == '(' || temp[i] == '{' || temp[i] == '[')
{
push(temp[i]);
}
else if (temp[i] == ')' || temp[i] == '}' || temp[i] == ']')
{
char opening = pop();  // Pop and get value
if ((temp[i] == ')' && opening != '(') ||
(temp[i] == '}' && opening != '{') ||
(temp[i] == ']' && opening != '['))
{
// TODO: Not matching, handle it in some appropriate way
}
}

Answer 2

一旦开始，就很难停止这些事情。意图"；轻轻触摸"；你的代码，这就是结果。我希望这些评论能说明它在做什么。。。主要是对于3种类型的"；打开"；，这个"；"推"；它的配偶在堆栈上。然后当一个"；关闭"；如果遇到，则将其传递给popExpect()，以便根据堆栈顶部的内容进行验证(如果有的话(。该函数返回布尔值yes/no以继续。

不管怎样。。。

#include <stdio.h>
#define STACKSIZE 30 // One "magic number" in this source
char stack[ STACKSIZE ]; // Global, but let's go with it
int top = 0;
void push( char x ) { // little change here
if( top == STACKSIZE )
puts( "Stack Full");
else
stack[ top++ ] = x;
}
bool popExpect( char c ) { // compare expected char on top with passed char
return top && c == stack[ --top ];
}
// function "broken out" for repeated tests
bool chk( const char *str ) {
char *cp, pairs[] = "(){}[]"; // three important pairs
bool isGood = true; // optimism
// while good and not finished string
for( int i = 0; isGood && str[ i ]; i++ )
// is this char one of the "special" ones?
if( ( cp = strchr( pairs, str[ i ] ) ) != NULL ) {
// which "special" char is it?
int off = cp - pairs;
// because "paired" 0,2,4 are open, 1,3,5 are close
if( off%2 == 0 ) // opening
push( cp[1] ); // push the close that matches this open
else // special closing
isGood = popExpect( str[ i ] ); // does this close match?
}
// all good and nothing left on the stack
return isGood && top == 0;
}
int main() {
const char *s1 = "(foobar)({}){bar}[[[(foo)]]]"; // balanced
const char *s2 = "(foobar)({}){ { bar}[[[(foo)]]]"; // unbalanced open
const char *s3 = "(foobar)({}){ ] bar}[[[(foo)]]]"; // unbalanced close
puts( chk( s1 ) ? "Balanced" : "Unbalanced" );
puts( chk( s2 ) ? "Balanced" : "Unbalanced" );
puts( chk( s3 ) ? "Balanced" : "Unbalanced" );
return 0;
}