Parenthesis Matching with a Stack

A well know problem in the parsing of mathematical expressions and other special file formats such as Newick files( in Bioinformatics) is parenthesis matching, ie making sure they are nested properly.   For example (), (()), ((()))()(()) are examples of strings of parenthesis that are properly nested.  Here are some that are not,  ()),  ))((,  ()()).

Our problem is to read in a string of parenthesis and check to see if it is correct.  This is in fact quite easy if we use a stack.   Here is the general algorith.

Algorithm for parenthesis matching

  • We process the string from left to right one character at a time
  • Whenever we see a opening parenthesis, we push it on stack.
  • When we see closing parenthesis, we check what is at the top of the stack, if we have corresponding parenthesis, we pop it from the top of the stack.  Note that at anytime the stack may be empty and popping an empty stack creates an error.  Consequently we need to check to see if the stack is empty BEFORE popping.  If empty early return false.
  • If parenthesis at the top of the stack is not corresponding opening parenthesis, we return false, as there is no point check the string further.
  • Again, when we reach at end of the string, we need to check if stack is empty or not. If the stack is empty, we are good. If stack is not empty, parenthesis do not match.

The complexity is of course O(n)

Here is some example code

// Class, How do you modify the following if we add [] and{} to ()
// and match things like {(){}(())[]}
bool ParenOK(string str) {
 stack<char> stk;
 char c;
 for (unsigned int i = 0; i < str.length(); i++) {
    c = str[i];
    if (c == '(')
       stk.push(c);
    else if ((c == ')') && (!stk.empty()) && (stk.top() == '('))
              stk.pop();
         else {
              return false;
         }
    }
   return (stk.empty());
}

Question 1: How would you modify the above to allow {} and []  as well as () in your string.  In other words check things like   []{}(()){()()}  to see if everything is nested correctly.

Question 2: How would you modify the above code to check a Newick file say,

(A:0.1,B:0.2,(C:0.3,D:0.4):0.5)

 

Comments are closed.