Department of Software Engineering

Data Structures & Algorithms Lab

Lab # 4

SUBMITTED TO:
Sir Rehan Ahmed Siddiqui
SUBMITTED BY:
Mahnoor Mustafa
(2020-BSE-051)
CLASS:
BSE III B
 TASK 1

Convert (manually) the following expressions to postfix.

1. (A+B*D)/(E-F)+G : ABD*+EF-G+/

A*(B+D)/E-F*(G+H/K) : ABD+*EF-GHK/+*/

Convert the following infix expressions to prefix.

2. A*B +(C/E) – (F+G) : -+*AB/CE+FG
A+(B-D)/E-F*(G*H+K) : */+A-BD-EF+*GHK

Evaluate the given Postfix expression and trace the contents of the
Stack at each step
using the standard evaluation algorithm.
273-/215+*+

Symbol Stack Contents

2 2
7 2,7
3 2,7,3
3. - 2,4
/ 0,5
2 0,5,2
1 0,5,2,1
5 0,5,2,1,5
+ 0,5,2,6
* 0,5,1,2
+ 12+2=14

Result : 12.5

4.
Convert the following expression from infix to postfix and show the
contents of Stack and the output expression at each step.
(A+B) * C – D+F*G
 Stack
Output Expression
Symbol Contents

( (
A A
+ + B
B
) ) +
* * C
C D
- - F
D G
+ + *
F +
* * -
G *

OUTPUT : AB+CDFG*+-*

TASK 2
Create a program to find weather a string in palindrome or not using stack.
Palindrome is a word, phrase, or sequence that reads the same backwards as
forwards.
#include"stdafx.h"
#include<iostream>
#include<string>
using namespace std;
const char size=100;
class stack{
private :
char myarr[size];
public:

int mytop;
stack(){
mytop=-1;}
bool epmty()
{
if(mytop==-1)
return true;
 else
return false;}
bool full(){
if(mytop=size-1)
return true;
else
return false;
}
void push(char vale)
{
if(mytop<size-1)
{++mytop;
myarr[mytop]=vale;}
else
cout<<"stack is full"<<endl;;
}
char pop(){
if(mytop>-1)
{
return myarr[mytop--];
}
else
return myarr[size-1];}
void display()
{
if(mytop==size-1)
{
for(int i=0;i<=size-1;i--)
{
cout<<myarr[i];
} } }
};
int _tmain(int argc, _TCHAR* argv[])
{
stack stk;
string str="MADAM";
int count=0;
int length=str.length();
for(int i=0;i<length;i++)
stk.push(str.at(i));
for(int i=0;i<str.length();i++)
{
if(stk.pop()==str.at(i))
{ count=0; }
else
{ count=1; }
}
if(count==0)
cout<<" It is a Palindrome "<<endl;
else
 cout<<" Not a Palindrome "<<endl;

system("pause");
return 0;
}

TASK 3
Implement a program to covert the infix expression to postfix and
display the result on screen
#include"stdafx.h"
#include<iostream>
#include<string>
using namespace std;
const int stack_capacity = 20;

class STACK
{
private:
int arr[stack_capacity];
int my_top;
public:
STACK()
{
my_top = -1;
}

bool empty()
{
if (my_top == -1)
return true;
else
return false;
}

void push (int value)

{
if (my_top < stack_capacity - 1)
{
++my_top;
 arr[my_top] = value;
}
else
cout<<"STACK IS FULL, CAN'T ADD MORE VALUES"<<endl;
}
int top()
{
if (my_top >= 0)
return arr[my_top];
else
return 0;
}
int pop()
{
if (my_top >= 0)
return arr[my_top--];
else
return 0;
}

void display()
{
if(my_top >= 0)
{
cout<<"STACK ELEMENTS ARE:";
for (int i = my_top; i >= 0; i--)
{
cout<<arr[i]<<" ";
}
}
else
cout<<"STACK IS EMPTY"<<endl;
}
};
string Infix_Postfix(string st);
bool Operator(char x);
bool Operand(char x);
int precedence (char x);

int _tmain(int argc, _TCHAR* argv[])

{
string abc;
cout<<"Enter Infix Expression \n";
cin>>abc;
string postfix = Infix_Postfix(abc);
cout<<"POSTFIX Expression = "<<postfix<<endl;
cout<<endl;

system("pause");
return 0;
}

string Infix_Postfix(string s)
{
STACK S;
string output;
for(int i = 0;i<s.length();i++)
{
if((s.at(i)>= 'a' && s.at(i) <= 'z')||(s.at(i)>= 'A' && s.at(i) <= 'Z'))
{
output+=s.at(i);
}

else if(s.at(i)=='(')
{
S.push('(');
}
else if (Operator(s.at(i))==true)
{
if(precedence(s.at(i))<=precedence(S.top()))
{
char ch=S.top();
S.pop();
output+=ch;
}
S.push(s.at(i));
}
else if(s.at(i)==')')
{
while(S.top()!='(')
{
char ch=S.top();
S.pop();
output+=ch;
}
if(S.top()=='(')
{
char c=S.top();
S.pop();
}
}
}
while(S.top()!='\0')
{
char ch=S.top();
S.pop();
output+=ch;
}
return output;
}
bool Operand(char x)
{
if(x >= '0' && x <= '9')
return true;
if(x >= 'a' && x <= 'z')
return true;
if(x >= 'A' && x <= 'Z')
return true;
return false;
}

bool Operator(char x)
{
if(x == '+' || x == '-' || x == '*' || x == '/' || x== '$')
return true;
return false;
}

int precedence(char op)

{
if(op == '^')
return 3;
else if(op == '*' || op == '/')
return 2;
else if(op == '+' || op == '-')
return 1;
else
return -1;
}