Applications of stack

The stack data structure is used in a wide range of applications such as

1. Converting infix expression to postfix and prefix expressions

2. Evaluating the postfix expression

3. Checking well-formed (nested) parenthesis

4. Reversing a string

5. Processing function calls

6. Parsing (analyse the structure) of computer programs

7. Simulating recursion

8. In computations such as decimal to binary conversion

9. In backtracking algorithms (often used in optimizations and in games)

1. EXPRESSION EVALUATI ON AND CONVERSION

The most frequent application of stacks is in the evaluation of arithmetic expressions. An arithmetic expression is made of operands, operators, and delimiters.

Operator Precedence:

1. Exponentiation (^), Unary (+), Unary (-), and not (~)

2. Multiplication (\) and division (/)

3. Addition (+) and subtraction (-)

4. Relational operators  (<, <= , =,  ≥, >)

5. Logical AND

6. Logical OR

The order of evaluation, from left to right or right to left, is called associativity. Exponentiation is right associative and all other operators are left associative. In the parenthesized expressions, the innermost parenthesized expression is evaluated first.

Let us consider the expression

X = A/B ^ C + D X E - A X C

By using priorities and associativity rules, the expression X is rewritten as

X = A/(B ^ C) + (D X E) - (A X C)

The Polish Mathematician Han Lukasiewicz suggested a notation called Polish notation, which gives two alternatives to represent an arithmetic expression, namely the postfix and prefix notations.

The advantage is that a parenthesis is not required while writing expressions in Polish notation. The order in which the operations are to be performed is determined by the positions of the operators and operands in the expression.

The conventional way of writing the expression is called infix, because the binary operators occur between the operands, and unary operators precede their operand.

For example, the expression ((A + B) X C)/D is an infix expression. In postfix notation, the operator is written after its operands, whereas in prefix notation, the operator precedes its operands.

The postfix and prefix expressions possess many advantages as follows:

1. The need for parenthesis as in an infix expression is overcome in postfix and prefix notations.

2. The priority of operators is no longer relevant.

3. The order of evaluation depends on the position of the operator but not on priority and associativity.

4. The expression evaluation process is much simpler than attempting a direct evaluation from the infix notation.

Postfix Expression Evaluation

The postfix expression may be evaluated by making a left-to-right scan, stacking operands, and evaluating operators using the correct number from the stack as operands and again placing the result onto the stack. This process continues till the stack is not empty or on occurrence of the character #, which denotes the end of the expression.

Algorithm for evaluation of postfix expression

1. Let E denote the postfix expression

2. Let Stack denote the stack data structure to be used & let Top = −1

3. while(1) do

begin

X = get_next_token(E) // Token is an operator, operand, or delimiter

if(X = #) {end of expression}

then return

if(X is an operand)

then push(X) onto Stack

else {X is operator}

begin

OP1 = pop() from Stack

OP2 = pop() from Stack

Tmp = evaluate(OP1, X, OP2)

push(Tmp) on Stack

end

end

4. stop

Example:

Let us consider an example postfix expression E = AB + C X#.

Scan this expression from left to right, character by character. The following push and pop operations are performed using stack to evaluate the given postfix expression.

An expression in one form can be converted to the other two forms.

1. Infix expression to postfix expression

2. Infix expression to prefix expression

3. Prefix expression to infix expression

4. Prefix expression to postfix expression

5. Postfix expression to infix expression

6. Postfix expression to prefix expression

II. Processing of function calls

One natural application of stacks in computer programming is the processing of function calls and their terminations.

The program must remember the place where the call was made so that it can return there after the function is complete.

For example let ABC, PQR, XYZ are three functions along with one main function. The main function invokes ABC, ABC invoke PQR, and PQR in turn invoke XYZ.

main function is the first to start work, but it is the last to be finished. 

Use of stack for processing of function calls

III. Reversing a String with a Stack

The LIFO (Last In First Out) property of the stack access guarantees the reversal.

Suppose the sequence ABCDEF is to be reversed. With a stack, simply scan the sequence, pushing each element onto the stack until the end of the sequence is reached.

Then stack is popped repeatedly, with each popped element sent to the output, until the stack is empty