/*******************************************************
APPLICATION : Stack Implementation of Linked List
CODED BY : Ankit Pokhrel
COMPILED ON : Borland C++ Ver 5.02
DATE : 2010 - June - 29
********************************************************/
#include "iostream.h"
#include "conio.h"
#include "process.h"
struct Stack //Structure to represent Stack
{
int data;
struct Stack *next; //Pointer to next node
};
typedef struct Stack node; //Now, node represent Structure Stack
node *New,*head = NULL,*top = NULL; //Global Variables
void create()
{
New = new node; //Create a new node
New -> data = NULL; //Initialize data
New -> next = NULL; //Initialize next pointer field
if(head == NULL) //if first node
{
head = New; //Initialize head
top = New; //Update top
}
}
void push(int ITEM)
{
node *temp = head;
if(head == NULL) //if First Item is Pushed to Stack
{
create(); //Create a Node
head -> data = ITEM; //Insert Item to head of List
return; //Exit from Function
}
create(); //Create a new Node
New -> data = ITEM; //Insert Item
while(temp -> next != NULL)
temp = temp -> next; //Go to Last Node
temp -> next = New; //Point New node
top = New; //Update top
}
node* pop()
{
node *temp = head,*deleted;
if(top == NULL) //If the Stack is Empty
{
cout << "\nStack Underflow";
exit(0); //Exit from Program
}
if(top == head) //If only one Item
{
deleted = head;
head = top = NULL; //Set head and top to Null
return deleted; //Return deleted node
}
while(temp -> next != top)
temp = temp -> next; //move pointer temp to second last node
temp -> next = NULL; //Second last node points to NULL
deleted = top; //Save topmost node
top = temp; //Update top
return deleted; //Return deleted node
}
void display()
{
if(head == NULL) //if no items
{
cout << "Stack is empty";
return;
}
node *temp = head;
cout << temp -> data << ' '; //Print First Item
while(temp -> next != NULL)
{
temp = temp -> next; //Move to next node
cout << temp -> data << ' '; //Print Next Item
}
}
int main()
{
node *n;
int i;
for(i = 1;i <= 5;i++)
push(5*i); //Push 5 elements on Stack
cout << "The elements of Stack are : ";
display(); //Display all Elements
for(i = 1;i <= 5;i++)
{
n = pop(); //Pop elements
cout << endl << "\nDeleted Item : " << n -> data << endl; //Display deleted element
cout << "The elements of Stack are : ";
display(); //Display all Elements
}
cout << "\n\nThis is Stack Underflow Condition (No Items on Stack).";
getch();
n = pop(); //Stack Underflow Condition (no Items on Stack)
return 0;
}
Stack Implementation of Linked List
Program to Evaluate the given Postfix Expression
/*******************************************************
APPLICATION : Evaluation of Postfix Expression
CODED BY : Ankit Pokhrel
COMPILED ON : Borland C++ Ver 5.02
DATE : 2010 - June - 10
********************************************************/
#include "iostream.h"
#include "conio.h"
#include "stdio.h"
#include "math.h"
/*********** Class to Represent Stack ************/
template "class T"
class stack
{
private:
T *arr;
int TOP,MAXSTK;
public:
stack()
{
MAXSTK = 31;
arr = new T[MAXSTK];
TOP = 0;
}
stack(int n)
{
MAXSTK = n + 1;
arr = new T[MAXSTK];
TOP = 0;
}
friend void push(stack &,T); //Push an Item to Stack
friend T pop(stack &); //Pop an Item From Stack
friend int empty(stack); //To Check wheter the stack is empty or not
~stack()
{
delete arr; //Destroy arr
}
};
template "class T"
void push(stack "T" &s, T item)
{
if(s.TOP != s.MAXSTK)
{
s.TOP += 1;
s.arr[s.TOP] = item;
}
else //Overflow Condition
cout << "\nStack Overflow.";
}
template "class T"
T pop(stack "T" &s)
{
T temp;
if(s.TOP != 0)
{
temp = s.arr[s.TOP];
s.TOP -= 1;
return temp;
}
else //Underflow Condition
{
temp = -999;
return temp;
}
}
template "class T"
int empty(stack "T" s)
{
if(s.TOP == 0) //Stack is empty
return 1;
else
return 0;
}
int main()
{
char postfix[30],temp[8];
int i = 0;
cout << "Enter a Valid Postfix Expression,\n";
cout << "Write Expression in One Line Seperated by Space,\n";
cout << "Hit Enter when Finished\n\n";
postfix[i - 1] = '\0';
while(postfix[i-1] != '\n') //Until a user hit Enter key
postfix[i++] = getchar(); //Get a Character
stack "float" stk(50); //Float Stack
float value,operand1,operand2,item;
i = 0;
int j,pos = 0,k;
while(postfix[i-1] != '\n')
{
if(postfix[i] >= '0' && postfix[i] <= '9') //If Number is found
{
temp[0] = postfix[i]; // Save Postfix[i] to temp
j = i+1;
k = 1;
if(postfix[i+1] != ' ') //Check for next character, If not Space
{
while(postfix[j] != ' ') //While space is not found
temp[k++] = postfix[j++]; //Save Postfix[j] to temp
}
temp[k] = '\0'; //End String temp
pos = j + 1; //Update position
item = atof(temp); //Convert string temp to float and store to item
push(stk,item); //Push to stack
}
else if(postfix[i] == '+' || postfix[i] == '-' || postfix[i] == '*' || postfix[i] == '/' || postfix[i] == '$' || postfix[i] == ' ') //If Operator is found
{
operand2 = pop(stk); //Pop operand2 from Stack
if(operand2 == -999) //if Underflow Condition
break; //break from loop
operand1 = pop(stk); //Pop operand1 from Stack
if(operand1 == -999)
break;
if(postfix[i] == '+')
value = operand1 + operand2;
if(postfix[i] == '-')
value = operand1 - operand2;
if(postfix[i] == '*')
value = operand1 * operand2;
if(postfix[i] == '/')
if(operand2 != 0)
value = operand1 / float(operand2);
else
{
cout << "\nError ! Cannot Divide by Zero";
getch();
return 0;
}
if(postfix[i] == '$') //Power
value = pow(operand1,operand2);
push(stk,value); //Push result to stack
pos += 2; //Update position
}
else
{
cout << "\nError : Illegal Character";
getch();
return 0;
}
i = pos; //Update i
}
float Result = pop(stk); //Pop Result
if(Result == -999 || !empty(stk))//If Underflow Condition or stack is not empty, Print Error message and exit
{
cout << "\nError : The Given Postfix Expression is Not Valid.";
getch();
return 0;
}
else //Print Result
cout << "\nResult = " << Result;
getch();
return 0;
}
/*******************************************************
APPLICATION : Evaluation of Prefix Expression
CODED BY : Ankit Pokhrel
COMPILED ON : Borland C++ Ver 5.02
DATE : 2010 - June - 11
********************************************************/
#include "iostream.h"
#include "conio.h"
#include "stdio.h"
#include "math.h"
#include "string.h"
template "class T"
class stack
{
private:
T *arr;
int TOP,MAXSTK;
public:
stack()
{
MAXSTK = 31;
arr = new T[MAXSTK];
TOP = 0;
}
stack(int n)
{
MAXSTK = n + 1;
arr = new T[MAXSTK];
TOP = 0;
}
friend void push(stack &,T);
friend T pop(stack &);
friend int empty(stack);
~stack()
{
delete arr;
}
};
template "class T"
void push(stack "T" &s, T item)
{
if(s.TOP != s.MAXSTK)
{
s.TOP += 1;
s.arr[s.TOP] = item;
}
else
cout << "\nStack Overflow.";
}
template "class T"
T pop(stack "T" &s)
{
T temp;
if(s.TOP != 0)
{
temp = s.arr[s.TOP];
s.TOP -= 1;
return temp;
}
else
{
temp = -999;
return temp;
}
}
template "class T"
int empty(stack "T" s)
{
if(s.TOP == 0)
return 1;
else
return 0;
}
int main()
{
char prefix[30],temp[2];
int i = 0;
float item;
cout << "Enter a Valid Prefix Expression,\n";
cout << "Write Expression in One Line Seperated by Space,\n";
cout << "Hit Enter when Finished\n\n";
prefix[i - 1] ='\0';
while(prefix[i-1] != '\n')
prefix[i++] = getchar();
stack "float" stk(50);
float value,operand1,operand2;
int j = i - 2,pos,k;
while(j >= 0)
{
pos = 0;
if(prefix[j] >= '0' && prefix[j] <= '9')
{
temp[0] = prefix[j]; // Save Prefix[j] to temp
i = j - 1;
k = 1;
if(prefix[j-1] != ' ') //Check for next character, If not Space
{
while(prefix[i] != ' ') //While space is not found
{
temp[k++] = prefix[i--]; //Save Prefix[i] to temp
pos++; //Increase Position
}
pos += 2;//At Last Increase Position by 2 to Skip Space
}
else //If a Single Character
pos = 2; //Skip Space
temp[k] = '\0'; //End String temp
strrev(temp);
item = atof(temp); //Convert string temp to float and store to item
push(stk,item); //Push to stack
}
else if(prefix[j] == '+' || prefix[j] == '-' || prefix[j] == '*' || prefix[j] == '/' || prefix[j] == '$' || prefix[j] == 'l' || prefix[j] == '#' || prefix[j] == ' ')
{
operand1 = pop(stk);
if(operand1 == -999)
break;
if(prefix[j] == '+' || prefix[j] == '-' || prefix[j] == '*' || prefix[j] == '/' || prefix[j] == '$')
{
operand2 = pop(stk);
if(operand2 == -999)
break;
}
if(prefix[j] == '+')
value = operand1 + operand2;
if(prefix[j] == '-')
value = operand1 - operand2;
if(prefix[j] == '*')
value = operand1 * operand2;
if(prefix[j] == '/')
{
if(operand2 != 0)
value = operand1 / float(operand2); //Cast one operand to float
else
{
cout << "\nError ! Cannot Divide by Zero";
getch();
return 0;
}
}
if(prefix[j] == '$')
value = pow(operand1,operand2);
if(prefix[j] == 'l')
value = log10(float(operand1));
if(prefix[j] == '#')
value = sqrt(operand1);
push(stk,value);
pos = 2;
}
else
{
cout << "\nError : Illegal Character";
getch();
return 0;
}
j -= pos;
}
float Result = pop(stk);
if(Result == -999 || !empty(stk)) //If Underflow Condition or stack is not empty, Print Error message and exit
{
cout << "\nError : The Given Prefix Expression is Not Valid.";
getch();
return 0;
}
else
cout << "\nResult = " << Result;
getch();
return 0;
}
#include "iostream.h"
#include "conio.h"
#include "stdio.h"
#include "stdlib.h"
template
class stack
{
private:
T *arr;
int TOP,MAXSTK;
public:
stack() //Default Constructor
{
MAXSTK = 31;
arr = new T[MAXSTK];
TOP = 0;
}
stack(int n) //Parameterized Constructor
{
MAXSTK = n + 1;
arr = new T[MAXSTK];
TOP = 0;
}
friend void push(stack &,T);
friend T pop(stack &);
friend int empty(stack);
~stack()
{
delete arr;
}
};
template
void push(stack
{
if(s.TOP != s.MAXSTK)
{
s.TOP += 1;
s.arr[s.TOP] = item;
}
else
cout << "\nData Overflow.";
}
template
T pop(stack
{
if(s.TOP != 0)
{
T temp = s.arr[s.TOP];
s.TOP -= 1;
return temp;
}
else
cout << "\nData Underflow.";
}
template
int empty(stack
{
if(s.TOP == 0)
return 1;
else
return 0;
}
int main()
{
clrscr();
const int True = 1,False = 0;
int valid = True,i = 0;
stack
char str[100];
cout << "Enter an Expression\n";
while(str[i-1] != '\n')
{
str[i] = getchar();
if(str[i] == '(' || str[i] == '{' || str[i] == '[') //If (,{ or [ is encountered
push(s,str[i]); //Push to Stack
if(str[i] == ')' || str[i] == '}' || str[i] == ']') //If ),} or ] is encountered
{
if(i == 0)
valid = False;
else
{
char ch = pop(s); //Pop Stack
if(str[i] == ')' && ch != '(')
valid = False;
if(str[i] == '}' && ch != '{')
valid = False;
if(str[i] == ']' && ch != '[')
valid = False;
}
}
i++; //Update i
}
if(!empty(s)) //If the Stack is not Empty at Last
valid = False; //Set valid = false
if(valid)
cout << "\nCorrect String Format";
else
cout << "\nIncorrect String Format";
getch();
return 0;
}