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

general
, , ,
1

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.

2

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;

}
2 Likes
3

@geek_geek

and what about recursive approach.

4

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…

1 Like
5

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.

6

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.

7

Balanced Paranthesis

Stack

This is the most optimal way to find out.

#include<bits/stdc++.h>

#include

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;

}