11-01-2012, 10:59 PM
CS301 Data Structure VU Current Assignment No. 1 [size=12]semester Fall November 2012[/SIZE]
In any programming language, when a program containing any expression/string is executed, a language translator such as compiler checks whether the brackets in the expression/string are properly balanced or not. Brackets are properly balanced if each opening bracket has its corresponding closing bracket. Compiler executes the program successfully if expression/string contains properly balanced brackets but generates syntax error in case of unbalanced pair of brackets.
For example, expression/string: [{(A+B)*C}/D], (a+345), and “(Welcome)” contains properly balanced pairs of brackets, but the expression: [{(A+B)*10}/D does not.
Write a program in C++ that prompts a user to enter an expression/string containing brackets. Pass this expression to a function which checks it for balanced/unbalanced pair of brackets. Then, print “Balanced” if this expression has balanced pair of brackets, and print “Unbalanced” otherwise.
Hint:
1. You have to use stack to keep record of left brackets (i.e. opening brackets).
Solution Guidelines:
1. Create a class named “bracket_checker” that should contain following inline functions:
• Constructor( ): To initialize “bracket_cheker” class data members.
• Isempty( ): To check whether a stack is empty or not.
• Push( ) // To push any opening bracket onto the stack
• Pop( ) // To pop bracket from top whenever a closing bracket is found
• Checkbrackets( ) // To check whether brackets are balanced or not
2. Your program should be able to check following pair of brackets:
( ), { }, [ ]
3. You have to check the following:
1. (a). There should be no mismatch of brackets e.g. ‘)’ against ‘{‘
(b). Each opening bracket should contain its corresponding matching closing bracket. E.g. ‘)’ against ‘(‘
2. Expression should not contain only opening brackets
3. Expression should not contain only closing brackets
4. Number of left (opening) and right (closing) brackets should be equal
4. In main() function:
(a). Create an object test of type bracket_checker.
(b). Prompt the user to enter an expression/string and call Check_brackets() function to check whether it is balanced or not. Expression/string entered by user should be passed to Check_brackets() function as parameter.
Note: You are required to test at least two different expressions/strings.
Sample Input:
Following are two different sample input expressions:
• [{((5*3)+(2+5)*(3/2))}/5]
• [{(A*(A*3))+((B+5)*(C-D))*((3/2)-5)}]]
Sample output:
Please open the separate file attached with assignment file.
Note: Your solution can be checked for any expression. So, your program should be able to generate correct output for every expression.
In any programming language, when a program containing any expression/string is executed, a language translator such as compiler checks whether the brackets in the expression/string are properly balanced or not. Brackets are properly balanced if each opening bracket has its corresponding closing bracket. Compiler executes the program successfully if expression/string contains properly balanced brackets but generates syntax error in case of unbalanced pair of brackets.
For example, expression/string: [{(A+B)*C}/D], (a+345), and “(Welcome)” contains properly balanced pairs of brackets, but the expression: [{(A+B)*10}/D does not.
Write a program in C++ that prompts a user to enter an expression/string containing brackets. Pass this expression to a function which checks it for balanced/unbalanced pair of brackets. Then, print “Balanced” if this expression has balanced pair of brackets, and print “Unbalanced” otherwise.
Hint:
1. You have to use stack to keep record of left brackets (i.e. opening brackets).
Solution Guidelines:
1. Create a class named “bracket_checker” that should contain following inline functions:
• Constructor( ): To initialize “bracket_cheker” class data members.
• Isempty( ): To check whether a stack is empty or not.
• Push( ) // To push any opening bracket onto the stack
• Pop( ) // To pop bracket from top whenever a closing bracket is found
• Checkbrackets( ) // To check whether brackets are balanced or not
2. Your program should be able to check following pair of brackets:
( ), { }, [ ]
3. You have to check the following:
1. (a). There should be no mismatch of brackets e.g. ‘)’ against ‘{‘
(b). Each opening bracket should contain its corresponding matching closing bracket. E.g. ‘)’ against ‘(‘
2. Expression should not contain only opening brackets
3. Expression should not contain only closing brackets
4. Number of left (opening) and right (closing) brackets should be equal
4. In main() function:
(a). Create an object test of type bracket_checker.
(b). Prompt the user to enter an expression/string and call Check_brackets() function to check whether it is balanced or not. Expression/string entered by user should be passed to Check_brackets() function as parameter.
Note: You are required to test at least two different expressions/strings.
Sample Input:
Following are two different sample input expressions:
• [{((5*3)+(2+5)*(3/2))}/5]
• [{(A*(A*3))+((B+5)*(C-D))*((3/2)-5)}]]
Sample output:
Please open the separate file attached with assignment file.
Note: Your solution can be checked for any expression. So, your program should be able to generate correct output for every expression.