Example A. "(){}" is valid B. "({[]})” is valid C. “((})” is invalid
Friday, May 4, 2012
You are given a string of ‘n’ characters where n is even. The string only consist of 6 type of characters: (){}[]. The task is to form a well formed expression. A well formed expression consist of proper nesting of braces and their is no priority between the braces like [ > } > ). You can edit any bracket and change it to remaining types for accomplishing the task.
Subscribe to:
Post Comments
(
Atom
)
10 comments :
Can you please give ur suggestions...how to approach this problem.
Here is my approach for this problem:
1- Create an array of size 6. Each index will cater the count of each type of character.Also keep the start and end type of each bracket count continuous in the array.
2- Now scan the count array and make the pair of similar brackets depending on the count = min(a[i], a[i+1]).
3- After updating the array every entry will be updated by the a[i] - count values.
- The last step would then be just insert brackets on the remaining count values.
There is a solution for this in the book " Data Structures and Algorithms in Java by Robert Lafore" ..
1) Push the opening braces in the stack, whenever a closing bracket is encounter, pop the element in the stack and match them.
Code:
while(ch=='{' || ch=='[' || ch='(')
{
pushinstack(ch);
}
while(stackis not empty)
{
if(ch=='}'||ch==']'||ch=')')
{
chpop = popstack();
if(ch=='}' && chpop ='{' || ch==']' && chpop ='[' || ch==')' && chpop ='(' )
{
continue;
}
else
{
System.out.println("Error");
}
}
Hope it helps!!
@Shruti ..you are checking whether given expression is balanced or not , but question is saying that you have to produce the balanced expression form given set .
@shetwank naive approach is to generate the permutation of string and then print out the all balanced expression , now come to 2nd approach as you told , will it work for the string like "{[" or "})" etc. ? 'coz if i/p string has length then o/p can of n length only isn't it ?
@Anon ..r u new bee or crazy , u r just spamming the blog dats why we removed the comment , we got d question from 1 of d user and we think u r confused wid problem statement in your mind ..there are many problem looks similer but statement differ . if u think its not d correct , paste that here , we will add that !!!
How much time do you need more?
Post a Comment