Scribd
Upload
5 views27 pages

Stack Implementation in C and C++

Uploaded by

kumarikritika2028
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views27 pages

Stack Implementation in C and C++

Uploaded by

kumarikritika2028
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Stack using Array

#include <stdio.h>
#include <stdlib.h>

struct Stack
{
int size;
int top;
int *S;
};

void create(struct Stack *st)


{
printf("Enter Size");
scanf("%d",&st->size);
st->top=-1;
st->S=(int *)malloc(st->size*sizeof(int));
}

void Display(struct Stack st)


{
int i;
for(i=[Link];i>=0;i--)
printf("%d ",st.S[i]);
printf("\n");

void push(struct Stack *st,int x)


{
if(st->top==st->size-1)
printf("Stack overflow\n");
else
{
st->top++;
st->S[st->top]=x;
}
}

int pop(struct Stack *st)


{
int x=-1;

if(st->top==-1)
printf("Stack Underflow\n");
else
{
x=st->S[st->top--];
}
return x;
}

int peek(struct Stack st,int index)


{
int x=-1;
if([Link]-index+1<0)
printf("Invalid Index \n");
x=st.S[[Link]-index+1];

return x;
}

int isEmpty(struct Stack st)


{
if([Link]==-1)
return 1;
return 0;
}

int isFull(struct Stack st)


{
return [Link]==[Link]-1;
}

int stackTop(struct Stack st)


{
if(!isEmpty(st))
return st.S[[Link]];
return -1;
}

int main()
{
struct Stack st;
create(&st);

push(&st,10);
push(&st,20);
push(&st,30);
push(&st,40);

printf("%d \n",peek(st,2));

Display(st);

return 0;
}
Stack using Linked List

#include <stdio.h>
#include <stdlib.h>

struct Node
{
int data;
struct Node *next;
}*top=NULL;

void push(int x)
{
struct Node *t;
t=(struct Node*)malloc(sizeof(struct Node));

if(t==NULL)
printf("stack is full\n");
else
{
t->data=x;
t->next=top;
top=t;
}

int pop()
{
struct Node *t;
int x=-1;

if(top==NULL)
printf("Stack is Empty\n");
else
{
t=top;
top=top->next;
x=t->data;
free(t);
}
return x;
}

void Display()
{
struct Node *p;
p=top;
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}

int main()
{
push(10);
push(20);
push(30);

Display();

printf("%d ",pop());

return 0;
}
Infix to Postfix Conversion
#include <stdio.h>
#include <stdlib.h>
#include<strings.h>

struct Node
{
char data;
struct Node *next;
}*top=NULL;

void push(char x)
{
struct Node *t;
t=(struct Node*)malloc(sizeof(struct Node));

if(t==NULL)
printf("stack is full\n");
else
{
t->data=x;
t->next=top;
top=t;
}

char pop()
{
struct Node *t;
char x=-1;

if(top==NULL)
printf("Stack is Empty\n");
else
{
t=top;
top=top->next;
x=t->data;
free(t);
}
return x;
}

void Display()
{
struct Node *p;
p=top;
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}

int isBalanced(char *exp)


{
int i;

for(i=0;exp[i]!='\0';i++)
{
if(exp[i]=='(')
push(exp[i]);
else if(exp[i]==')')
{
if(top==NULL)
return 0;
pop();
}
}
if(top==NULL)
return 1;
else
return 0;
}

int pre(char x)
{
if(x=='+' || x=='-')
return 1;
else if(x=='*' || x=='/')
return 2;
return 0;
}

int isOperand(char x)
{
if(x=='+' || x=='-' || x=='*' || x=='/')
return 0;
else
return 1;

char * InToPost(char *infix)


{
int i=0,j=0;
char *postfix;
int len=strlen(infix);
postfix=(char *)malloc((len+2)*sizeof(char));

while(infix[i]!='\0')
{
if(isOperand(infix[i]))
postfix[j++]=infix[i++];
else
{
if(pre(infix[i])>pre(top->data))
push(infix[i++]);
else
{
postfix[j++]=pop();
}
}
}
while(top!=NULL)
postfix[j++]=pop();
postfix[j]='\0';
return postfix;
}

int main()
{
char *infix="a+b*c-d/e";
push('#');

char *postfix=InToPost(infix);

printf("%s ",postfix);

return 0;
}
Parenthesis Matching

#include <stdio.h>
#include <stdlib.h>

struct Node
{
char data;
struct Node *next;
}*top=NULL;

void push(char x)
{
struct Node *t;
t=(struct Node*)malloc(sizeof(struct Node));

if(t==NULL)
printf("stack is full\n");
else
{
t->data=x;
t->next=top;
top=t;
}

char pop()
{
struct Node *t;
char x=-1;

if(top==NULL)
printf("Stack is Empty\n");
else
{
t=top;
top=top->next;
x=t->data;
free(t);
}
return x;
}

void Display()
{
struct Node *p;
p=top;
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}

int isBalanced(char *exp)


{
int i;

for(i=0;exp[i]!='\0';i++)
{
if(exp[i]=='(')
push(exp[i]);
else if(exp[i]==')')
{
if(top==NULL)
return 0;
pop();
}
}
if(top==NULL)
return 1;
else
return 0;
}
int main()
{
char *exp="((a+b)*(c-d)))";

printf("%d ",isBalanced(exp));

return 0;
}
#include <iostream>
#include<cstring>
using namespace std;

class Node{
public:
char data;
Node* next;
};

class Stack{
private:
Node* top;
public:
Stack();
~Stack();
void push(char x);
char pop();
char peek(int index);
int isEmpty();
int isFull();
char stackTop();
};

Stack::Stack() {
top = nullptr;
}

Stack::~Stack() {
Node* p = top;
while (top){
top = top->next;
delete p;
p = top;
}
}

void Stack::push(char x) {
Node* t = new Node;
if (t == nullptr){
cout << "Stack Overflow!" << endl;
} else {
t->data = x;
t->next = top;
top = t;
}
}

char Stack::pop() {
Node* p;
char x = -1;
if (top == nullptr){
cout << "Stack Underflow!" << endl;
} else {
p = top;
x = p->data;
top = top->next;
delete p;
}
return x;
}

int Stack::isFull() {
Node* t = new Node;
int r = t ? 1 : 0;
delete t;
return r;
}

int Stack::isEmpty() {
return top ? 0 : 1;
}

char Stack::stackTop() {
if (top){
return top->data;
}
return -1;
}

char Stack::peek(int index) {


if (isEmpty()){
return -1;
} else {
Node* p = top;

for (int i=0; p != nullptr && i<index-1; i++){


p = p->next;
}

if (p != nullptr){
return p->data;
} else {
return -1;
}
}
}

int isBalanced(char* exp){


Stack stk;

for (int i=0; i<strlen(exp); i++){


if (exp[i] == '('){
[Link](exp[i]);
} else if (exp[i] == ')'){
if ([Link]()){
return false;
} else {
[Link]();
}
}
}
return [Link]() ? true : false;
}

int main() {

char E[] = "((a+b)*(c-d))";


cout << isBalanced(E) << endl;

char F[] = "((a+b)*(c-d)))";


cout << isBalanced(F) << endl;

char G[] = "(((a+b)*(c-d))";


cout << isBalanced(G) << endl;

return 0;

}
#include <iostream>
#include<cstring>
#include <stack>
#include <map>

using namespace std;

int isBalanced(char* exp){

// Create map
map<char, char> mapping;
mapping['}'] = '{';
mapping[')'] = '(';
mapping[']'] = '[';

// Create map iterator


map<char, char>::iterator itr;

// Create stack
stack<char> stk;

for (int i=0; i<strlen(exp); i++){


if (exp[i] == '{' || exp[i] == '[' || exp[i] == '('){
[Link](exp[i]);
} else if (exp[i] == '}' || exp[i] == ']' || exp[i] == ')'){
if ([Link]()){
return false;
} else {
char temp = [Link]();
itr = [Link](exp[i]);
if (temp == itr->second){ // itr->first is key, itr-
>second is value
[Link]();
} else {
return false;
}
}
}
}
return [Link]() ? true : false;
}

int main() {

char A[] = "{([a+b]*[c-d])/e}";


cout << isBalanced(A) << endl;

char B[] = "{([a+b]}*[c-d])/e}";


cout << isBalanced(B) << endl;

char C[] = "{([{a+b]*[c-d])/e}";


cout << isBalanced(C) << endl;

return 0;
}
Infix to Postfix Conversion
#include <stdio.h>
#include <stdlib.h>
#include<strings.h>

struct Node
{
char data;
struct Node *next;
}*top=NULL;

void push(char x)
{
struct Node *t;
t=(struct Node*)malloc(sizeof(struct Node));

if(t==NULL)
printf("stack is full\n");
else
{
t->data=x;
t->next=top;
top=t;
}

char pop()
{
struct Node *t;
char x=-1;

if(top==NULL)
printf("Stack is Empty\n");
else
{
t=top;
top=top->next;
x=t->data;
free(t);
}
return x;
}

void Display()
{
struct Node *p;
p=top;
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}

int isBalanced(char *exp)


{
int i;

for(i=0;exp[i]!='\0';i++)
{
if(exp[i]=='(')
push(exp[i]);
else if(exp[i]==')')
{
if(top==NULL)
return 0;
pop();
}
}
if(top==NULL)
return 1;
else
return 0;
}

int pre(char x)
{
if(x=='+' || x=='-')
return 1;
else if(x=='*' || x=='/')
return 2;
return 0;
}

int isOperand(char x)
{
if(x=='+' || x=='-' || x=='*' || x=='/')
return 0;
else
return 1;

char * InToPost(char *infix)


{
int i=0,j=0;
char *postfix;
int len=strlen(infix);
postfix=(char *)malloc((len+2)*sizeof(char));

while(infix[i]!='\0')
{
if(isOperand(infix[i]))
postfix[j++]=infix[i++];
else
{
if(pre(infix[i])>pre(top->data))
push(infix[i++]);
else
{
postfix[j++]=pop();
}
}
}
while(top!=NULL)
postfix[j++]=pop();
postfix[j]='\0';
return postfix;
}

int main()
{
char *infix="a+b*c-d/e";
push('#');

char *postfix=InToPost(infix);

printf("%s ",postfix);

return 0;
}
Evaluation of Postfix
#include <stdio.h>
#include <stdlib.h>
#include<strings.h>

struct Node
{
int data;
struct Node *next;
}*top=NULL;

void push(int x)
{
struct Node *t;
t=(struct Node*)malloc(sizeof(struct Node));

if(t==NULL)
printf("stack is full\n");
else
{
t->data=x;
t->next=top;
top=t;
}

int pop()
{
struct Node *t;
int x=-1;

if(top==NULL)
printf("Stack is Empty\n");
else
{
t=top;
top=top->next;
x=t->data;
free(t);
}
return x;
}

void Display()
{
struct Node *p;
p=top;
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}

int isBalanced(char *exp)


{
int i;

for(i=0;exp[i]!='\0';i++)
{
if(exp[i]=='(')
push(exp[i]);
else if(exp[i]==')')
{
if(top==NULL)
return 0;
pop();
}
}
if(top==NULL)
return 1;
else
return 0;
}
int pre(char x)
{
if(x=='+' || x=='-')
return 1;
else if(x=='*' || x=='/')
return 2;
return 0;
}

int isOperand(char x)
{
if(x=='+' || x=='-' || x=='*' || x=='/')
return 0;
else
return 1;

char * InToPost(char *infix)


{
int i=0,j=0;
char *postfix;
long len=strlen(infix);
postfix=(char *)malloc((len+2)*sizeof(char));

while(infix[i]!='\0')
{
if(isOperand(infix[i]))
postfix[j++]=infix[i++];
else
{
if(pre(infix[i])>pre(top->data))
push(infix[i++]);
else
{
postfix[j++]=pop();
}
}
}
while(top!=NULL)
postfix[j++]=pop();
postfix[j]='\0';
return postfix;
}

int Eval(char *postfix)


{
int i=0;
int x1,x2,r=0 ;

for(i=0;postfix[i]!='\0';i++)
{
if(isOperand(postfix[i]))
{
push(postfix[i]-'0');
}
else
{
x2=pop();x1=pop();
switch(postfix[i])
{
case '+':r=x1+x2; break;
case '-':r=x1-x2; break;
case '*':r=x1*x2; break;
case '/':r=x1/x2; break;
}
push(r);
}
}
return top->data;
}

int main()
{
char *postfix="234*+82/-";

printf("Result is %d\n",Eval(postfix));

return 0;
}

You might also like