UVA Problem 673 – Parentheses Balance Solution

UVA Problem 673 – Parentheses Balance Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

This problem can be solved easily using Stack ( also check out these problems i have solved using stack uva 11192uva 483 ).  Here the only corner case is space character. Input only contains three types of character 1st bracket, 3rd bracket and a space character.

Here i have provided three solutions. All have same logic. But first one is well commented and written for easier understanding. Second one is modified version of first. For the first and second code i take input as string but in the last i take input one by one as characters.

In the second code i have checked if length is odd then i know it can’t be balanced. So i just print NO. Which is “strlen(par) & 1“. It is equivalent to “strlen(par) % 2 == 1” meaning string length is odd.

The logic for this code is whenever we find a closing bracket it must have its corresponding opening bracket before ( to its immediate left ) that. So we remove those two and keep processing rest of the input. Example,

[ [(  )]  ()]

Here we do nothing ( or, store them in string ) when we find an opening bracket. Whenever we find a closing bracket we see the character before that ( to its left ) is its opening bracket. If this condition doesn’t match then there is error in the input. So break immediately. Also when we find a closing bracket with its opening bracket we remove them and process rest of the input. Example,

[ [(  )]  ()]  /* our input */
[ [] ()]       /* we remove first occurrence of closing and its corresponding opening bracket to its left */
[ ()]          /* Process rest of the input */
[ ]
               /* Here nothing is left so it is a valid input */

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.


Critical Input:

More Critical inputs can be found in this link,

https://gist.github.com/quickgrid/72b1adc38d8752cd6905

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

Output:

Yes
No
Yes

Code Usage of Stack ( Explained ):

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 673 ( Parentheses Balance )
 */

#include<stdio.h>

/**
 * Size for our stack although they said 128 but stack safety
 */
#define SIZE 256

/**
 * Our stack or array to hold parenthesis
 */
static char stack[SIZE];
/**
 * Our stack index counter
 */
int top = -1;

/**
 * Push function of out stack, We basically store the character and increase the counter
 * Checking of stack overflow is not implemented since stack size is large enough for this program
 */
void push(char c){
    stack[++top] = c;
}

/**
 * Set the element in current index to NUL and decrease the index
 * Stack underflow never occurs for this program
 */
void pop(){
    stack[top--] = '\0';
}

int main(){
    register unsigned n, i;
    unsigned char c;

    /**
     * Scan the test case count, getchar() is needed because i used gets() below which takes away my new line if getchar() is not used
     */
    scanf("%u", &n); getchar();

    while (n--){
        stack[SIZE] = {'\0'};
        /**
         * Reset the stack index, meaning we start using our stack array from the beginning
         */
        top = -1;
        /**
         * If no error then error is 0 else if there is error then error is 1
         */
        unsigned error = 0;

        /**
         * Our character array to take the input string
         */
        char *par = new char[SIZE + 1];
        gets(par);

        for (i = 0; par[i]; ++i){
            /**
             * Corner case the input can have space
             */
            if(par[i] == ' ')
                continue;

            /**
             * Push the character to stack if open bracket
             */
            if(par[i] == '[' || par[i] == '(')
                push(par[i]);

            /**
             * Pop or remove the element from top of stack if matching closing bracket found
             */
            else if(par[i] == ']' && stack[top] == '[')
                pop();
            else if(par[i] == ')' && stack[top] == '(')
                pop();

            else{
                /**
                 * If matching closing bracket not found then set error flag to 1 (ON)
                 */
                error = 1;
                /**
                 * Since we found a mistake there is no need to process rest of the string
                 */
                break;
            }
        }

        /**
         * If error flag is on or there still exist some brackets on stack then print NO
         */
        if(error || top > -1)
            printf("No\n");
        else
            printf("Yes\n");
    }
    return 0;
}

Taking input as string:(Faster)

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 673 ( Parentheses Balance )
 */

#include<stdio.h>
#include<string.h>

