Applications of Stack Data Structure

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

1. for (each character ch in the infix expression) {
2. 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

3. }
4. }
5. // append to postfixExp the operators remaining in the stack
6. while (!Stack.isEmpty())
7. postfixExp = postfixExp + (Stack.pop())

Fox example the following figure shows how to convert the infix expression a - (b + c * d)/e to postfix form