Applications of Stack
Expression conversion (Infix, Postfix, Prefix)
Expression evaluation
Balancing the symbols
Towers of Hanoi
Decimal to binary conversion
Reversing a string
Expressions
Expression is a string of operands and operators.
Operands are some numeric values and
operators are of 2 types.
1. Unary operators
2. Binary operators
There are three types of expressions
1. Infix Expression
2. Postfix Expression
3. Prefix Expression
Infix Expression
Infix Expression = Operand1 Operator Operand2
Example:
1. ( a + b )
2. ( a + b ) * ( c – d )
3. ( a + b / e ) * ( d + f )
• Parenthesis can be used in these expressions,
infix expression are the most natural way of
representing the expressions.
Postfix Expression
Postfix Expression = Operand1 Operand2 Operator
Example:
1. a b +
2. a b + c d - *
3. a b + e / d f + *
• In Postfix expression there is no parenthesis used. All
the corresponding operands come first and then
operator can be placed.
Prefix Expression
Prefix Expression = Operator Operand1 Operand2
Example:
1. + a b
2. * + a b - c d
3. * / + a b e + d f
• In Prefix expression there is no parenthesis used.
All the corresponding operators come first and then
operands are arranged.
Precedence
Operator Precedence Precedence in
in stack
expression
^ 3 4
* / 2 2
+ - 1 1
( 0 4
Infix to postfix conversion
1. Read the Infix expression from left to right
2. If the input symbol read is '(' then push it onto the stack.
3. If the input symbol read is an operand then place it in postfix
expression.
4. If input symbol read is an operator then
a) Check if the precedence of the operator which is in the stack has
greater precedence than the precedence of the operator read, if so
then remove that symbol from stack and place it in postfix
expression. Repeat the step (4 a) till you get the operator in the
stack has lesser precedence than the operator being read.
b) Otherwise push the operator being read onto the stack
5. If the input symbol read is a closing parenthesis ')' then pop all the
operators from the stack, place them in postfix expression till the
opening parenthesis is not popped. The '(' should not be place in
the postfix expression.
6. Finally print the postfix expression.
Infix to postfix conversion
Stack
Infix Expression
( a + b - c ) * d – ( e + f )$
Postfix Expression
Infix to postfix conversion
Stack
Infix Expression
a + b - c ) * d – ( e + f )$
Postfix Expression
(
Infix to postfix conversion
Stack
Infix Expression
+ b - c ) * d – ( e + f )$
Postfix Expression
a
(
Infix to postfix conversion
Stack
Infix Expression
b - c ) * d – ( e + f )$
Postfix Expression
a
+
(
Infix to postfix conversion
Stack
Infix Expression
- c ) * d – ( e + f )$
Postfix Expression
ab
+
(
Infix to postfix conversion
Stack
Infix Expression
c ) * d – ( e + f )$
Postfix Expression
ab+
-
(
Infix to postfix conversion
Stack
Infix Expression
) * d – ( e + f )$
Postfix Expression
ab+c
-
(
Infix to postfix conversion
Stack
Infix Expression
* d – ( e + f )$
Postfix Expression
ab+c-
Infix to postfix conversion
Stack
Infix Expression
d – ( e + f )$
Postfix Expression
ab+c-
*
Infix to postfix conversion
Stack
Infix Expression
– ( e + f )$
Postfix Expression
ab+c-d
*
Infix to postfix conversion
Stack
Infix Expression
( e + f )$
Postfix Expression
ab+c–d*
-
Infix to postfix conversion
Stack
Infix Expression
e + f )$
Postfix Expression
ab+c–d*
(
-
Infix to postfix conversion
Stack
Infix Expression
+ f )$
Postfix Expression
ab+c–d*e
(
-
Infix to postfix conversion
Stack
Infix Expression
f )$
Postfix Expression
+ ab+c–d*e
(
-
Infix to postfix conversion
Stack
Infix Expression
)$
Postfix Expression
+ ab+c–d*ef
(
-
Infix to postfix conversion
Stack
Infix Expression
$
Postfix Expression
ab+c–d*ef+
-
Infix to postfix conversion
Stack
Infix Expression
Postfix Expression
ab+c–d*ef+-
Infix to postfix conversion
Stack
Infix Expression
( a + b * c ) + d – ( e + f )$
Postfix Expression
Infix to postfix conversion
Stack
Infix Expression
a + b * c ) + d – ( e + f )$
Postfix Expression
(
Infix to postfix conversion
Stack
Infix Expression
+ b * c ) + d – ( e + f )$
Postfix Expression
a
(
Infix to postfix conversion
Stack
Infix Expression
b * c ) + d – ( e + f )$
Postfix Expression
a
+
(
Infix to postfix conversion
Stack
Infix Expression
* c ) + d – ( e + f )$
Postfix Expression
ab
+
(
Infix to postfix conversion
Stack
Infix Expression
c ) + d – ( e + f )$
Postfix Expression
* ab
+
(
Infix to postfix conversion
Stack
Infix Expression
) + d – ( e + f )$
Postfix Expression
* abc
+
(
Infix to postfix conversion
Stack
Infix Expression
+ d – ( e + f )$
Postfix Expression
abc*+
Infix to postfix conversion
Stack
Infix Expression
d – ( e + f )$
Postfix Expression
ab+c-
+
Infix to postfix conversion
Stack
Infix Expression
– ( e + f )$
Postfix Expression
ab+c-d
+
Infix to postfix conversion
Stack
Infix Expression
( e + f )$
Postfix Expression
ab+c–d+
-
Infix to postfix conversion
Stack
Infix Expression
e + f )$
Postfix Expression
ab+c–d+
(
-
Infix to postfix conversion
Stack
Infix Expression
+ f )$
Postfix Expression
ab+c–d+e
(
-
Infix to postfix conversion
Stack
Infix Expression
f )$
Postfix Expression
+ ab+c–d+e
(
-
Infix to postfix conversion
Stack
Infix Expression
)$
Postfix Expression
+ ab+c–d+ef
(
-
Infix to postfix conversion
Stack
Infix Expression
$
Postfix Expression
ab+c–d*ef+
-
Infix to postfix conversion
Stack
Infix Expression
Postfix Expression
ab+c–d*ef+-
#include<stdio.h>
#include<stdlib.h>
#define STACKSIZE 20
typedef struct{
int top;
char items[STACKSIZE];
}STACK;
void push(STACK *, char);
char pop(STACK *);
void main()
{
int i;
char x,y, E[20] ; /* Assume that Infix Expression E contains single-digit
integers/parenthesis/operators*/
STACK s;
s.top = -1; /* Initialize the stack is */
printf("Enter the Infix Expression:");
scanf("%s",E);
for(i=0;E[i] != '\0';i++){
x= E[i];
if(x<=’z’ && x>=’a’) /* Consider all lowercase letter operands from a to z */
printf(“%c”,x);
else if(x == ’(’)
push(&s ,x);
else if(x == ’)’){
y=pop(&s) ;
while(y != ‘(‘){
printf(“%c”,y);
y=pop(&s) ;
}
}
else {
if(s.top ==-1 || s.items[s.top] == ‘(‘)
push(&s ,x);
else {
y = s.items[s.top]; /* y is the top operator in the stack*/
if( y==’*’ || y==’/’){ /* precedence of y is higher/equal to x*/
printf(“%c”, pop(&s));
push(&s ,x);
}
else if ( y==’+’ || y==’-’)
if( x==’+’ || x==’-’) { /* precedence of y is equal to x*/
printf(“%c”, pop(&s));
push(&s ,x);
}
else /* precedence of y is less than x*/
push(&s ,x);
}
}
}
while(s.top != -1)
printf(“%c”,pop(&s));
}
void push(STACK *sptr, char ps) /*pushes ps into stack*/
{
if(sptr->top == STACKSIZE-1){
printf("Stack is full\n");
exit(1); /*exit from the function*/
}
else
sptr->items[++sptr->top]= ps;
}
char pop(STACK *sptr)
{
if(sptr->top == -1){
printf("Stack is empty\n");
exit(1); /*exit from the function*/
}
else
return sptr->items[sptr->top--];
}
