How can stacks be used for checking balancing of symbols?

Stacks can be used to check if the given expression has balanced symbols or not. The algorithm is very much useful in compilers. Each time parser reads one character at a time. If the character is an opening delimiter like ‘(‘ , ‘{‘ or ‘[‘ then it is PUSHED in to the stack. When a closing delimiter is encountered like ‘)’ , ‘}’ or ‘]’ is encountered, the stack is popped. The opening and closing delimiter are then compared. If they match, the parsing of the string continues. If they do not match, the parser indicates that there is an error on the line. A linear time O(n) algorithm based on stack can be given as:-

• Create a stack.
• while ( end of input is not reached ) {
  • If the character read is not a symbol to be balanced, ignore it.
  • If the character is an opening delimiter like ( , {  or [ , PUSH it into the stack.
  • If it is a closing symbol like ) , } , ] , then if the stack is empty report an error, otherwise POP the stack.
  • If the symbol POP-ed is not the corresponding delimiter, report an error.
• At the end of the input, if the stack is not empty report an error.

Examples:

For tracing the algorithm let us assume that the input is () (() [()])