Applications of Stack

Applications of Stack:

• Application means a real problem of life where stack data structure may apply to resolve that problem.

1. Polish notation:
A. Expression Conversion

B. Expression Evaluation

OR

2. Recursion function

3. String Reverse

4. Tower of Hanoi

1. Polish notation

• It is a process of writing for expression.
• It is founded by
• polish mathematician Mr. Jan.
• An expression is a compound form of operand and operator.
• Example: A + B
• Here, + is an operator and A and B are operands.
• 
  
• The polish notation are classified into:

1. Infix
2. Prefix
3. Postfix

1. Infix notation:

• An expression is called the Infix expression if the operator appears in between the operands in the expression.
• Syntax: operand1 operator operand2
• Example: A+B

2. Prefix notation:

• An expression is called the prefix expression if the operator appears in the expression before the operands.
• Syntax: operator operand1 operand2
• Example: +AB

3. Postfix notation:

• An expression is called the postfix expression if the operator appears in the expression after the operands.
• Syntax: operand1 operand2 operator
• Example: AB+

A. Expression Conversion

• Conversion means a process of convert one notation to another notation.
  
• There are following types of conversion.
• 1. Infix to Prefix (A+B, +AB)
• 2. Infix to Postfix (A+B, AB+)
• 3. Prefix to Infix (+AB, A+B)
• 4. Prefix to Postfix (+AB, AB+)
• 5. Postfix to Infix (AB+, A+B)
• 6. Postfix to Prefix (AB+, +AB)

• The stack can be used to convert some infix expression into its postfix equivalent, or prefix equivalent.

• 1. Infix to Prefix
• Infix Example : (A+B) * (C-D)
• Example: *+AB-CD
• 4. Prefix to Postfix
• Example: *+AB-CD
• Example: AB+CD-*
• 5. Postfix to Infix
• Example: AB*C+
• Example: ((A * B) + C))
• 6. Postfix to Prefix
• Example: AB+CD-*
• Example: *+AB-CD

B. Expression Evaluation

• Example:
  
• Example: abc*+d-
• suppose, a=4, b=3, c=2 and d=5
• Now, final expression as 4 3 2 * + 5 -
• In stack,
• Label Stack Value
• 4 push 4 4
• 3 push 3 4 3
• 2 push 2 4 3 2
• * pop (3*2) 4 6
• + pop (4+6) 10
• 5 push 5 10 5
• - pop (10-5) 5