Application of Stack

Application of Stack
1. Converting an Expression from Infix to Postfix
One application of stack data structure is converting the infix expression to postfix expression.
we have three way to write the arithmetic expression:-
1- Infix expression : the operators appeared within the operands as:
A+(B/C) .
2- Postfix expression : the operators appeared after the operands as:
X Y / , 3 5+.
3- Prefix expression : the operators appeared before the operands as:
/ X Y , * 6 7.
Why to use these weird looking PREFIX and POSTFIX notations when we have simple INFIX notation?. To our surprise INFIX notations are not as simple as they seem specially while evaluating them. To evaluate an infix expression we need to consider Operators’ Priority and Associative property.
For example expression 3+5*4 evaluate to 32 i.e. (3+5)*4 or to 23 i.e. 3+(5*4).
There are no precedence rules to learn, and parentheses are never needed in postfix expression this is why to convert infix to postfix.
In program to convert any expression from infix expression to postfix one, we will use a stack which may contain: arithmetic operators, parentheses and a spatial delimiter "#". The following steps defines that conversion :
Define the infix priority, which takes an operators, parenthesis or # as:
Input Character priority
( 5
^ , (-), (+) , Not 4
*, / ,AND , DIV, MOD 3
+ , - , OR 2
= , < , > , < > , <=,>= 1
# 0

2- Define stack priority, which takes the same possibility of the infix priority except the left parentheses ( will have 0 priority.
3- Push # onto stack as first entry.
4- Read the next character from the infix expression.
5- Test the character.
- If the character is an operand, add it to the postfix string.
- If the character is a right parenthesis then pop entries from the stack add them to the postfix string until a left parenthesis is poped. Discovered both left and right parenthesis.
- If the character is a #, pop all entries that remain in the stack add them to postfix string.
- Otherwise, pop from the stack and add to postfix the operator that have stack priority greater than or equal to the infix priority of the read character, then push the read character to the stack.
These steps summarized in the following algorithm:
Algorithm : Converting Infix expression to Postfix expression
Inputs: Infix (Infix expression as string)
Outputs: Post ( Post expression as string)
Begin
- Initialized stack with # character , Top=0 and post =""
- Ch = Read the first char in Infix
- While (Ch < > # )
If ( Operand( Ch)) then
Add Ch to post string
else if ( Ch = ) )
while the top element of stack < > ( do
n= pop(stack, top)
add n to post string
end while
n=pop(stack, top)
else
while PriStack(stack[top] >= PriInfix(Ch) do
n=pop(stack, top)
add n to post string
end while
push (stack, top, Ch)
end if
Ch = next character of Infix
End while
If ( Ch = # )
While stack[top] < > # do
N=pop(stack, top)
Add n to post string
Else write " Invalid String"
Return post
End
The converting algorithm need to some functions, such as:
Operand (Ch) function
Test if Ch is operand or not. The operand contains the digits and letters. For simplicity, in our program the operands contain the small letters only.
PriInfix (Ch) function
Return the priority of Ch in Infix priority table. In C++ will use case switch to handles this table such as:
Switch (Ch)
{Case × : return (3);
Case / : return (3);
.
.
Default: cout <<"illegal operation";
Exit (1);
}
priStack (stack[top]) function
return the priority of the top element of stack in stack priority table. Used switch to represent that table.



Example 1 :- Convert the following infix expression to postfix: A + (B /C)#.
Infix Stack Postfix
#
A # A
+ # + A
( #+( A
B #+( AB
/ #+( / AB
C #+( / ABC
) #+ ABC/
# # ABC/+

Example 2 :- Convert the following infix expression to postfix a+b*c+d*e#
input stack postfix
#
a # a
+ #,+ a
b #,+ ab
* #,+,* ab
c #,+,* abc
+ #,+ abc*+
d #,+ abc*+d
* #,+,* abc*+d
e #,+,* abc*+de
# # abc*+de*+
Example 3:- Convert the following infix expression to postfix
(( A – ( B + C)) * D) / (E +F) #
Infix Stack Postfix
#
( #(
( #((
A #(( A
- #((- A
( #((-( A
B #((-( AB
+ #((-(+ AB
C #((-(+ ABC
) #((- ABC+
) #( ABC+-
* #(* ABC+-
D #(* ABC+-D
) # ABC+-D*
/ #/ ABC+-D*
( #/( ABC+-D*
E #/( ABC+-D*E
+ #/(+ ABC+-D*E
F #/(+ ABC+-D*EF
) #/ ABC+-D*EF+
# # ABC+-D*EF+/

Example 4:- Convert the following infix expression to postfix (a+b^c^d)*(e+f/d)#
input stack postfix
#
( #,(
a #,( a
+ #,(,+ a
b #,(,+ ab
^ #,(,+,^ ab
c #,(,+,^ abc
^ #,(,+,^ abc^
d #,(,+,^ abc^d
) # abc^d^+
* #,* abc^d^+
( #,*,( abc^d^+
e #,*,( abc^d^+e
+ #,*,(,+ abc^d^+e
f #,*,(,+ abc^d^+ef
/ #,*,(,+,/ abc^d^+ef
d #,*,(,+,/ abc^d^+efd
) #,* abc^d^+efd/+
# abc^d^+efd/+*




Q:- Convert the infix to postfix:-
1) (m+k) / 3 + ( l / 4 ) #.
2) a - b / ( c * d ^ e) #.
3) (a+b) *(c*d-e)*f / g#.
2. Recursion
A Recursion function is one that calls itself. This powerful technique
produces repetition without using loops(e.g., while or for).Thus it can produce substantial results from very little code. Recursion allows elegantly simple solutions to difficult problems. But it can also be misused, producing inefficient code. Recursive code is usually produced from recursive algorithms.
Recursion involves the internal use of a stack. The recursive calls of a method will be stored on a stack, and manipulated in a similar manner.
Basis and Recursive Parts
To work correctly, every recursive function must have a basis and a recursive part. The basis is what stops the recursion. The recursive part is where the function calls itself.
Simple Recursion Functions
1. The factorial function is defined mathematically by


Recursive implementation of the Factorial function:-
int fact (int n)
{ if (n==0)
return 1 ; // basis
else
return n*fact(n-1); // recursive part
}
2. The power function is defined mathematically by
= {?(1 if n=0@x*f(x^(n-1) ) if n>0)?
Recursive implementation of the x^n :-
int pow (int x, int n)
{ if ( n==0)
return 1 ; // basis
else
return x* pow(x,n-1) ; // recursive part
}
3. The Fibonacci numbers :- The Fibonacci numbers are 0,1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ....... . Each number after the second is the sum of the two preceding numbers. This is a naturally recursive definition:
={?(0, if n=0@1, if n=1@F_(n-1)+F_(n-2) ,if n>1)?
Recursive implementation of the Fibonacci numbers :-
int fibo (int n)
{ if (n < 2)
return n; // basis
else
return fibo(n-1) + fibo(n-2); // recursive part
}