Having trouble with stack implementation

Question

Full disclosure: this is for an assignment. I'm not looking for explicit answers, but a little guidance.

I'm having a hard time initializing my stack in C. Specifically, I can't seem to get it to properly push new elements onto the stack. I know my push/pop/etc functions are correct (they were provided) but I fear that I'm not looking at this correctly.

This is a basic attempt at reading a string and determining if it is "balanced" (all parentheses, curly and square brackets have partners and appear in the correct order.) As far as I can tell, it isn't a problem with my logic and I believe the syntax is correct, so I'm kind of at a loss for ideas...

Here's my attempt at the implementation:

int isBalanced(char* s) {

struct DynArr *string;
string = newDynArr(50);

while (nextChar(s) != '\0') {
    if ((nextChar(s) == '(') || (nextChar(s) == '{') || (nextChar(s) == '[')) {
        pushDynArr(string, nextChar(s));
    }
    if (nextChar(s) == ')') {
        if (topDynArr(string) != '(') {
            return 0;
        } else popDynArr(string);
    }
    if (nextChar(s) == '}') {
        if (topDynArr(string) != '{') {
            return 0;
        } else popDynArr(string);
    }
    if (nextChar(s) == ']') {
        if (topDynArr(string) != '[') {
            return 0;
        } else popDynArr(string);
    }
}

if (isEmptyDynArr(string)) {
    printf("The stack is empty\n");
    return 1;
} else return 0;
}

The output always prints "The stack is empty" and returns true, despite me giving it unbalanced strings. I've probably been looking at this for too long and can't recognize the obvious. I'd appreciate any help you can lend. I don't need explicit answers, but a push in the right direction would be enough.

Edit: Here are the functions that have been requested...

int isEmptyDynArr(DynArr *v) 
{
    if(v->size == 0) {
        return 1;
    }
    else return 0;
}

DynArr* newDynArr(int cap)
{
    assert(cap > 0);
    DynArr *r = (DynArr *)malloc(sizeof( DynArr));
    assert(r != 0);
    initDynArr(r,cap);
    return r;
}

void pushDynArr(DynArr *v, TYPE val)
{
    assert(v != 0);
    addDynArr(v, val);
}

void popDynArr(DynArr *v)
{
    assert(v != 0);
    assert(isEmptyDynArr(v) == 0);
    v->size--;
}

TYPE topDynArr(DynArr *v)
{
    assert(v != 0);
    assert(isEmptyDynArr(v) == 0);
    return v->data[v->size - 1];
}

char nextChar(char* s)
{
    static int i = -1;
    char c;
    ++i;
    c = *(s+i);
    if ( c == '\0' )
        return '\0';
    else
        return c;
}

Just a friendly tip: Don't have variables with the same name as reserved words/standard classes in C++. It works since this isn't C++, but it will be easier to port to C++, or to to compile with a C++ compiler (seen it done because of the stricter type rules). — Some programmer dude
– Some programmer dude, Commented Nov 27, 2012 at 9:06
What does nextChar do? I'm asking because you don't seem to be incrementing the s pointer anywhere. If you do that with nextChar - which is impossible in C, unless you use some kind of global counter, but not in C++ - you're gonna run into troubles because you call nextChar multiple times in a row before determining the character. If not, you need to increment it after each iteration. — Cubic
– Cubic, Commented Nov 27, 2012 at 9:09
Can you please show the DynArr structure? And the nextChar and the pushDynArr/popDynArr/topDynArr/isEmptyDynArr functions? — Some programmer dude
– Some programmer dude, Commented Nov 27, 2012 at 9:10

lenik · Accepted Answer · 2012-11-27 09:13:45Z

2

this line may skip 1 or 2 or 3 characters from the input line:

nextChar(s) == '(') || (nextChar(s) == '{') || (nextChar(s) == '['

you should most definitely use:

char ch = nextChar(s);
if( ch == '(' || ch == '{' || c == '[' )

answered Nov 27, 2012 at 9:13

lenik

23.6k4 gold badges38 silver badges44 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

unwind Over a year ago

Another way of putting this is that nextChar() is not idempotent: each call will move its idea of where in the string it's reading from.

idigyourpast Over a year ago

@lenik Thank you, that was the problem. I think I was too tired to realize that each successive call to nextChar() was incrementing through the stack before any operation could be performed on it. Adding char ch = nextChar(s) allowed one element to be used throughout each pass in the while loop, and the rest works great. Thank you again.

Cubic · Accepted Answer · 2012-11-27 09:45:43Z

You don't seem to be incrementing s anywhere. What does your nextChar function do? I can only guess, but it seems like it'll just return *s. If that's the case, you need to increment s (++s) after each iteration. If it does magically (because there really isn't a sensible way to do that in plain C) increment s anyways, you should only call it once per iteration and save the result. I'd guess it's the former, in which case for example for this string: "(())" you will read the first '(' twice and return 0.

Update: Yeah, apparently your nextChar function does use a global counter. Advice two applies, only call it once per iteration. Or better yet, get rid of that thing. The way that function is designed, you can effectively use it exactly once in the entire lifetime of your program, and the entire functionality of that thing can be replaced by (*s ? *(s++) : *s). Or just *(s++) (and just do the check for 0 yourself).

Collectives™ on Stack Overflow

Having trouble with stack implementation

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related