Applications of Stack in Data Structure:
In this article, we will understand the Applications of Stack in the data structure.
What do you mean by Stack?
A Stack is a widely used linear data structure in modern computers in which insertions and deletions of an element can occur only at one end, i.e., top of the Stack. It is used in all those applications in which data must be stored and retrieved in the last.
An everyday analogy of a stack data structure is a stack of books on a desk, Stack of plates, table tennis, Stack of bootless, Undo or Redo mechanism in the Text Editors, etc.
Following is the various Applications of Stack in Data Structure:
- Evaluation of Arithmetic Expressions
- Backtracking
- Delimiter Checking
- Reverse a Data
- Processing Function Calls
1. Evaluation of Arithmetic Expressions
A stack is a very effective data structure for evaluating arithmetic expressions in programming languages. An arithmetic expression consists of operands and operators.
In addition to operands and operators, the arithmetic expression may also include parenthesis like “left parenthesis” and “right parenthesis”.
Example: A + (B – C)
To evaluate the expressions, one needs to be aware of the standard precedence rules for arithmetic expression. The precedence rules for the five basic arithmetic operators are:
Operators | Associativity | Precedence |
---|---|---|
^ exponentiation | Right to left | Highest followed by *Multiplication and /division |
*Multiplication, /division | Left to right | Highest followed by + addition and – subtraction |
+ addition, – subtraction | Left to right | lowest |
Evaluation of Arithmetic Expression requires two steps:
- First, convert the given expression into special notation.
- Evaluate the expression in this new notation.
Notations for Arithmetic Expression
There are three notations to represent an arithmetic expression:
- Infix Notation
- Prefix Notation
- Postfix Notation
Infix Notation
The infix notation is a convenient way of writing an expression in which each operator is placed between the operands. Infix expressions can be parenthesized or unparenthesized depending upon the problem requirement.
Example: A + B, (C – D) etc.
All these expressions are in infix notation because the operator comes between the operands.
Prefix Notation
The prefix notation places the operator before the operands. This notation was introduced by the Polish mathematician and hence often referred to as polish notation.
Example: + A B, -CD etc.
All these expressions are in prefix notation because the operator comes before the operands.
Postfix Notation
The postfix notation places the operator after the operands. This notation is just the reverse of Polish notation and also known as Reverse Polish notation.
Example: AB +, CD+, etc.
All these expressions are in postfix notation because the operator comes after the operands.
Conversion of Arithmetic Expression into various Notations:
Infix Notation | Prefix Notation | Postfix Notation |
---|---|---|
A * B | * A B | AB* |
(A+B)/C | /+ ABC | AB+C/ |
(A*B) + (D-C) | +*AB – DC | AB*DC-+ |
Let’s take the example of Converting an infix expression into a postfix expression.
In the above example, the only change from the postfix expression is that the operator is placed before the operands rather than between the operands.
Evaluating Postfix expression:
Stack is the ideal data structure to evaluate the postfix expression because the top element is always the most recent operand. The next element on the Stack is the second most recent operand to be operated on.
Before evaluating the postfix expression, the following conditions must be checked. If any one of the conditions fails, the postfix expression is invalid.
- When an operator encounters the scanning process, the Stack must contain a pair of operands or intermediate results previously calculated.
- When an expression has been completely evaluated, the Stack must contain exactly one value.
Example:
Now let us consider the following infix expression 2 * (4+3) – 5.
Its equivalent postfix expression is 2 4 3 + * 5.
The following step illustrates how this postfix expression is evaluated.
2. Backtracking
Backtracking is another application of Stack. It is a recursive algorithm that is used for solving the optimization problem.
3. Delimiter Checking
The common application of Stack is delimiter checking, i.e., parsing that involves analyzing a source program syntactically. It is also called parenthesis checking. When the compiler translates a source program written in some programming language such as C, C++ to a machine language, it parses the program into multiple individual parts such as variable names, keywords, etc. By scanning from left to right. The main problem encountered while translating is the unmatched delimiters. We make use of different types of delimiters include the parenthesis checking (,), curly braces {,} and square brackets [,], and common delimiters /* and */. Every opening delimiter must match a closing delimiter, i.e., every opening parenthesis should be followed by a matching closing parenthesis. Also, the delimiter can be nested. The opening delimiter that occurs later in the source program should be closed before those occurring earlier.
Valid Delimiter | Invalid Delimiter |
---|---|
While ( i > 0) | While ( i > |
/* Data Structure */ | /* Data Structure |
{ ( a + b) – c } | { ( a + b) – c |