Parenthesis Matching in a Snap with Stacks 🧱

Release .5

What is a Stack 🤨?
A stack is a data structure that follows the Last In First Out (LIFO) principle. This means that the last item added to the stack is the first item removed.
Stacks can be implemented using arrays or linked lists 🔗.

A simple example of a stack is a stack of plates. When you add a plate to the stack, it goes on top of the other plates ( Last in ), when you remove a plate from the stack, you remove the top plate first ( First out ) 🏃🏻‍♂️.

*These are the operations that can be performed in a stack:
*

• Push: To push an item onto the stack, we first need to check if the stack is full. If the stack is full, we cannot push any more items onto it. If the stack is not full, we can push the item onto the stack by adding it to the top of the stack.

• Pop: To pop an item off the stack, we first need to check if the stack is empty. If the stack is empty, we cannot pop any items off it. If the stack is not empty, we can pop the item off the stack by removing it from the top of the stack.

• Peek: To peek at the top item of the stack, we first need to check if the stack is empty. If the stack is empty, there is no top item to peek at. If the stack is not empty, we can peek at the top item of the stack by returning the item at the top of the stack.

• IsEmpty: To check if the stack is empty, we simply check if the top of the stack is pointing to null. If the top of the stack is null, then the stack is empty. Otherwise, the stack is not empty.

• IsFull: To check if the stack is full, we need to keep track of the capacity of the stack. If the number of items in the stack is equal to the capacity of the stack, then the stack is full. Otherwise, the stack is not full.

Implementation:

// Initialize the stack
Stack stack = new Stack();

// Push an item onto the stack
stack.push(new Plate());

// Pop an item off the stack
Plate plate = stack.pop();

// Peek at the top item of the stack
Plate topItem = stack.peek();

// Check if the stack is empty
boolean isEmpty = stack.isEmpty();

// Check if the stack is full
boolean isFull = stack.isFull();

The implementation of the stack operations that I have described here is just an example using a stack of plates. For a more concrete implementation, you can look for the implementation of these operations in your preferred coding language.

Stacks are used in many different programming applications:

• Function calling
• Infix to postfix conversion
• Parenthesis matching

Parenthesis Matching:
The parenthesis matching problem is a problem of determining whether the parentheses in a given expression are matched correctly. A parenthesis is considered to be matched if it has a corresponding parenthesis of the same type that comes after it. For example, the parentheses in the expression (2 + 3) * (4 - 1) are matched correctly, because each opening parenthesis has a corresponding closing parenthesis.
However, the parentheses in the expression (2 + 3) * )4 - 1) are not matched correctly, because the closing parenthesis ")" does not have a corresponding opening parenthesis.

To solve the parenthesis matching problem using a stack, we can do the following:

1. Initialize a stack.
2. Iterate through the expression, one character at a time.
3. If the current character is an opening parenthesis, push it onto the stack. This means that we are "pushing" the opening parenthesis onto the stack, so that we can "pop" it off later to match it with a closing parenthesis.
4. If the current character is a closing parenthesis, pop the stack and check if the top element of the stack is the corresponding opening parenthesis. If it is, then the parentheses are matched. Otherwise, the parentheses are not matched.
5. If the stack is not empty at the end of the expression, then the parentheses are not matched. This is because there are still opening parentheses that have not been matched with closing parentheses.

Here are some examples of expressions and whether they are matched or not:

(2 + 3) * (4 - 1) - Matched
(2 + 3) * )4 - 1) - Not matched
{2 + 3} * {4 - 1} - Matched

Infix, Prefix and Postfix Expressions:
They are three different ways of writing mathematical expressions.

• Infix expression: In an infix expression, the operator is placed between the operands. For example, the expression 2 + 3 is an infix expression.
• Prefix expression: In a prefix expression, the operator is placed before the operands. For example, the expression + 2 3 is a prefix expression.
• Postfix expression: In a postfix expression, the operator is placed after the operands. For example, the expression 2 3 + is a postfix expression.

Examples of infix, prefix, and postfix expressions:

• Infix: (2 + 3) * 4
• Prefix: * + 2 3 4
• Postfix: 2 3 + 4 *

Implementation:
Infix expression: To convert an infix expression to a postfix expression, we can use a stack. The stack is used to store the operators in the expression.

1. Initialize a stack.
2. Iterate through the infix expression, one character at a time.
3. If the current character is an operand, append it to the postfix expression.
4. If the current character is an operator, pop the top two elements from the stack. If the precedence of the operator on the stack is less than or equal to the precedence of the current operator, then append the current operator to the postfix expression. Otherwise, push the current operator onto the stack.
5. Repeat steps 3-4 until the end of the infix expression is reached.
6. The postfix expression will be the reversed order of the elements in the stack.

Prefix expression: To convert an infix expression to a prefix expression, we just need to reverse the infix expression.

Postfix expression: To evaluate a postfix expression, we can use a stack. The stack is used to store the operands in the expression.

1. Initialize a stack.
2. Iterate through the postfix expression, one character at a time.
3. If the current character is an operand, push it onto the stack.
4. If the current character is an operator, pop the top two elements from the stack. Perform the operation corresponding to the operator and push the output back onto the stack.
5. Repeat steps 3-4 until the end of the postfix expression is reached.
6. The top element of the stack will be the result of the expression.

Be sure to check the code for these expressions.

In this post, we discussed the stack data structure, the parenthesis matching problem, infix, prefix, and postfix expressions. We also saw the procedure on how to implement these concepts. I hope this post was informative and helpful.
If you have any questions, please feel free to leave a comment below.

Happy Coding 👍🏻!
Thank You