Question

Complete the following C program to solve the parenthesis matching problem using a stack. We studied the problem and the algorithm in class. Given a sequence of chars (symbols), check if each “(”, “{”, or “[” is paired with a matching “)”, “}”, or “[”. For example,

1. correct: ( )(( )){([( )])}    
2. correct: (( )(( ))){([( )])}  
3. incorrect: )(( )){([( )])}    
4. incorrect: ({[ ])}    
5. incorrect: (  

#include <stdio.h>

#include <stdlib.h>

#define size 100

void push(char *s, int* top, char element);

char pop(char *s, int *top);

int full(int *top, const int size);

int empty(int *top);

void init(int *top);

void init(int *top)

{*top = 0;

}

void push(char *s, int* top, char element)

{s[(*top)++] = element;

}

char pop(char *s, int *top)

{return s[--(*top)];

}

int full(int *top, const int size)

{return *top == size ? 1 : 0;

}

int empty(int *top)

{return *top == 0 ? 1 : 0;

}

void main(){

int top;

char element;

char stack[size];

init(&top);

//You are required to complete the following:

//read a sequence of chars

//check if each parenthesis matches with the correct one; print error message if not.

//you can define variables and arrays that you need.

}

Answer 1

CODE SNAPSHOTS:

OUTPUT SNAPSHOTS:

CODE:

#include <stdio.h>
#include <stdlib.h>
#define SIZE 100

bool check(char *par, char *s, int *top);
void push(char *s, int *top, char element);
char pop(char *s, int *top);
int full(int *top, const int size);
int empty(int *top);
void init(int *top)
{
    *top = 0;
}
void push(char *s, int *top, char element)
{
    s[(*top)++] = element;
}
char pop(char *s, int *top)
{
    return s[--(*top)];
}
int full(int *top, const int size)
{
    return *top == size ? 1 : 0;
}
int empty(int *top)
{
    return *top == 0 ? 1 : 0;
}
bool check(char *par, char *s, int *top)
{
    for (int i = 0; par[i] != '\0'; i++)
    {
        if (par[i] == '(' || par[i] == '{' || par[i] == '[')
            push(s, top, par[i]);
        else
        {
            if (empty(top))
                return false;
            char ele = pop(s, top);
            bool flag = false;
            switch (par[i])
            {
            case ')':
                if (ele == '(')
                    flag = true;
                break;
            case '}':
                if (ele == '{')
                    flag = true;
                break;
            case ']':
                if (ele == '[')
                    flag = true;
                break;
            default:
                flag = false;
                break;
            }
            if (!flag)
                return false;
        }
    }
    if (empty(top))
        return true;
    return false;
}
int main()
{
    int top;
    char stack[SIZE];
    init(&top);
    char paranthesis[SIZE];
    printf("Enter the sequence:   ");
    scanf("%s", paranthesis);

    if (check(paranthesis, stack, &top))
    {
        printf("\nCorrect Sequence");
    }
    else
    {
        printf("\nIncorrect Sequence");
    }
    return 0;
}

Please comment in case of doubts or queries.
It would be really hepful if you could give an upvote :)