Postfix Expression Using Stack

Stack is one of the data structures that are used to store the data. Stack basically uses a method called Last in, First out (LIFO). This means when we visually interpret a stack, the data entries inside a stack are done in an order where the last entry will be removed first in order to traverse the stack. The insertion of data and the deletion is done using two operations, Push and Pop.

The primary objective of the push operation is to enter the data into the stack. Whenever the data is pushed into the stack, it is referred to as the top of the stack. The top of the stack means the fresh or the last entry into the stack. The pop operation will remove the data from the stack, which is the new entry. The pop operation only deletes the top of the stack.

The top means the last entry into the stack. The push and pop operations that are being performed are done only on the top of the stack. Stacks can be applied in various formats, such as arrays, linked lists, etc. For array mode, a fixed size of the array is considered, and the top is continuously monitored so that the push and pop operations are done efficiently. In the linked list mode, each element in the stack is represented as a node that contains the value from the element in the stack, which is linked to the next element.

Stacks are used in various applications, such as managing the data flow and managing function calls in programming languages; this is done where the function calls are considered as the elements for the stack and are pushed and popped from the stack whenever it is needed. One of the primary purposes of stacks is for expression evaluation; there are many types of expression evaluation: infix, postfix, and prefix. These are used to evaluate the arithmetic expressions, which include operands and operators.

Expression evaluation is a technique, where solving a given arithmetic equation using a stack with the help of its operations. Some rules are to be followed while evaluating an arithmetic expression. The given arithmetic expression will be in the form of an infix notation where the operations are mentioned between two operands. We have to follow the operator precedence to evaluate the arithmetic expression using the stack. The infix representation will be in the form where the operand is between two operators. The prefix representation will be in the form where the operand is before the operators.

Let us discuss the postfix expression evaluation in detail: The postfix expression will be in the form where the operand will be at the last of the operators.

To evaluate the given arithmetic expression, we must follow the rules given below:

1. Take an empty stack.
2. From the given arithmetic expression, scan it from left to right.
3. For each element of the expression, if the element is an operator, then push it into the stack until we get an operand.
4. If we encounter an operand, pop the first two elements from the stack and operate with the operand.
5. The answer from the operation will be pushed back into the stack.
6. Again, scan until we get an operand and do the same.
7. Push the final result into the stack.
8. Pop the final result into the computer.

Consider the following postfix expression: 3173*+-, to solve the given expression:

1. First, take an empty stack.
2. Scan it from the left to the end.
3. Push the first element into the stack, i.e., 3.
4. Check for the next element in the expression; the next element is also an operator 1.
5. Push the element 1 into the stack. The next element from the given expression is also an operator, so push it into the stack.
6. Scan for the next element, which is also an operator, and push the element into the stack.
7. The next element is an operand, so we have to take the top and the element right below the top and perform the operation based on the precedence.
8. According to the precedence, the * has the higher priority so that we can continue.
9. Now apply * operand for the 7 and 3; we get 21.
10. Now push the 21 into the stack and scan the expression; we again got an operand.
11. Now take the top and the element below the top and apply the operand to the elements 21 and 1; we get 22.
12. Now, push 22 into the stack and then scan.
13. We get an operand; taking 22 and 3, we apply the operand and get -19 as the final answer.
14. Push the final answer into the stack, and then pop it back into the device.

This way, the given postfix expression is calculated using the stack as the data structure.