Home Misc How can stacks be used for checking balancing of symbols?

How can stacks be used for checking balancing of symbols?

by nikoo28
0 comment

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:

EXAMPLE Valid? Description
(A+B) + (C-D) Yes The expression is having balanced symbol
((A+B) + (C-D) No One closing brace is missing.
((A+B) + [C-D]) Yes Opening and closing braces correspond
((A+B) + [C-D]] No The last brace does not correspond with the first opening brace.

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

Input Symbol Operation Stack Output
( Push ( (
) Pop (
Test if ( and A[i] match? YES
( Push ( (
( Push ( ( (
) Pop (
Test if ( and A[i] match? YES
(
[ Push [ ( [
( Push ( ( [ (
) Pop )
Test if ( and A[i] match? YES
( [
] Pop [
Test if [ and A[i] match? YES
(
) Pop (
Test if ( and A[i] match? YES
Test if Stack is Empty? YES TRUE

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More