You are given a string consisting of parenthesis style characters ( ) [ ] and { }. A string of thistype 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 then (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 executablefile 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 mark er 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.

Complete in C please