STACK ADT:

Stack ADT is an abstract data type that usually holds a collection of data and enables to perform certain operations on it in a particular order is called LIFO (Last In First Out), which means that the last element that is put into the collection will be the first element to get out.

APPLICATION OF STACK ADT:

Every single software engineer must understand the stacks has many applications starting from memory management to real life and it is a fundamental (and simple) data structure. Generally, one of the applications of Stack is in the conversion of arithmetic expressions in high-level programming languages into machine-readable form.

As our computer system can only understand and work on a binary language, it assumes that an arithmetic operation can take place in two operands only e.g., A+B, C*D, D/A, etc. But in our usual form, an arithmetic expression may consist of more than one operator and two operands e.g. (A+B)*C(D/(J+D)).

Meanwhile,we need to know about the two expressions which occur in the evaluation process of the calculator:

• INFIX EXPRESSION:

It follows the scheme of <operand><operator><operand>. Such an expression is termed infix expression. E.g., A+B

• POSTFIX EXPRESSION:

It follows the scheme of <operand><operand><operator>.
E.g., AB+

STACK ADT HELPS IN EVALUATION:

• INFIX TO POSTFIX CONVERSION ALGORITHM:
• Push “(“onto Stack, and add “)” to the end of X.
• Scan X from left to right and repeat Steps 3 to 6 for each element of X until the Stack is empty.
• If an operand is encountered, add it to Y.
• If a left parenthesis is encountered, push it onto Stack.
• If an operator is encountered, then:
  1. Repeatedly pop from Stack and add to Y each operator (on the top of Stack) which has the same precedence as or higher precedence than the operator.
  1. Add operator to Stack.
  1. [End of If]
• If a right parenthesis is encountered, then:
  1. Repeatedly pop from Stack and add to Y each operator (on the top of Stack) until a left parenthesis is encountered.
  1. Remove the left Parenthesis.
  1. [End of If]
• .END

Let’s take an example to better understand the algorithm

Infix Expression: A+ (B*C-(D/E^F)*G)*H, where ^ is an exponential operator.

1. POSTFIX TO INFIX CONVERSION ALGORITHM:

1) Add ) to postfix expression.

2) Read postfix expression Left to Right until ) encountered

3) If the operand is encountered, push it onto Stack

[End If]

4) If the operator is encountered, Pop two elements

i) A -> Top element

ii) B-> Next to Top elements

iii) Evaluate B operator A push B operator A onto Stack

5) Set result = pop

6) END

Let’s see an example to better understand the algorithm:

Expression: 456*+

Advantage of Postfix Expression over Infix Expression:

An infix expression is difficult for the machine to know and keep track of precedence of operators. On the other hand, a postfix expression itself determines the precedence of operators (as the placement of operators in a postfix expression depends upon its precedence). Therefore, for the machine, generally it is easier to carry out a postfix expression than an infix expression.

CONCLUSION:

If you were aware of Stack data structure and thinking that it is useless in real life, well, here is the real-life use case for you. I hope this will be useful to understand the concepts of the stack as well as the evaluation process and algorithms of the calculator.

Click here for an e-book reference