Stacks are used in applications such as converting expression from infix notations to postfix notations and many others. Stacks are also used in games like towers of Hanoi problem.

1. Infix Expression, where operator is placed between the operands.

Algorithm for converting Infix to Postfix.

a. Add a right parenthesis ‘)’ at the end of P.

b. Scan P from left to right and repeat steps 3 & 4 for each element P until the ‘)’ is encountered.

c. If an operand is encountered, put it on STACK.

d. If an operator * is encountered, then:

i) Remove the two top elements of STACK, where A is the top element and B is next-to top element.

ii) Evaluate B * B

iii) Place theresult of (b) back on STACK.

e. Set VALUE equal to the top element on STACK.

f. Return

Algorithm for converting Infix to Postfix.

a. Push “(“ into STACK and add “)” to the end of the Q.

b. Scan Q from left to right and repeat steps 3 to 6 for each element of Q until the STACK is empty.

c. If an operand is encountered, add it to P.

d. If a left parenthesis is encountered, push it on to STACK.

e. If an operator * is encountered, then

i. Repeatedly pop from STACK and add to P each operator which has the same precedence as or higher precedence than *

ii. Add * to STACK.

f. If right parenthesis is encountered, then

i. Repeatedly pop from STACK and add to P each operator until a left parenthesis is encountered.

ii. Remove the left parenthesis.

g. return

2. Prefix Expression, where operator is placed before the operands.

3. Postfix Expression, where operator is placed after the operands.

Questions:

1. Calculate Infix, Prefix, and Postfix Expression.

2. Conversion of Infix, prefix and postfix Notation.

Rules to be remember during infix to postfix conversion:

a) Parenthesize the expression starting from left to right.

b) Operator with higher precedence is evaluates first.

c) The sub-expression (part of expression) which has been converted into postfix is to be treated as single operand.

d) Once the expression is converted into postfix form, then remove the parenthesis.

Example: convertA+ [{(B+C) + (D+E)*F}/G]

Sol: A+ [{(BC+) + (DE+)*F}/G]

A+ [{BC+DE+F*+}/G]

A+ [BC+DE+F*+G/]

ABC+DE+F*+G/+

Malloc is a keyword which initialize the memory space for the inputted pointer type of variable it only takes the assign space from the memory which is reserve for keywords or any initialized value.

Calloc it works same as malloc keyword accept the memory allocation, it requires the two. parameter first the value and second for the size.

Arrays have some disadvantages like:

1. Wastage of memory, because total space allocated must be known in advance, otherwise enough space can be wasted.

2. Some operations like Insertion and Deletions require extra time, because insertion and deletion requires enough shifting of elements.Due to these disadvantages we use dynamic memory allocation i.e., using Linked List.