Heading

A stack is a linear ordered Abstract Data Type (ADT) in which all the insertions and deletions are done on the same end called top. It follows the Last In First Out (LIFO) or First In Last Out (FILO) order. i.e., the first element inserted is the last to be deleted (or) the last element inserted is the first to be removed from the stack.
The concept of stacks can be clearly explained using the example of a pile of plates. The plate which is kept first is taken out at last.

So if you want to remove the yellow plate, you need to pick black and red plate.

The two main operations that can be performed on the stack are push and pop.
Push : Inserting an element into the stack is called push operation.
Pop : Deleting or removing an element from the stack is called the pop operation
Traverse: Traversing operation involves processing all the elements of the stack and printing them (or performing some other operation)
For example, consider the stack as follows:

Thus, removing 22 implies, pop the element 22.
Similarly, adding implies push the element 55.
The order as clear is Last in, First Out(LIFO) or First in, Last Out(FILO).

The other auxillary stack operations that can be performed on the stack are:
top() : returning the element indicated by the top pointer
size() : Number of elements in the stack is returned
isEmpty() : checks whether the stack is empty or not
isFull() : checks whether the stack is full

Infix notation:
In an infix expression, the operator is between the two operands of an operation. The infix expression can be interpreted and evaluated directly without converting it to any other notation.
Example:
5+2*3
In the above expression, the operator appears between the operands. This expression can be evaluated by applying the basic mathematical expression simplification rules. 5+2*3 = 5+6 = 11
Prefix notation:
In a prefix expression, the operators precede the corresponding operands on which they work. The prefix expression can be evaluated only after converting it to infix notation.
Example:
*-40/8 2 - /200 10 4
The infix notation of the given prefix expression is ((40-(8/2))*((200/10)-4). This infix expression can be simplified as (40-4)*(20-4) = 36*16 = 576

Postfix notation:
In a postfix expression, the operators come after the corresponding operands on which they work. The postfix expression can be evaluated only after converting it to infix notation.
Example:
30 2*4+
The infix notation of the above postfix expression is ((30*2)+4). By evaluating the infix notation, we get 60+4 = 64. So, 64 is the answer for the given postfix expression.

Steps to convert Infix expression to Postfix
1.Scan all the characters one by one from left to right.
2.If the character is an operand, then print it.
3.Else,
a.If the precedence of the operator scanned is greater than that of the operator on the top of the stack, then push the scanned operator into the stack.
b.Else, pop and print all the operators from the stack until the operator at the top of the stack has lower precedence that that of the scanned operator.
c.If the character is ‘(‘, then push it into the stack.
d.If the character is ‘)’, then print all the elements in the stack until ‘(‘ is encountered.
4.Repeat the steps ii) and iii) until the entire infix expression is scanned.
5.Pop and print the remaining elements from the stack.

C Code
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include <string.h>

char infix_string[20], postfix_string[20];
int top;
int stack[20];

int pop();
int precedence(char symbol);
int isEmpty();
void infix_to_postfix();
int check_space(char symbol);
void push(long int symbol);

int main()
{
int count, length;
char temp;
top = -1;
printf("\nEnter the infix expression ");
scanf("%s", infix_string);
infix_to_postfix();
printf("\nThe Postfix expression is: %s\n", postfix_string);
return 0;
}

/* Function to convert from infix to postfix */
void infix_to_postfix()
{
unsigned int count, temp = 0;
char next;
char symbol;
for(count = 0; count < strlen(infix_string); count++)
{
symbol = infix_string[count];
if(!check_space(symbol))
{
switch(symbol)
{
case '(': push(symbol);
break;
case ')':
while((next = pop()) != '(') // pop until '(' is encountered
{
postfix_string[temp++] = next;
}
break;
case '+':
case '-':
case '*':
case '/':
case '%':
case '^':
while(!isEmpty() && precedence(stack[top]) >= precedence(symbol)) // Check precedence and push the higher one
postfix_string[temp++] = pop();
push(symbol);
break;
default:
postfix_string[temp++] = symbol;
}
}
}
while(!isEmpty())
{
postfix_string[temp++] = pop();
}
postfix_string[temp] = '\0';
}

/* Function to check precedence of operators */
int precedence(char symbol)
{
switch(symbol)
{
case '(': return 0;
case '+':
case '-':
return 1;
case '*':
case '/':
case '%':
return 2;
case '^':
return 3;
default:
return 0;
}
}

int check_space(char symbol)
{
if(symbol == '\t' || symbol == ' ' )
{
return 1;
}
else
{
return 0;
}
}

