C++:使用堆栈验证括号是否平衡(逻辑错误)

Question

我有一个用基本的初始化、显示、推送、弹出、顶部等函数创建的简单堆栈。我需要一个函数来验证字符串是否具有匹配的括号。我想我已经很接近了，但是我有以下问题:if (s.size == 0 && c == ')') 在我的平衡函数中间。 p>

这个条件应该由字符串 "s1"和除号之前的括号满足，但它不是......它仍然返回 true。

感谢您的关注。

#include <iostream>
#include <string>
#include <stdlib.h>

using namespace std;

struct Stack{
    static const unsigned MAX_SIZE = 5;
    char data[ MAX_SIZE ];
    unsigned size;
};

void initialize( Stack & stack );
void show( const Stack & stack );
unsigned getSize( const Stack & stack );
void push( Stack & stack, char c );
char pop( Stack & stack );
char top( const Stack & stack );
bool die( const string & msg );
bool balanced (const string & expr);

int main(){

    string s1 = "X*((4+(3-2)/(Y+X))+(Z-8))) / ((A+(B-2))";
    string s2 = "())";
    string s3 = "(()";

    cout << balanced(s1) << endl;
    cout << balanced(s2) << endl;
    cout << balanced(s3) << endl;

}

void initialize( Stack & stack ){
    stack.size = 0;
}

void show( const Stack & stack ){
    cout <<"[" << stack.size <<"]:";
    for(  unsigned i = 0;  i < stack.size;  i++  )
        cout <<stack.data[i];
    cout <<endl;
} // show

unsigned getSize( const Stack & stack ) {return stack.size;}

void push( Stack & stack, char c ){
    if( stack.size == Stack::MAX_SIZE )  die( "push: overflow" );
    stack.data[stack.size++] = c;
} // push

char pop( Stack & stack ){
    if( stack.size == 0 )  die( "pop: underflow" );
    return stack.data[--stack.size];
} // pop

char top( const Stack & stack ){
    if( stack.size == 0 )  die( "top: underflow" );
    return stack.data[stack.size-1];
} // top

bool die( const string & msg ){
    cerr <<endl <<"Fatal error: " << msg <<endl;
    exit( EXIT_FAILURE );
}

bool balanced (const string & expr){

    Stack s;
    initialize(s);

    for (unsigned i = 0; i < expr.size(); i++){
        char c = expr[i];

        if (c == '(')
        {
            if( expr.size() == Stack::MAX_SIZE )  {
                die( "push: overflow" );
            }

            push(s, c);

        }

        if (s.size == 0 && c == ')')
        {
            return false;
        }
        else if (c == ')'){
            pop(s);
        }

        if (s.size == 0){

            return true;
        }

        else

        return false;
    }
}

Answer 1

虽然您的问题的评论中似乎已经提供了您需要的答案(不错，dlev)，但我想建议一种可能更快的替代方法。

bool balanced(const string& expression)
{
    int count = 0;
    for (int i = 0; i < expression.size(); ++i)
    {
        if (expression[i] == '(') ++count;
        else if (expression[i] == ')') --count;
        if (count < 0) return false;
    }
    return count == 0;
}

这有效地丢弃了栈结构，只保留它的大小。如果它低于 0，则意味着找到了不匹配的右括号，如果循环在未达到 0 的情况下终止，则有 count。不匹配的左括号。

还应注意，仅检查 count < 0 是不够的循环结束后，因为像 ")(" 这样的事情会通过测试。