CS201: Elementary Data Structures

One of the main applications of stacks in compilers is to determine whether delimiters in an input string or files are matched or not. As an example, consider the use of parentheses. A sequence of symbols involving parenthesis(), addition(+), multiplication(*), and integers is said to have "balanced parentheses" if each right (closing) parenthesis has a corresponding left (opening) parenthesis before it. For example, these expressions have balanced parentheses:

2*7          // no parenthesis - still balanced
(1+3)   
((2*16)+1)*(44+(17+9))

These following expressions do not have balanced parenthesis:

(44+38       // a left parenthesis with no right parenthesis
)            // a right parenthesis with no left parenthesis
(55+(12*11)  // missing a )   

This image demonstrates how stacks can be used for delimiter matching:

We can use a stack to store characters and do this matching.

1. Start with an empty stack.
2. For each left parenthesis, push left parenthesis.
3. For each right parenthesis, pop left parenthesis.
4. For each non-parenthesis character, do nothing.

The expression is balanced if the stack is empty and there are no more characters to process. It is not balanced if the stack is not empty after the last character (too many left parenthesis), or if the stack is empty and a right parenthesis still exists (a right without a left).

We can match multiple types of delimiters. For example, we might want to match (), [], and {}. In that case, we can push the left delimiter onto the stack and do a check when we pop, as in the following pseudocode:

if (next character is a right delimiter)
    then
        { if (stack is empty) then return false
else { 
    pop the stack if (right delimiter is corresponding version of what was popped off the stack) 
then
    continue processing
else
    return false } } 

Source: University of Delhi, http://vle.du.ac.in/mod/book/view.php?id=5686&chapterid=2407
 This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 2.5 India License.