Parentheses' Check

PROBLEM STATEMENT :
A mathematical expression will be inputted as a string. We need to check where the mathematical string is properly parenthesized. This includes checking for 2 conditions :

1. Every opening parenthesis should have a similar closing parenthesis.
2.  The order of the opening and closing of parentheses should be correct i.e. the parenthesis to open last should be closed first.

A correct expression would be ( { [x+y*z] [x+y] } )
An incorrect expression would be something like { [x+y} ]

NOTE : We are not interested in the variable expression within the parentheses. As long the expression is correctly parenthesized, we need not encumber ourselves with the underlying variables and their relations.

ALGORITHM : 
For rule no.1, we need to establish concurrency between the symbols i.e. we need to have a '}' for every '{' only. '}' doesn't correspond to '['. And since according to rule no.2, the last parenthesis to be opened should be the first to be closed, we use a LIFO kind of data structure: a stack.

We scan the expression from left to right character by character. Whenever we encounter an opening parenthesis, we push it into a stack. Whenever we find a closing parenthesis, we compare it with the top of the stack and if the correspondence relation holds true, we pop the stack. We ignore all other characters.

The java code that follows the above algorithm is given in the form of a Gist below :
Each of the routines push, pop and checkForParentheses takes O(1) time. Thus, for a n-character long string, the main function takes O(n) time, ignoring the overheads for calling a function. 

Thus we see another important application of the data structure stack. Parentheses check is an important routine in expression-checking as well as expression-evaluation.