void push(long int symbol)
{
if(top > 20)
{
printf("Stack Overflow\n");
exit(1);
}
top = top + 1;
stack[top] = symbol; // Push the symbol and make it as TOP
}

int isEmpty()
{
if(top == -1)
{
return 1;
}
else
{
return 0;
}
}

int pop()
{
if(isEmpty())
{
printf("Stack is Empty\n");
exit(1);
}
return(stack[top--]); // Pop the symbol and decrement TOP
}

Steps to convert Postfix Expression to Infix
1.Scan the Postfix expression from Left to Right
2.If the character scanned is an operand, push it into the stack
3.If the scanned character is an operator, pop the top element from the stack and print it. Then, print the scanned operator. Next, pop another element from the stack and print it.
4.Repeat the steps ii) and iii) until the whole expression is scanned.
5.Pop the remaining element from the stack and print it.

C Code
#include <stdio.h>
#include <stdlib.h>
int top = 10;
struct node
{
char ch;
struct node *next;
struct node *prev;
} *stack[11];
typedef struct node node;

void push(node *str)
{
if (top <= 0)
printf("Stack is Full ");
else
{
stack[top] = str;
top--;
}
}

node *pop()
{
node *exp;
if (top >= 10)
printf("Stack is Empty ");
else
exp = stack[++top];
return exp;
}
void convert(char exp[])
{
node *op1, *op2;
node *temp;
int i;
for (i=0;exp[i]!='\0';i++)
if (exp[i] >= 'a'&& exp[i] <= 'z'|| exp[i] >= 'A' && exp[i] <= 'Z')
{
temp = (node*)malloc(sizeof(node));
temp->ch = exp[i];
temp->next = NULL;
temp->prev = NULL;
push(temp);
}
else if (exp[i] == '+' || exp[i] == '-' || exp[i] == '*' || exp[i] == '/' ||
exp[i] == '^')
{
op1 = pop();
op2 = pop();
temp = (node*)malloc(sizeof(node));
temp->ch = exp[i];
temp->next = op1;
temp->prev = op2;
push(temp);
}
}

void display(node *temp)
{
if (temp != NULL)
{
display(temp->prev);
printf("%c", temp->ch);
display(temp->next);
}
}

void main()
{
char exp[50];
clrscr();
printf("Enter the postfix expression :");
scanf("%s", exp);
convert(exp);
printf("\nThe Equivalant Infix expression is:");
display(pop());


}


#include <stdio.h>
#include <stdlib.h>
int top = 10;
struct node
{
char ch;
struct node *next;
struct node *prev;
} *stack[11];
typedef struct node node;

void push(node *str)
{
if (top <= 0)
printf("Stack is Full ");
else
{
stack[top] = str;
top--;
}
}

node *pop()
{
node *exp;
if (top >= 10)
printf("Stack is Empty ");
else
exp = stack[++top];
return exp;
}
void convert(char exp[])
{
node *op1, *op2;
node *temp;
int i;
for (i=0;exp[i]!='\0';i++)
if (exp[i] >= 'a'&& exp[i] <= 'z'|| exp[i] >= 'A' && exp[i] <= 'Z')
{
temp = (node*)malloc(sizeof(node));
temp->ch = exp[i];
temp->next = NULL;
temp->prev = NULL;
push(temp);
}
else if (exp[i] == '+' || exp[i] == '-' || exp[i] == '*' || exp[i] == '/' ||
exp[i] == '^')
{
op1 = pop();
op2 = pop();
temp = (node*)malloc(sizeof(node));
temp->ch = exp[i];
temp->next = op1;
temp->prev = op2;
push(temp);
}
}

void display(node *temp)
{
if (temp != NULL)
{
display(temp->prev);
printf("%c", temp->ch);
display(temp->next);
}
}

void main()
{
char exp[50];
clrscr();
printf("Enter the postfix expression :");
scanf("%s", exp);
convert(exp);
printf("\nThe Equivalant Infix expression is:");
display(pop());


}

Steps to convert Prefix expression to Infix
1.Scan the prefix expression from right to left.
2.If the scanned character is an operand, then push it into the stack
3.If the scanned character is an operator, pop two elements from the top of the stack and print them in the following format operand1 + operator + operand2
4.Repeat the steps ii) and iii) until the entire expression is scanned.

C Code
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <conio.h>
char opnds[50][80],oprs[50];
int topr=-1,topd=-1;
pushd(char *opnd)
{
strcpy(opnds[++topd],opnd);
}
char *popd()
{
return(opnds[topd--]);
}

