January 26, 2023

Parenthesis matching using stack

Parenthesis matching algorithm

PARENTHESIS_MATCHING (EQ, VALID)
This algorithm checks whether the expression EQ written in infix notation is valid or not and assigns TRUE or FALSE to VALID.


1. Scan EQ from left to right until the end of the equation is encountered:
2.     If”(“is encountered then: put it in the STACK.
3.     If the closing bracket is encountered then:
              (a) If STACK is empty, then Set VALID: = FALSE and return.
              (b) Pop the “(” from the STACK.
        [End of If structure.]
    [End of Step 2 loop.]
4. If STACK is empty, then:
       Set VALID := TRUE
7. Else:
      Set VALID := FALSE

    [End of If structure.]

8. Return


Leave a Reply