
November 9th, 2011, 10:00 AM
#1
Bracket matching algorithm
Hey... I was wondering if any1 can help me. I have an algorithm but dont understand how to go through it.
Here is an expression : s * (s a) * (s b * (s c)
This is the algorithm:
To test whether phrase is wellbracketed:
1. make bracketstack empty.
2. for each symbol sym in phrase (scanning from left to right),
repeat:
2.1. if sym is a left bracket:
2.1.1. add sym to the top of bracketstack.
2.2. if sym is a right bracket:
2.2.1. if bracketstack is empty, terminate with false.
2.2.2. remove a bracket from the top of bracketstack into
left.
2.2.3. if left and sym are not matched brackets, terminate
with false.
3. terminate with true if bracketstack is empty, or false otherwise
If some1 would help me that would be gr8

November 9th, 2011, 01:38 PM
#2
Re: Bracket matching algorithm
Isn't it overkill to use a stack? A counter should be enought.
Initially set the counter to zero. Scan the expression once looking for brackets. For each leftbracket increment the counter and for each rightbracket decrement it. If afterwards the counter is zero the brackets did match up.

November 9th, 2011, 01:54 PM
#3
Re: Bracket matching algorithm
Originally Posted by nuzzle
Isn't it overkill to use a stack? A counter should be enought.
Sure  as long as there's just one sort of bracket pairs like in the OP's sample. However, the algorithm obviously is designed to support more of them.
@ragha5: To me the description of the algorithm looks crystal clear, no idea what I might have to add to that. At any rate, here's a related thread that might provide some inspiration: http://www.codeguru.com/forum/showthread.php?t=507730
I was thrown out of college for cheating on the metaphysics exam; I looked into the soul of the boy sitting next to me.
This is a snakeskin jacket! And for me it's a symbol of my individuality, and my belief... in personal freedom.

November 9th, 2011, 07:45 PM
#4
Re: Bracket matching algorithm
i should have phrased my question differently. i am new to algorithms, i dont understand how to go through it with the expression given. i dont need to implement in a program... just by hand. this is the one of many expression that i have to execute. if some1 can help me that would be gr8.

November 10th, 2011, 01:49 AM
#5
Re: Bracket matching algorithm
Well, what's the problem? Are you not familiar with how a stack works?
Anyway, in principle leftbrackets are pushed onto the stack until a rightbracket is found. Then a bracket is popped from the stack and compared with the rightbracket.
There are several possible error conditions that are checked along the way:
1. The stack is empty when a bracket is to be popped.
2. A popped bracket is not of the same kind as the rightbracket it's compared with.
3. The stack is not empty when the scan is finished.
If none of these errors occur the sequence is considered wellbracketed.
Last edited by nuzzle; November 10th, 2011 at 03:03 AM.
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
OnDemand Webinars (sponsored)