pushr(char opr)
{
oprs[++topr]=opr;
}
char popr()
{
return(oprs[topr--]);
}
int empty(int t)
{
if( t == 0) return(1);
return(0);
}

void main()
{
char prfx[50],ch,str[50],opnd1[50],opnd2[50],opr[2];
int i=0,k=0,opndcnt=0;

printf("Give an Expression = ");
gets(prfx);
printf(" Given Prefix Expression : %s\n",prfx);
while( (ch=prfx[i++]) != '\0')
{
if(isalnum(ch))
{
str[0]=ch; str[1]='\0';
pushd(str); opndcnt++;
if(opndcnt >= 2)
{
strcpy(opnd2,popd());
strcpy(opnd1,popd());
strcpy(str,"(");
strcat(str,opnd1);
ch=popr();
opr[0]=ch;opr[1]='\0';
strcat(str,opr);
strcat(str,opnd2);
strcat(str,")");
pushd(str);
opndcnt-=1;
}
}
else
{
pushr(ch);
if(opndcnt==1)opndcnt=0; /* operator followed by single operand*/
}
}
if(!empty(topd))
{
strcpy(opnd2,popd());
strcpy(opnd1,popd());
strcpy(str,"(");
strcat(str,opnd1);
ch=popr();
opr[0]=ch;opr[1]='\0';
strcat(str,opr);
strcat(str,opnd2);
strcat(str,")");
pushd(str);
}
printf(" Infix Expression: ");
puts(opnds[topd]);
getch();
}

Steps to convert Prefix expression to postfix
1.Scan the prefix expression from right to left.
2.If the scanned character is an operand, then push it into the stack
3.If the scanned character is an operator, pop two elements from the top of the stack and print them in the following format operand1 + operand2 + operand2
4.Repeat the steps ii) and iii) until the entire expression is scanned.


C Code
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>

#define BLANK ' '
#define TAB '\t'
#define MAX 50

char *pop();
char prefix[MAX];
char stack[MAX][MAX];
void push(char *str);
int isempty();
int white_space(char symbol);
void prefix_to_postfix();
int top;

int main()
{
top = -1;
printf("Enter Prefix Expression : ");
gets(prefix);
prefix_to_postfix();

}/*End of main()*/

void prefix_to_postfix()
{
int i;
char operand1[MAX], operand2[MAX];
char symbol;
char temp[2];
char strin[MAX];
for(i=strlen(prefix)-1;i>=0;i--)
{
symbol=prefix[i];
temp[0]=symbol;
temp[1]='\0';

if(!white_space(symbol))
{
switch(symbol)
{
case '+':
case '-':
case '*':
case '/':
case '%':
case '^':
strcpy(operand1,pop());
strcpy(operand2,pop());
strcpy(strin,operand1);
strcat(strin,operand2);
strcat(strin,temp);
push(strin);
break;
default: /*if an operand comes*/
push(temp);
}
}
}
printf("\nPostfix Expression :: ");
puts(stack[0]);
}/*End of prefix_to_postfix()*/


void push(char *str)
{
if(top > MAX)
{
printf("\nStack overflow\n");
exit(1);
}
else
{
top=top+1;
strcpy( stack[top], str);
}
}/*End of push()*/

char *pop()
{
if(top == -1 )
{
printf("\nStack underflow \n");
exit(2);
}
else
return (stack[top--]);
}/*End of pop()*/
int isempty()
{
if(top==-1)
return 1;
else
return 0;
}
int white_space(char symbol)
{
if(symbol==BLANK || symbol==TAB || symbol=='\0')
return 1;
else
return 0;
}

Evaluating postfix expression using stack
1.Scan all the characters in the postfix expression from left to right.
2.If the character is an operand, push it into the stack
3.Else, pop two operands from the stack and perform the corresponding operation on the popped elements. Then, push the result into the stack.
4.Repeat the above two steps until the expression is processed completely.
5.The remaining element in the stack is the result.

Evaluating prefix expression using stack
1.Reverse the prefix expression
2.Now, evaluate the resulting postfix expression using the above mentioned method.

Void traverse_stack()
{
int i;
printf(“The elements in the stack are:\n”);
for(i=top;i>0;i--)
{
Printf(“%d ”, stack[top]);
}
The above function traverses all the elements of the stack, until ‘top’ becomes zero. top==0 indicates that the stack is empty.

PUSH : time complexity is O(1)
POP : time complexity is O(1)
TRAVERSE : time complexity is O(n), where n is the number of elements in the stack. The traverse operation has a linear time complexity, because all the elements in the stacks are processed one by one to give the output.