CODEWITHSUNDEEP
calgorithmmatchingbrackets
James
James

Reputation: 91

matching brackets program in C

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:

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.

Upvotes: 5

Views: 3625

Answers (5)

Shashank
Shashank

Reputation: 13869

Here is the easiest way to do it using no regex/complicated language stuff.

The only thing you need is a simple array of maximum length 10 to simulate a stack. You need this to keep track of the last bracket type opened. Every time you open a bracket, you will "push" the bracket type onto the end of the array. Every time you close a bracket, you will "pop" the bracket type off the end of the array if and only if the bracket types match.

Algorithm:

Iterate over each character in the string.

When you encounter an open bracket of any type, append it to your array. If your array is full (i.e. you are already storing 10 open bracket types), and you can't append it, you already know that the brackets do not match and you can end your program.

When you encounter a closed bracket of any type, if the closed-bracket type does not match the last element of your array, you already know that the brackets do not match and you can end the program, printing that they don't match. Else if the closed-bracket type does match the last element of your array, "pop" it off the end of your array.

Finally, if the array is empty at the end of your iteration, then you know that the brackets match.

EDIT: It has been pointed out to me in the comments that this is an explicit stack and that recursion may be a better method of using an implicit stack.

Upvotes: 2

Bernhard Barker
Bernhard Barker

Reputation: 55599

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.

Upvotes: 5

Ingo Schalk-Schupp
Ingo Schalk-Schupp

Reputation: 920

As amit answered, you definitely need some sort of stack. This can be mathematically proven. However, you can avoid using stack data structures in your code by using the compiler's stack mechanism. This requires you to use recursive function calls.

Upvotes: 1

sandymatt
sandymatt

Reputation: 5612

So you're not allowed to use stacks..but you ARE allowed to use arrays! This is good.

This might be against the rules, but you can mimic a stack with an array. Keep an index to the "next open spot" in the array, and make sure you do all of your insertions / deletions from that index.

My suggestion? parse each character in the string, and use the "stack" described above to determine when to add and remove brackets / parens / curlys.

Upvotes: 2

amit
amit

Reputation: 178431

You are describing a Context-Free language in here that you need to verify if a word is in the language or not.

This means that there is a Context Free Grammar you can create that describes this language.

For this specific language, one can use a deterministic stack automaton to verify if a word is in the language or not (this is not true for every context free langauge, some require non deterministic stack automaton)
Note that you can use recursion to imitate stack, and use the implicit call stack for it.

Other alternative (which is good for all context free languages) is CYK Algorithm, but it's an overkill here.

Upvotes: 3

Related Questions