matching brackets program in C

Question

I am fairly new to c programming and I have a question to do with a bracket matching algorithm:

Basically, for an CS assignment, we have to do the following:

We need to prompt the user for a string of 1-20 characters. We then need to report whether or not any brackets match up. We need to account for the following types of brackets "{} [] ()".

Example:

Matching Brackets
-----------------
Enter a string (1-20 characters): (abc[d)ef]gh
The brackets do not match.

Another Example:

Enter a string (1-20 characters): ({[](){}[]})
The brackets match

One of the requirements is that we do NOT use any stack data structures, but use techniques below:

• Data types and basic operators
• Branching and looping programming constructs
• Basic input and output functions
• Strings
• Functions
• Pointers
• Arrays
• Basic modularisation

Any ideas of the algorithmic steps I need to take ? I'm really stuck on this one. It isn't as simple as counting the brackets, because the case of ( { ) } wouldn't work; the bracket counts match, but obviously this is wrong.

Any help to put me in the right direction would be much appreciated.

Answer 1

You can use recursion (this essentially also simulates a stack, which is the general consensus for what needs to happen):

• When you see an opening bracket, recurse down.
• When you see a closing bracket:
  • If it's matched (i.e. the same type as the opening bracket in the current function), process it and continue with the next character (don't recurse)
  • If it's not matched, fail.
• If you see any other character, just move on to the next character (don't recurse)
• If we reach the end of the string and we currently have a opening bracket without a match, fail, otherwise succeed.