static char stack[256];
static char par[256];
int top;

int main(){
    unsigned n, error;

    scanf("%u", &n);
    getchar();

    while(n--){
        gets(par);

        if(strlen(par) & 1)
            printf("No\n");
        else{
            stack[256] = {'\0'};
            top = -1;
            error = 0;

            for(unsigned i = 0; par[i]; ++i){
                if(par[i] == ' ')
                    continue;

                if(par[i] == '[' || par[i] == '(')
                    stack[++top] = par[i];
                else if((par[i] == ')' && stack[top] == '(') || (par[i] == ']' && stack[top] == '['))
                    --top;
                else{
                    error = 1;
                    break;
                }
            }

            (error || top > -1) ? printf("No\n") : printf("Yes\n");
        }
    }
    return 0;
}

Taking input one by one as characters:

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 673 ( Parentheses Balance )
 */

#include<stdio.h>

#define SIZE 256

char stack[SIZE];

int main(){
    register unsigned n, i;
    unsigned ch;
    scanf("%u", &n); getchar();

    while(n--){
        register int top = -1;
        unsigned error = 0;

        while ((ch = getchar()) != '\n'){
            if (ch == ' ') continue;
            if (ch == '[' || ch == '(') stack[++top] = ch;
            else if ((ch == ']' && stack[top] == '[') || (ch == ')' && stack[top] == '(')) --top;
            else error = 1;
        }

        if (error || top > -1) printf("No\n");
        else printf("Yes\n");
    }
    return 0;
}

2 thoughts on “UVA Problem 673 – Parentheses Balance Solution

  1. i have used space() function to remove space and paren function to find ()or[] relation and if found then they are
    made spaces and space func is called but it shows wa,help me out
    #include
    #include <stdio.h>
    #include <string.h>
    #include
    using namespace std;
    char str[130];
    void paren(int p);
    void space();

    int ck;

    void space(){
    int i,j=0;
    char str1[strlen(str)];
    for(i=0;str[i];i++){
    if(str[i]=='(‘||str[i]==’)’||str[i]=='[‘||str[i]==’]’){
    str1[j]=str[i];
    j++;
    }
    }
    strcpy(str,str1);
    if(j==0)return;
    else
    paren(0);
    }
    void paren(int p){
    int i=p;
    if(str[i]=='[‘&&str[i+1]==’]’){
    str[i]=’ ‘,str[i+1]=’ ‘;
    space();
    }
    if(str[i]=='(‘&&str[i+1]==’)’){
    str[i]=’ ‘,str[i+1]=’ ‘;
    space();
    }
    if(str[i]=='[‘&&(str[i+1]=='(‘||str[i+1]=='[‘))paren(i+1);
    if(str[i]=='(‘&&(str[i+1]=='(‘||str[i+1]=='[‘))paren(i+1);
    if(str[i]=='[‘&&str[i+1]==’)’){
    ck=0;
    return;
    }
    if(str[i]=='(‘&&str[i+1]==’]’){
    ck=0;
    return;
    }
    if(str[i]==’)’||str[i]==’]’){
    ck=0;
    return;
    }

    }
    int main()
    {

    char ch;
    int i,j,k,l,m,n,u,h;
    cin>>h;
    getchar();
    while(h–){
    i=0;
    gets(str);
    k=0,l=0,m=0,n=0;
    ck=1;
    if(strlen(str)==0)printf(“Yes\n”);
    else {
    for(i=0;str[i];i++){
    if(str[i]=='(‘)m++;
    if(str[i]==’)’)n++;
    if(str[i]==’]’)k++;
    if(str[i]=='[‘)l++;
    }
    if(l!=k||m!=n)ck=0;
    if(ck==1){
    space();
    }
    if(ck==0)cout<<“No”<<endl;
    else if(ck==1)cout<<“Yes”<<endl;

    }
    }

    return 0;
    }

    Like

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s