balanced paranthesis

[Azhagu]

in data structure, how the paranthesis balanced are checked with stack.little confusion in it.

[rubberman]

Please show example of what you are having problems with.

[Hiroshe]

So you know that each left paren needs to have a matching right paren. You also know that order is important.

If you see { ( then you would expect to see ) } eventually in that order. That is to say, the last left paren we see needs to match the next right paren. That's what a stack is (the first one in is the last one to be matched "first in last out" or FILO for short).

So for the expression

hello{(world),(whats)}[new]
0           1 2     345   6

When we have read position from 0 to 1, out stack looks like: {(. Once we read ) it looks like {.

Then at position 2, it looks like {(.

At position 3, after ) is read, it looks like { again.

At position 4 the stack is empty, but we still have more input.

At 5 it looks like [ and finally at 6 it is empty again. Since it is empty and we have no more input, we're done.

[bhavna123]

Balanced parenthesis means every opening parenthesis has its corresponding closing parenthesis. And the order is from inner to outer for closing.

For example, if you have some parenthesis in this order {a*(b+C then closing parenthesis will be ) then } that is the expression will be: {a*(b+c)}

[ITTechnos]

Check this Code:

#include <iostream>
#include <stack>
#include <string>
#include <cstring>
#include <cstdio>

using namespace std;

stack <char> Stk;

int main()
{
    char str[100],temp;
    gets(str);
    int len = strlen(str);
    for(int i=0;i<len;i++)
    {
        if(str[i]=='(' || str[i]=='{' || str[i]=='[')
            Stk.push(str[i]);
        else
        {
            temp = Stk.top();
            if(temp=='(' && str[i]==')' || temp=='[' && str[i]==']' || temp=='{' && str[i]=='}')
                Stk.pop();
            else
                break;
        }
    }
    if(Stk.empty())
        cout << "Balanced Parenthesis" << endl;
    else
        cout << "Not balanced parenthesis" << endl;
    return 0;
}

Sample I/O to check Parentheses balance:

Check those I/O:

Input:

([])
(([()])))
([()])()

Output:

Balanced Parenthesis
Not balanced parenthesis
Balanced Parenthesis

Hope this will help :)

Check this code

-1 for posting c++ code in the 'c' forum.
-100 for using gets() as it is unsafe.
-10 for not being able to ignore other string variables.

[Gonbe]

#include <assert.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

/******** Stack *********/

const unsigned STACK_INTIAL_ALLOC_SZ = 8;

typedef struct {
        void*    elems;     /* The elements that are stored in the stack.             */
        unsigned elem_sz;   /* The size in bytes of the elements stored in the stack. */
        unsigned size;      /* The amount of elements stored in the stack.            */
        unsigned capacity;  /* The capacity of the stack.                             */
} Stack;

void stack_create (Stack* const s, const unsigned elem_size);
void stack_delete (const Stack* const s);
bool stack_empty  (const Stack* const s);
void stack_push   (Stack* const s, const void* const elem_addr);
void stack_pop    (Stack* const s, void* const elem_addr);

void stack_create (Stack* const s, const unsigned elem_size)
{
    assert(elem_size > 0);

    s->elems     = malloc(STACK_INTIAL_ALLOC_SZ * elem_size);
    s->elem_sz   = elem_size;
    s->size      = 0;
    s->capacity  = STACK_INTIAL_ALLOC_SZ;

    assert(s->elems != NULL);
}

void stack_delete (const Stack* const s)
{
    free(s->elems);
}

bool stack_empty (const Stack* const s)
{
    return (s->size == 0);
}

void stack_push (Stack* const s, const void* const elem_addr)
{
    void* dest_addr = NULL;

    /* Double the size once the stack's capacity is reached. */
    if (s->size >= s->capacity)
    {
        s->capacity *= 2;
        s->elems     = realloc(s->elems, s->capacity * s->elem_sz);

        assert(s->elems != NULL);
    }

    /* Store the element */
    dest_addr = (char*) s->elems + s->size * s->elem_sz;
    memcpy (dest_addr, elem_addr, s->elem_sz);
    s->size++;
}

void stack_pop (Stack* const s, void* const elem_addr)
{
    const void* src_addr = NULL;

    assert(!stack_empty(s));

    s->size--;
    src_addr = (const char*) s->elems + s->size * s->elem_sz;
    memcpy(elem_addr, src_addr, s->elem_sz);
}


/******** Parenthesis *********/

typedef struct {
    char first;
    char second;
} Pair;

const Pair     PAR_PAIR[]   = {{'(', ')'}, {'{', '}'}, {'[', ']'}};
const unsigned PAR_PAIR_CNT = sizeof(PAR_PAIR) / sizeof(Pair);

const Pair* par_get_pair    (const char symbol);
bool        par_is_balanced (const char string[], const unsigned length);

const Pair* par_get_pair (const char symbol)
{
    unsigned i = 0;

    for (i = 0; i < PAR_PAIR_CNT; i++)
    {
        if (PAR_PAIR[i].first == symbol || PAR_PAIR[i].second == symbol) {
            return PAR_PAIR + i;
        }
    }
    return NULL;
}

bool par_is_balanced (const char string[], const unsigned length)
{
    Stack       stack;
    const Pair* par_pair;
    const Pair* stack_pair;
    unsigned    i;
    bool        mismatch = false;

    stack_create(&stack, sizeof(const Pair*));

    for (i = 0; i < length && !mismatch; i++)
    {
        /* Obtain the parenthesis information for this symbol */
        par_pair = par_get_pair(string[i]);

        /* The symbol was a parenthesis */
        if (par_pair != NULL)
        {
            /* The symbol was the opening symbol */
            if (par_pair->first == string[i])
            {
                stack_push(&stack, &par_pair);
            }

            /* The symbol was the closing symbol */
            else
            {
                /* There is no parenthesis information on the stack at all */
                if (stack_empty(&stack))
                {
                    mismatch = true;
                }
                else
                {
                    stack_pop(&stack, &stack_pair);

                    /* The expected symbol did not match the encountered one */
                    if (par_pair->second != stack_pair->second)
                       mismatch = true;
                }
            }
        }
    }
    stack_delete(&stack);

    return (!mismatch && stack_empty(&stack));
}


int main(void)
{
    unsigned i = 0;
    const char* EXAMPLE[] =
        { "([])",
          "(([()])))",
          "([()])()" };

    const unsigned EXAMPLE_CNT =
        sizeof(EXAMPLE) / sizeof(char*);

    for (i = 0; i < EXAMPLE_CNT; i++)
    {
        printf("%-15s: ", EXAMPLE[i]);

        if (par_is_balanced(EXAMPLE[i], strlen(EXAMPLE[i])))
                printf("balanced.\n");
        else
                printf("not balanced.\n");
    }
    return 0;
}

[David W]

This may be a little simpler C code ... to get you started?

-> NO dynamic memory used (stack size pre-fixed at compile time)

-> also uses a 'table look-up' method

-> note the simple struct used

/* stack_stuff2.c */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h> /* re. tolower... */


#define SIZE 100

#define TRUE 1
#define FALSE 0

const char BRACES[][2] = { "()", "[]", "{}", "<>" };
const int NUM_BRACES = sizeof BRACES / sizeof *BRACES;

/* return 0 if NOT found, or index+1 where found ... */
int posBraces( char c, int type ) /* type: 0=open; 1=closed */
{
    int i = 0;
    while( i < NUM_BRACES )
    {
        if( c == BRACES[i][type] ) return i+1;
        ++i;
    }
    /* if reach here... NOT found, so ... */
    return 0;
}


typedef struct
{
    int top;
    char items[SIZE];
 } Stack ;

int empty( Stack* ps )
{
    if( ps->top == -1 )
        return TRUE;
    /* else */
    return FALSE;
}

void pop( Stack* ps )
{
    if( !empty(ps) ) ps->top -= 1;
    else
    {
        printf( "Stack Underflow" );
        exit(1);
    }
}

void push( Stack* ps, char c )
{
    if( ps->top < SIZE-1 )
        ps->items[ ++ps->top ] = c;
    else
    {
        printf( "Stack Overflow" );
        exit(2);
    }
}

char top( Stack* ps )
{
    if( !empty( ps ) )
        return  ps->items[ ps->top ]  ;
    /* else ... */
    printf( "Stack is Empty\n" );
    return 'X';
}


char takeInChr( const char* msg )
{
    char chr;
    fputs( msg, stdout ); fflush( stdout );
    chr = getchar();
    if( chr != '\n' )
        while( getchar() != '\n' ) ; /* flush stdin ... */
    return chr;
}
/* defaults to 'true'/'yes'/'1' unless 'n' or 'N' entered */
int more()
{
    if( tolower( takeInChr( "More (y/n) ? " )) == 'n' )
        return 0;
    /* else ... */
    return 1;
}



int main()
{
    char exp[SIZE], *p;
    int j, pos, valid;

    Stack s;

    do
    {
        printf( "Enter a line to check: " ) ;
        fgets( exp, SIZE, stdin );
        p = strchr( exp, '\n' );
        if( p ) *p = '\0'; /* eliminate '\n' at end */
        else
        {
            printf( "The buffer size %d may not be large enough?\n",
                    SIZE );
            while( getchar() != '\n' ) ; /* flush stdin ... */
        }

        /* Ok ... now check the line that was just entered. */

        s.top = -1; /* initial top of stack to -1 */
        valid = TRUE;
        j = 0;

        while( exp[j] != '\0' && valid )
        {
            /* if in set of open braces ... */
            if( (pos = posBraces( exp[j], 0 )) )
                push( &s, exp[j] );

            /* if in set of closed braces ... */
            else if( (pos = posBraces( exp[j], 1)) )
            {
                if( empty( &s ) ) valid = FALSE;
                else
                {
                    if( BRACES[pos-1][0] == top( &s ) )
                        pop( &s );
                    else valid = FALSE;
                }
            }
            ++j;
        }

        /* Now test and report re. 'exit state' ... */

        if( empty(&s) && valid )
            printf( "The line '%s' is Valid\n", exp );
        else
            printf( "The line '%s' is Invalid\n", exp );
    }
    while( more() );

    return 0;
}