Parenthesis Matching Problem Using Stack Data Structure (Applications of Stack)
What is parenthesis matching?
If you remember learning mathematics in school, we had BODMAS there, which required you to solve the expressions, first enclosed by brackets, and then the independent ones. That's the bracket we're referring to. We have to see if the given expression has balanced brackets which means every opening bracket must have a corresponding closing bracket and vice versa.
Below given image would surely make it clear for you.
Checking if the parentheses are balanced or not must be a cakewalk for humans, since we have been dealing with this for the whole time. But even we would fail if the expression becomes too large with a great number of parentheses. This is where automating the process helps. And for automation, we need a proper working algorithm. We will see how we accomplish that together.
We’ll use stacks to match these parentheses. Let’s see how:
1. Assume the expression given to you as a character array.
- Iterate through the character array and ignore everything you find other than the opening and the closing parenthesis. Every time you find an opening parenthesis, push it inside a character stack. And every time you find a closing parenthesis, pop from the stack, in which you pushed the opening bracket.
Conditions for unbalanced parentheses:
When you find a closing parenthesis and try achieving the pop operation in the stack, the stack must not become underflow. To match the existing closing parenthesis, at least one opening bracket should be available to pop. If there is no opening bracket inside the stack to pop, we say the expression has unbalanced parentheses.
For example: the expression (2+3)*6)1+5 has no opening bracket corresponding to the last closing bracket. Hence unbalanced.
At EOE, that is, when you reach the end of the expression, and there is still one or more opening brackets left in the stack, and it is not empty, we call these parentheses unbalanced.
For example: the expression (2+3)*6(1+5 has 1 opening bracket left in the stack even after reaching the EOE. Hence unbalanced.
4. Note: Counting and matching the opening and closing brackets numbers is not enough to conclude if the parentheses are balanced. For eg: 1+3)*6(6+2.
Example:
We’ll try checking if the above expression has balanced parentheses or not.
Step 1: Iterate through the char array, and push the opening brackets at positions 0, 3, 6 inside the stack.
Step 2: Try popping an opening bracket from the stack when you encounter a closing bracket in the expression.
Step 3: Since we reached the EOE and there are still two parentheses left in the stack, we declare this expression of parentheses unbalanced.
Understanding the code below:
int parenthesisMatch(char *exp){
struct stack sp;
sp->size = 100;
sp->top = -1;
sp->arr = (char *)malloc(sp->size sizeof(char));
for (int i = 0; exp[i]!='\0'; i++) {
if(exp[i]=='('){
push(sp, '(');
} else if(exp[i]==')'){
if(isEmpty(sp)){
return 0;
} pop(sp); } }
if(isEmpty(sp)){
return 1;
} else{
return 0; } }
1. Start by creating an integer function paranthesisMatch, and pass the reference to a character array(expression) exp in the function as a parameter. This function will return 1 if the parentheses are balanced and zero otherwise.
2. Inside that function, create a stack pointer sp. And initialize the size member to some big number, let it be 100. Initialize the top to -1, and assign the array pointer a memory location in the heap. You have the freedom to choose any data structure you want to implement this stack. We have learned stacks using both arrays and linked lists very efficiently.
3. So, it would be better if you just copy everything of stack implementation because it will more or less remain the same for that part. I’ll use the array one.
4. Change the datatype of the array from integer to char. Accordingly, change everything from integer to char. And arr to exp.
5. Run a loop starting from the beginning of the expression till it reaches EOE.
6. If the current character of the expression is an opening parenthesis,’(' , push it into the stack using the push operation.
7. Else if the current character is a closing parenthesis ‘)’, see if the stack is not empty, using isEmpty, and if it is, return 0 there itself, else pop the topmost character using pop operation.
8. In the end, if the stack becomes empty, return 1, else 0.
9. In the main, define a random character array expression and just passing this expression to parenthesisMatch would do our job.
Multiple Parenthesis Matching
Above, we discussed matching only one type of parenthesis. Now, let's talk about matching all three types of parentheses. this is what we called multi-parenthesis matching.
If you remember, parenthesis matching has nothing to do with the validity of the expression. It just tells whether an expression has all the parentheses balanced or not. A balanced parentheses expression has a corresponding closing parenthesis to all of its opening parentheses. When we talk about matching multi parenthesis, our focus is mainly on the three types of an opening parenthesis, [ { ( and their corresponding closing parentheses, ) } ]. So, basically, this is just an extension of what we talk about in the previous .
Modifying what we did earlier to make it work for multi-matching needs very little attention. Just follow these steps:
1. Whenever we encounter an opening parenthesis, we simply push it in the stack, similar to what we did earlier.
2. And when we encounter a closing parenthesis, the following conditions should be met to declare its balance:
Before we pop, this size of the stack must not be zero.
The topmost parenthesis of the stack must match the type of closing parenthesis we encountered.
3. If we find a corresponding opening parenthesis with conditions in point 2 met for every closing parenthesis, and the stack size reduces to zero when we reach EOE, we declare these parentheses, matching or balanced. Otherwise not matching or unbalanced.
So, basically, we modified the pop operation. And that's all. Let's see what additions to the code we would like to make. But before that follow the illustration below to get a better understanding of the algorithm.
Example:
We’ll try checking if the above expression has balanced multi-parentheses or not.
Step 1: Iterate through the char array, and push the opening brackets of all types at positions 0, 1, 4 inside the stack.
Step 2: When you encounter a closing bracket of any type in the expression, try checking if the kind of closing bracket you have got matches with the topmost bracket in the stack.
Step 3: Since we couldn’t pop an opening bracket corresponding to a closed bracket, we would just end the program here, declaring the parentheses unbalanced.
Understanding the code below:
1. Our main focus is to modify the code for matching parenthesis of a single type to matching multi parentheses., we’ll copy the whole thing from above, from creating the function parenthesisMatch to the stack inside.
2. It is important to copy everything because a lot of things will remain the same. We make zero changes in the declaration of the stack and its members.
3. Run a loop starting from the beginning of the expression till it reaches EOE.
4. If the current character of the expression is an opening parenthesis, be it of any type,’(‘, ‘[’, ’{’, push it into the stack using the push operation.
5. Else if the current character is a closing parenthesis of any type ‘)’, ‘]’, ’}’, see if the stack is not empty, using isEmpty, and if it is, return 0 there itself, else pop the topmost character using pop operation and store it in another character variable named popped_ch declared globally.
6. Create an integer function, match which will get the characters, popped_ch, and the current character of the expression as two parameters. Inside this function, check if these two characters are the same. If they are the same, return 1, else 0.
int match(char a, char b){ i
f(a=='{' && b=='}'){
return 1;
} if(a=='(' && b==')'){ return 1;
} if(a=='[' && b==']'){
return 1;
} return 0;
}
Infix, Prefix and Postfix Expressions
What are these?
The three terms, infix prefix, and postfix will be dealt with individually later. In general, these are the notations to write an expression. Mathematical expressions have been taught to us since childhood. Writing expressions to add two numbers for subtraction, multiplication, or division. They were all expressed through certain expressions. That's what we're learning today: different expressions.
Infix:
This is the method we have all been studying and applying for all our academic life. Here the operator comes in between two operands. And we say, two is added to three. For eg: 2 + 3, a * b, 6 / 3 etc.
< operand 1 >< operator >< operand2 >
Prefix:
This method might seem new to you, but we have vocally used them a lot as well. Here the operator comes before the two operands. And we say, Add two and three. For e.g.: + 6 8, * x y, - 3 2 etc.
< operator \>< operand 1 >< operand2 >
Postfix:
This is the method that might as well seem new to you, but we have used even this in our communication. Here the operator comes after the two operands. And we say, Two and three are added. For e.g.: 5 7 +, a b *, 12 6 / etc.
< operand 1 >< operand2 >< operator >
To understand the interchangeability of these terms, please refer to the table below.
| s.no | Infix | Prefix | Postfix |
| 1. | a * b | * a b | a b * |
| 2. | a - b | - a b | a b - |
So far, we have been dealing with just two operands, but a mathematical expression can hold a lot more. We will now learn to change a general infix mathematical expression to its prefix and postfix relatives. But before that, it is better to understand why we even need these methods.
Why these methods?
When we evaluate a mathematical expression, we have a rule in mind, named BODMAS, where we have operators’ precedence in this order; brackets, of, division, multiplication, addition, subtraction. But what would you do when you get to evaluate a 1000 character long-expression, or even longer one? You will try to automate the process. But there is one issue. Computers don’t follow BODMAS; rather, they have their own operator precedence. And this is where we need these postfix and prefix notations. In programming, we use postfix notations more often, likewise, following the precedence order of machines.
Consider the expression a* ( b + c ) * d; since computers go left to right while evaluating an expression, we’ll convert this infix expression to its postfix form.
Its postfix form is, a b c + d . You must be wondering how we got here. Refer to the illustration below.
We have successfully reached what we wanted the machine to do. Now the kick is in converting infixes to postfixes and prefixes.
Converting infix to prefix:
Consider the expression, x - y * z.
1. Parentheses the expression. The infix expression must be parenthesized by following the operator precedence and associativity before converting it into a prefix expression. Our expression now becomes ( x - ( y * z ) ).
2. Reach out to the innermost parentheses. And convert them into prefix first, i.e. ( x - ( y z ) ) changes to ( x - [ y z ] ).
3. Similarly, keep converting one by one, from the innermost to the outer parentheses. ( x - [ y z ] ) → [ - x y z ].
4. And we are done.
Converting infix to postfix:
Consider the same expression, x - y * z.
5. Parentheses the expression as we did previously. Our expression now becomes ( x - ( y * z ) ).
6. Reach out to the innermost parentheses. And convert them into postfix first, i.e. ( x - ( y z ) ) changes to ( x - [ y z ] ).
7. Similarly, keep converting one by one, from the innermost to the outer parentheses. ( x - [ y z ] ) → [ x y z - ].
8. And we are done.
Similarly the expression p - q - r / a, follows the following conversions to become a prefix expression:
- p - q - r / a → ( ( p - q ) - ( r / a ) ) → ( [ - p q ] - [ / r a ] ) → - - p q / r a
Infix To Postfix Using Stack
Converting an infix expression to its postfix counterpart needs you to follow certain steps. The following are the steps:
Start moving left to right from the beginning of the expression.
The moment you receive an operand, concatenate it to the postfix expression string.
And the moment you encounter an operator, move to the stack along with its relative precedence number and see if the topmost operator in the stack has higher or lower precedence. If it's lower, push this operator inside the stack. Else, keep popping operators from the stack and concatenate it to the postfix expression until the topmost operator becomes weaker in precedence relative to the current operator.
If you reach the EOE, pop every element from the stack, and concatenate them as well. And the expression you will receive after doing all the steps will be the postfix equivalent of the expression we were given.
For our understanding now, let us consider the expression x - y / z - k * a. Step by step, we will turn this expression into its postfix equivalent using stacks.
1. We will start traversing from the left.
2. First, we got the letter ‘x’. We just pushed it into the postfix string. Then we got the subtraction symbol ‘-’, and we push it into the stack since the stack is empty.
3. Similarly, we push the division operator in the stack since the topmost operator has a precedence number 1, and the division has 2.
4. The next operator we encounter is again a subtraction. Since the topmost operator in the stack has an operator precedence number 2, we would pop elements out from the stack until we can push the current operator. This leads to removing both the present operators in the stack since they are both greater or equal in precedence. Don’t forget to concatenate the popped operators to the postfix expression.
5. Next, we have a multiplication operator whose precedence number is 2 relative to the topmost operator in the stack. Hence we simply push it in the stack.
6. And then we get to the EOE and still have two elements inside the stack. So, just pop them one by one, and concatenate them to the postfix. And this is when we succeed in converting the infix to the postfix expression.
Follow every step meticulously, and you will find it very easy to master this. You can see if the answer we found at the end is correct manually.
x - y / z - k a → (( x - ( y / z )) - ( k a )) → (( x - [ y z / ]) - [ k a ] ) → [ x y z / - ] - [ k a ] → x y z / - k a * -
Coding Infix to Postfix in C using Stack
We used stacks to take hold of the operators we encountered in the expression. We followed an algorithm to convert an infix expression to its postfix equivalent, which in short, said:
1. We create a string variable that will hold our postfix expression. We start moving from the left to the right. And the moment we receive an operand, we concatenate it to the postfix string. And whenever we encounter an operator, we proceed with the following steps:
Keep in account the operator and its relative precedence.
If either the stack is empty or its topmost operator has lower relative precedence, push this operator-precedence pair inside the stack.
Else, keep popping operators from the stack and concatenate it to the postfix expression until the topmost operator becomes weaker in precedence relative to the current operator.
2. If you reach the EOE, pop every element from the stack, if there is any, and concatenate them as well. And there, you’ll have your postfix expression.
Let us now see the program pursuing the conversion. I have attached the snippets alongwith. Keep checking them while you understand the codes.
Understanding the program for infix to postfix conversion:
1. First of all, create a character pointer function infixToPostfix since the function has to return a character array. And now pass into this function the given expression, which is also a character pointer.
2. Define a struct stack pointer variable sp. And give it the required memory in the heap. Create the instance. It’s safe to assume that a struct stack element and all its basic operations, push, pop, etc., have already been defined. You better copy everything from the stack tutorial.
3. Create a character array/pointer postfix, and assign it sufficient memory to hold all the characters of the infix expression in the heap.
4. Create two counters, one to traverse through the infix and another to traverse and insert in the postfix. Refer to the illustration below, which describes the initial conditions.
5. Run a while loop until we reach the EOE of the infix. And inside that loop, check if the current index holds an operator, and if it’s not, add that character into the postfix and increment both the counters by 1. And if it does hold an operator, call another function that would check if the precedence of the stackTop is less than the precedence of the current operator. If yes, push it inside the stack. Else, pop the stackTop, and add it back into the postfix. Increment j by 1.
char infixToPostfix(char infix){
struct stack sp = (struct stack ) malloc(sizeof(struct stack));
sp->size = 10;
sp->top = -1;
sp->arr = (char ) malloc(sp->size* sizeof(char));
char postfix = (char ) malloc((strlen(infix)+1) * sizeof(char));
int i=0; // Track infix traversal
int j = 0; // Track postfix addition
while (infix[i]!='\0') {
if(!isOperator(infix[i])){
postfix[j] = infix[i];
j++; i++;
} else{
if(precedence(infix[i])> precedence(stackTop(sp))){
push(sp, infix[i]); i++;
} else{
postfix[j] = pop(sp);
j++;
} } }
while (!isEmpty(sp)){
postfix[j] = pop(sp); j++;
} postfix[j] = '\0';
return postfix;
}
Creating the function infixToPostfix
6. It’s now time to create the two functions to make this conversion possible. isOperator & precedence which checks if a character is an operator and compares the precedence of two operators respectively.
7. Create an integer function isOperator which takes a character as its parameter and returns 2, if it's an operator, and 0 otherwise.
int isOperator(char ch){
if(ch=='+' || ch=='-' ||ch=='*' || ch=='/')
return 1;
else
return 0;
}
Creating the function isOperator
8. Create another integer function precedence, which takes a character as its parameter, and returns its relative precedence. It returns 3 if it’s a ‘/’ or a ‘*’. And 2 if it's a ‘+’ or a ‘-’.
9. If we are still left with any element in the stack at the end, pop them all and add them to the postfix.
int precedence(char ch){
if(ch == '*' || ch=='/')
return 3;
else if(ch == '+' || ch=='-')
return 2;
else return 0;
}
Creating the function precedence