Bracket matching algorithm

[ragha5]

Hey... I was wondering if any1 can help me. I have an algorithm but don’t 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 well-bracketed:
1. make bracket-stack 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 bracket-stack.
2.2. if sym is a right bracket:
2.2.1. if bracket-stack is empty, terminate with false.
2.2.2. remove a bracket from the top of bracket-stack into
left.
2.2.3. if left and sym are not matched brackets, terminate
with false.
3. terminate with true if bracket-stack is empty, or false otherwise


If some1 would help me that would be gr8…

[nuzzle]

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 left-bracket increment the counter and for each right-bracket decrement it. If afterwards the counter is zero the brackets did match up.

[Eri523]

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

[ragha5]

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.

[nuzzle]

Well, what's the problem? Are you not familiar with how a stack works?

Anyway, in principle left-brackets are pushed onto the stack until a right-bracket is found. Then a bracket is popped from the stack and compared with the right-bracket.

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 right-bracket 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 well-bracketed.