CODEWITHSUNDEEP
c++structstack
user2411290
user2411290

Reputation: 641

C++: Using a Stack to Verify if Parentheses are Balanced (Logic error)

I have a simple stack I created with basic initialize, show, push, pop, top, etc. functions. I need a function to verify whether or not a string has matching parentheses. I think I'm pretty close, but I have a problem with the following: if (s.size == 0 && c == ')') in the middle of my balanced function.

This condition should be met by string "s1" with the parenthesis just prior to the division sign, but it is not...It is still returning true.

Thanks for looking.

#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;
    }
}

Upvotes: 0

Views: 3534

Answers (1)

More Axes
More Axes

Reputation: 369

While the answer you needed seems to have been provided in the comments of your question (nice catch, dlev), I'd like to suggest an alternative approach, which is probably faster.

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;
}

This effectively throws away the stack structure, keeping only its size. Should it ever go below 0, it means an unmatched right parenthesis was found, and if the loop terminates without reaching 0, then there are count unmatched left parentheses.

It should also be noted that it would not suffice to check for count < 0 after the loop has finished, since things like ")(" would pass the test.

Upvotes: 1

Related Questions