Application of stacks :-
The linear data structure stack can be used in the following situations.
1. It can be used to process function calls.
2. Implementing recursive functions in high level languages
3. Converting and evaluating expressions.
Function calls:
A stack is useful for the compiler/operating system to store local variables used inside a function block, so that they can be discarded once the control comes out of the function block.
Recursive functions:
The stack is very much useful while implementing recursive functions. The return values and addresses of the function will be pushed into the stack and the lastly invoked function will first return the value by popping the stack.
Representation of expressions :-
In general there are 3 kinds of expressions available depending on the placement of the operators & operands.
1) Infix expression :- It is the general notation used for representing expressions.
“In this expression the operator is fixed in between the operands”
Ex: a + bc
2) Post fix expression :- (Reverse polish notation)
“In this expression the operator is placed after the operands”.
Ex : abc+
3) Prefix expression :- (Polish notation)
“In this expression the operators are followed by operands i.e the operators are fixed before the operands”
Ex : +abc
All the infix expression will be converted into post fix notation with the help of stack in any program
The stack will be useful in evaluating the postfix expressions also.
Algorithm for evaluating post fix expression using stacks :-
step :- 1 start
step :- 2 for(each character ch in the postfix expression)
step :- 3 If operand is found push it into the stack
step :- 4 else
step :- 5 If operator is found then pop the stack 2 times
OP2 = pop ( ) OP1 = pop ( )
step :- 6 Perform the specified operation as result = OP1 operator OP2
step :- 7 Push the intermediate result back into the stack
step :- 8 Repeat the above steps until the end of the expression
step :- 9 pop the stack to obtain the final result
step :- 10 stop
Algorithm to convert infix to post fix expression: -
– assumptions
§ Operands are single lowercase letters that represent integer values
§ Stack is a stack data structure
§ Precedence is the function to get the precedence of an operator
Steps
- for (each character ch in the infix expression) {
- switch (ch) {
i. case operand: // append operand to end of PE
postfixExp = postfixExp + ch; break
ii. case '(':
a Stack.push(ch) break
iii. case ')':
1. while (top of stack is not '(')
a. postfixExp = postfixExp + (Stack.pop())
2. Stack.pop() // remove the open parenthesis
3. break
iv. case operator:
1. while (!Stack.isEmpty and top of stack is not '(' and precendence(ch) <= precendence(top of aStack))
a. postfixExp = postfixExp + (Stack.pop())
2. Stack.push(ch) // save new operator
3. break
- }
- }
- // append to postfixExp the operators remaining in the stack
- while (!Stack.isEmpty())
- postfixExp = postfixExp + (Stack.pop())
Fox example the following figure shows how to convert the infix expression a - (b + c * d)/e to postfix form
