Parenthesis checking using stack
What is paranthesis matching?
In an expression opening bracket '(' should have corresponding closing brackets ')'.
We’ll use stacks to match these parentheses. Let’s see how:
1. Assume the expression given to you as a character array.
2. 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.
3.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.
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.
I have one task for you as well. Try checking if these expressions are balanced or not. And also, tell the number of times you had to push or pop in the stack. Also, comment on the time complexity of this algorithm. Answer the best and the worst runtime complexity for an expression of size n.
7 - ( 8 ( 3 * 4 ) + 11 + 12 ) ) - 8 )
#include <stdio.h>
#include <stdlib.h>
struct stack
{
int size;
int top;
char *arr;
};
int isEmpty(struct stack *ptr)
{
if (ptr->top == -1)
{
return 1;
}
else
{
return 0;
}
}
int isFull(struct stack *ptr)
{
if (ptr->top == ptr->size - 1)
{
return 1;
}
else
{
return 0;
}
}
void push(struct stack* ptr, char val){
if(isFull(ptr)){
printf("Stack Overflow! Cannot push %d to the stack\n", val);
}
else{
ptr->top++;
ptr->arr[ptr->top] = val;
}
}
char pop(struct stack* ptr){
if(isEmpty(ptr)){
printf("Stack Underflow! Cannot pop from the stack\n");
return -1;
}
else{
char val = ptr->arr[ptr->top];
ptr->top--;
return val;
}
}
int parenthesisMatch(char * exp){
// Create and initialize the stack
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;
}
}
int main()
{
char * exp = "((8)(*--$$9))";
// Check if stack is empty
if(parenthesisMatch(exp)){
printf("The parenthesis is matching");
}
else{
printf("The parenthesis is not matching");
}
return 0;
}
Multi-Parenthesis Matching
Here we will deal with three type of parenthesis → (), [] & {}.
We will check if a expression has a balanced parenthesis 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, ) } ].
Steps to follow:
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.
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.
Code
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){
if(a=='{' && b=='}'){
return 1;
}
if(a=='(' && b==')'){
return 1;
}
if(a=='[' && b==']'){
return 1;
}
return 0;
}
→ If the match function returns 1, our pop operation is successful, and we can continue checking further characters; else, if it returns 0, end the program here itself and return 0 to the main.
→ And if things went well throughout, and in the end, if the stack becomes empty, return 1, else 0.
// code for multi-parenthesis matching
int parenthesisMatch(char * exp){
// Create and initialize the stack
struct stack* sp;
sp->size = 100;
sp->top = -1;
sp->arr = (char *)malloc(sp->size * sizeof(char));
char popped_ch;
for (int i = 0; exp[i]!='\0'; i++)
{
if(exp[i]=='(' || exp[i]=='{' || exp[i]=='['){
push(sp, exp[i]);
}
else if(exp[i]==')'|| exp[i]=='}' || exp[i]==']'){
if(isEmpty(sp)){
return 0;
}
popped_ch = pop(sp);
if(!match(popped_ch, exp[i])){
return 0;
}
}
}
if(isEmpty(sp)){
return 1;
}
else{
return 0;
}
}
#include <stdio.h>
#include <stdlib.h>
struct stack
{
int size;
int top;
char *arr;
};
int isEmpty(struct stack *ptr)
{
if (ptr->top == -1)
{
return 1;
}
else
{
return 0;
}
}
int isFull(struct stack *ptr)
{
if (ptr->top == ptr->size - 1)
{
return 1;
}
else
{
return 0;
}
}
void push(struct stack* ptr, char val){
if(isFull(ptr)){
printf("Stack Overflow! Cannot push %d to the stack\n", val);
}
else{
ptr->top++;
ptr->arr[ptr->top] = val;
}
}
char pop(struct stack* ptr){
if(isEmpty(ptr)){
printf("Stack Underflow! Cannot pop from the stack\n");
return -1;
}
else{
char val = ptr->arr[ptr->top];
ptr->top--;
return val;
}
}
char stackTop(struct stack* sp){
return sp->arr[sp->top];
}
int match(char a, char b){
if(a=='{' && b=='}'){
return 1;
}
if(a=='(' && b==')'){
return 1;
}
if(a=='[' && b==']'){
return 1;
}
return 0;
}
int parenthesisMatch(char * exp){
// Create and initialize the stack
struct stack* sp;
sp->size = 100;
sp->top = -1;
sp->arr = (char *)malloc(sp->size * sizeof(char));
char popped_ch;
for (int i = 0; exp[i]!='\0'; i++)
{
if(exp[i]=='(' || exp[i]=='{' || exp[i]=='['){
push(sp, exp[i]);
}
else if(exp[i]==')'|| exp[i]=='}' || exp[i]==']'){
if(isEmpty(sp)){
return 0;
}
popped_ch = pop(sp);
if(!match(popped_ch, exp[i])){
return 0;
}
}
}
if(isEmpty(sp)){
return 1;
}
else{
return 0;
}
}
int main()
{
char * exp = "[4-6]((8){(9-8)})";
if(parenthesisMatch(exp)){
printf("The parenthesis is balanced");
}
else{
printf("The parenthesis is not balanced");
}
return 0;
}