You are not logged in. Please login at www.codechef.com to post your questions!

×

what could be the most optimum way to check balanced parenthesis?

I have one string which can only have '(' and ')' ex: ((())) or ()()() now I want to check whether this parenthesis is balanced or not.

static boolean isValidSequence(char []s){
    char[] temp=new char[s.length]; //stack
    int k=-1;
    for (int i=0;i<s.length ; i++) {
        if (s[i]=='(') {
            temp[++k]='(';
        }
        else k--;
    }
    if(k==-1)return true;
    return false;
}

This is my solution for the same, please tell me this solutions is correct or not. Could there be any more optimal way to achieve this.

Also show me the recursive implementation for this problem.

asked 31 Jul '16, 08:27

arpit728's gravatar image

2★arpit728
6831462
accept rate: 10%


You can do that without a stack as well

This way is more mempry efficient and faster

static boolean isValidSequence(char []s){
    int k=0;
    for (int i=0; i < s.length ; i++) 
    {
        if (s[i]=='(')
            k++;
        else 
            k--;
         if(k==-1)
            return false;
    }
    if(k==0)
    return true;
    else
    return false;

}
link

answered 31 Jul '16, 08:43

geek_geek's gravatar image

4★geek_geek
43914
accept rate: 16%

@geek_geek

and what about recursive approach.

(31 Jul '16, 09:21) arpit7282★

Use Stack datastructure to check for balanced paranthesis.. for each '(' push in into the stack and for each ')' pop the stack till string ends... if stack is not able to pop in between before the end of the string then its not balanced so break the loop.... if stack get empty at the end then it is balanced.... else not balanced..

link

answered 31 Jul '16, 10:42

chandyshot's gravatar image

4★chandyshot
33810
accept rate: 14%

You can keep a count of '(' and ')' both. Whenever there comes a '(' count++. And whenever any ')' comes count--. If at any time count becomes negative,indicates parenthesis are not balanced.

link

answered 31 Jul '16, 11:05

san1997's gravatar image

5★san1997
1
accept rate: 0%

If you can get advanced method of writing and and ideas are also possible in our writing company. Our writing company name as scholarship essay writing service. It is helps for submitting the thesis papers without any mistakes and errors. The writers can indicates the answers and ideas to the college students at online. Learning and training programs are possible for the students in fast way.

link

answered 11 Aug '16, 10:31

rubushawer's gravatar image

0★rubushawer
-1
accept rate: 0%

Balanced Paranthesis

Stack

This is the most optimal way to find out.

include<bits stdc++.h="">

include<stack>

using namespace std;

int main(){

string s;

cin>>s;

stack <char> st;

for(int i=0;i<s.length();i++){

    if(s[i]=='('){

        st.push('(');

    } else if(s[i]==')'){

        st.pop();

    }

}

if(st.size()==0){

    cout<<"Balanced";

} else {

    cout<<"Unbalanced";

}

return 0;

}

link

answered 01 Sep '17, 11:35

aryankhandal0's gravatar image

3★aryankhandal0
11
accept rate: 0%

edited 01 Sep '17, 11:38

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,643
×1,382
×170
×7

question asked: 31 Jul '16, 08:27

question was seen: 1,583 times

last updated: 10 Oct '17, 17:07