dcsimg
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 5 of 5

Thread: Bracket matching algorithm

  1. #1
    Join Date
    Nov 2011
    Posts
    2

    Question Bracket matching algorithm

    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…

  2. #2
    Join Date
    May 2009
    Posts
    2,413

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

  3. #3
    Join Date
    Jun 2010
    Location
    Germany
    Posts
    2,675

    Re: Bracket matching algorithm

    Quote Originally Posted by nuzzle View Post
    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.

  4. #4
    Join Date
    Nov 2011
    Posts
    2

    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.

  5. #5
    Join Date
    May 2009
    Posts
    2,413

    Re: Bracket matching algorithm

    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.
    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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)