One common use of stacks is to parse certain kinds of text strings. Typically th
ID: 3537984 • Letter: O
Question
One common use of stacks is to parse certain kinds of text strings. Typically the strings are lines
of code in a computer language, and the programs parsing them are compilers.
Write a program that prompts the user to enter a string, and then checks the delimiters in the
string. The delimiters are the braces '{' and '}', brackets '[' and ']', and parenthesis '(' and ')'. Each
opening or left delimiter should be matched by closing or right delimiter; that is, every '{' should
be followed by a matching '}' and so on. Also, opening delimiters that occur later in the string
should be closed before those occurring earlier. Examples:
c[d] // correct
a{b[c]d}e // correct
a{b(c]d}e // not correct; } doesn't match (
a[b{c}d]e} // not correct; nothing matches final }
a{b(c) // not correct; Nothing matches opening {
The program works by reading characters from the string one at a time and placing opening
delimiters, when it finds them, on a stack. When it reads a closing delimiter from the input, it
pops the opening delimiter from the top of the stack and attempts to match it with the closing
delimiter. If they're not the same type, then an error has occurred.
Explanation / Answer
#include<stdio.h>
#include<stdlib.h>
#define bool int
/* structure of a stack node */
struct sNode
{
char data;
struct sNode *next;
};
void push(struct sNode** top_ref, int new_data);
int pop(struct sNode** top_ref);
bool isMatchingPair(char character1, char character2)
{
if(character1 == '(' && character2 == ')')
return 1;
else if(character1 == '{' && character2 == '}')
return 1;
else if(character1 == '[' && character2 == ']')
return 1;
else
return 0;
}
/*Return 1 if expression has balanced Parenthesis */
bool areParenthesisBalanced(char exp[])
{
int i = 0;
struct sNode *stack = NULL;
while(exp[i])
{
if(exp[i] == '{' || exp[i] == '(' || exp[i] == '[')
push(&stack, exp[i]);
if(exp[i] == '}' || exp[i] == ')' || exp[i] == ']')
{
if(stack == NULL)
return 0;
else if ( !isMatchingPair(pop(&stack), exp[i]) )
return 0;
}
i++;
}
if(stack == NULL)
return 1; /*balanced*/
else
return 0; /*not balanced*/
}
/*driver program */
int main()
{
char exp[1000];
printf("Enter String to be matched: ");
scanf("%s",exp);
if(areParenthesisBalanced(exp))
printf(" Balanced : Correct Expression");
else
printf(" Not Balanced : Expression Incorrect ");
return 0;
}
/* Function to push an item to stack*/
void push(struct sNode** top_ref, int new_data)
{
/* allocate node */
struct sNode* new_node =
(struct sNode*) malloc(sizeof(struct sNode));
if(new_node == NULL)
{
printf("Stack overflow ");
getchar();
exit(0);
}
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*top_ref);
/* move the head to point to the new node */
(*top_ref) = new_node;
}
/* Function to pop an item from stack*/
int pop(struct sNode** top_ref)
{
char res;
struct sNode *top;
/*If stack is empty then error */
if(*top_ref == NULL)
{
printf("Stack overflow ");
getchar();
exit(0);
}
else
{
top = *top_ref;
res = top->data;
*top_ref = top->next;
free(top);
return res;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.