Please complete the following IN C ONLY, not C++, not java. Please also utilize

Question

Please complete the following IN C ONLY, not C++, not java. Please also utilize a standard stack as mentioned in the ask and follow all instructions. If you are unable to do so please leave this problem for someone who can do it or you will be negatively rated.

You are given a string consisting of parenthesis style characters ( ) [ ] and { }. A string of this type is said to be correct if:

(a) It is an empty string

(b) If string A is correct and string B is correct then string AB is correct

(c) If A is correct hten (A), [A], and {A} are all correct

You are to write a program that takes as input from the keyboard a series of strings of this type that can be of any length. The first line of input will contain a single integer n telling you how many strings you will be testing. Following that integer will be n lines (each ending in a new line character) that represent the strings you are supposed to test with one string per line.

Your program should output Yes if a given string is correct and No otherwise.

For example if the user types the following as input

3

([])

(([{}])))

([()[]()])()

Then your program should give the following output:

Yes

No

Yes

You will note that if you do your program correctly there is no prompt for data and the yes and no answers will be interspersed with your input data when you enter it manually. The following would be a more accurate representation of what you see on the screen when you cut and paste the input into your program.

3

([])

Yes

(([{}])))

No

([()[]()])()

Yes

You may find it useful to use a text file for testing your code so that you do not have to keep retyping the tests. You can do this from the command line by typing the name of the executable file followed by a less than sign and the name of your file. For example, if my executable is named day7 then I could type:

day7 < input.txt

This would redirect standard input so that the input instead comes from the file named input.txt. You should note that the input.txt file needs to be in the same directory as your executable file for the above command to work. Alternatively you can give the complete path information for the input file.

You may not assume anything about the size of the test strings coming in. In fact, some of the test strings may be hundreds of thousands of characters long…

How do you solve it? The trick to this problem is realizing that our stack interface can be used to solve the problem. One way to approach the problem is to read in a character, if it is a left marker then push it onto the stack. If it is a right marker then check the top of the stack (if it exists), if it is the correct left marker then pop it out and continue testing the string. If you encounter a right marker and the top of the stack is not the left hand version of the marker you just picked up or the stack is empty then you can determine that the string is not correct, clear the stack and go on to the next example. If you finish a whole string (encounter a new line) without encountering a problem then you can determine that the input string is correct.

Explanation / Answer

I hope this is what you asked .

I used just c and stack to check the paranthesis balancing.

#include<stdio.h>
#include<stdlib.h>
#define bool int

/* structure of a stack node */
struct sNode
{
char data;
struct sNode *next;
};

/* Function to push an item to stack*/
void push(struct sNode** top_ref, int new_data);

/* Function to pop an item from stack*/
int pop(struct sNode** top_ref);

/* Returns 1 if character1 and character2 are matching left
and right Parenthesis */
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;

/* Declare an empty character stack */
struct sNode *stack = NULL;

/* Traverse the given expression to check matching parenthesis */
while (exp[i])
{
/*If the exp[i] is a starting parenthesis then push it*/
if (exp[i] == '{' || exp[i] == '(' || exp[i] == '[')
push(&stack, exp[i]);

/* If exp[i] is an ending parenthesis then pop from stack and
check if the popped parenthesis is a matching pair*/
if (exp[i] == '}' || exp[i] == ')' || exp[i] == ']')
{

/*If we see an ending parenthesis without a pair then return false*/
if (stack == NULL)
return 0;

/* Pop the top element from stack, if it is not a pair
parenthesis of character then there is a mismatch.
This happens for expressions like {(}) */
else if ( !isMatchingPair(pop(&stack), exp[i]) )
return 0;
}
i++;
}
  
/* If there is something left in expression then there is a starting
parenthesis without a closing parenthesis */
if (stack == NULL)
return 1; /*balanced*/
else
return 0; /*not balanced*/
}

int main()
{
char exp[100];
printf("Enter the string");
scanf("%s",exp);
if (areParenthesisBalanced(exp))
printf(" Yes ");
else
printf(" No ");
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;
}
}

Here i got the input in the exp . Then i pushed the paranthesis in the stack if there is matching paranthesis then it should be popped. At the end of the string if there exist any paranthesis in the stack then string is unbalanced it return 0 else it return 1.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.