Assignment No. 01
SEMESTER Fall 2012
CS301- Data Structures

Total Marks: 20
Due Date: 07/11/2012

Uploading instructions

For clarity and simplicity, You are required to Upload/Submit only ONE .CPP file.

Note: Use ONLY Dev-C++ IDE.

Objective
The objective of this assignment is

> To make you familiar Programming with the Stack data structure.

Assignment:

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.

Lectures Covered: This assignment covers Lecture # 1-8
Deadline: Your assignment must be uploaded/submitted at or before. November 7, 2012

Solution

/binary addition using stack in STL

// Inclusion of header files
#include<iostream>
#include<stack>
#include<conio.h>
using namespace std;

/* READ BINARY NUMBER */
stack<int> read()
{
stack<int> s;
int x,n,i;

cout<<”\nEnter the no. of bits in the no. :”;
cin>>n;
cout<<”\nEnter the binary number : “;

for(i=0;i<n;i++)
{
cin>>x;
s.push(x);
}
return s;
}
/* DISPLAY FUNCTION */

void display(stack<int> &s)
{
cout<<” “;
while(!s.empty())
{
cout<<s.top()<<” “;
s.pop();
}
}
/* ADDITION OF TWO BINARY NOS.*/
stack<int> add(stack<int> &s1,stack<int> &s2)
{
stack<int> s;
int sum,carry=0,b1,b2;

while(!s1.empty()||!s2.empty())
{
b1=b2=0;
if(!s1.empty())
{
b1=s1.top();
s1.pop();
}
if(!s2.empty())
{
b2=s2.top();
s2.pop();

}
sum=(b1+b2+carry)%2;
carry=(b1+b2+carry)/2;
s.push(sum);
}
if(carry==1)
s.push(1);
return s;
}

/* MAIN FUNCTION*/

int main()
{
stack<int> s1,s2,s3;
int ch;

cout<<”\n\t\t\t***MENU***\n”;
cout<<”\n1……..Read first number”
<<”\n2……..Read second number”
<<”\n3……..Display addtion of two numbers”
<<”\n4……..Exit”;

do
{
cout<<”\nEnter your choice..: “;
cin>>ch;

switch(ch)
{
case 1:
s1=read();
break;

case 2:
s2=read();
break;

case 3:
cout<<”\nThe result of addition is :”;
s3=add(s1,s2);
display(s3);
break;
}
}while(ch!=4);
return 0;
getch();
}

…………………………………………….

#include <iostream.h>
#include<stdlib.h>
using namespace std;
class Bin_Add
{
public:
Bin_Add() { current = -1;}
int top(){return A[current];}
int pop(){ return A[current--];}
void push(int x) {A[++current] = x;}
int isEmpty(){return ( current == -1 );}
void add();

private:

int current;
int A[20];
int x;
int y;
};
int main()
{
int n=0, a=0,b=0;
Bin_Add b1,b2,b3,b_Sum;

cout <<”\n Pleas Enter the number of bits in each binary number = “;
cin >> n;
cout <<”\n Pleas Enter 1stbinary number bit by bit = \n”;
for (int i=0; i<n ;i++)
{
cin >> a;
b1.push(a);
}
cout <<”\n Pleas Enter 1stbinary number bit by bit = \n”;
for (int i=0; i<n ;i++)
{
cin >> b;
b2.push(b);
}
/********************** */ /* ADDITION OF TWO BINARY NOS.*/
int sum,carry=0,x1,x2;
while(!b1.isEmpty()||!b2.isEmpty())
{
x1=x2=0;
if(!b1.isEmpty())
{
x1=b1.top();
b1.pop();
}
if(!b2.isEmpty())
{
x2=b2.top();
b2.pop();
}
sum = (x1+x2+carry)%2;
carry=(x1+x2+carry)/2;
b3.push(sum);
}
if(carry==1)
b3.push(1);
cout << “\n Sum of binary number is = “;
while(!b3.isEmpty())
{
cout << b3.top();
b3.pop();
}
cout << “\n “;
/**************************************************** */
system(“pause”);
}