This blog is under construction

Wednesday, 27 February 2013

Balancing The Expressions


Algorithm to find whether the given expression is balanced or not:
  1. Read one character at a time.
  2. If the input character is an open brace, then push it in to the stack.
  3. If the input character is a close brace and the stack has matching close brace in the stack, then pop the open brace from the stack.  Otherwise, its an unbalanced expression due to mismatched brace.
  4. If the input character is a close brace and the stack is empty, then display "missing open brace" error message.
  5. If we still have open braces left in our stack and there is no more input to process, then report error message as missing close brace.
  6. If we are done processing all the inputs and we don't have any data left in our stack, then the given expression is a balanced expression.


Example For Imbalanced Expression:
expression: (a + b}
input: (
Input is open brace.  So, push it into the stack.

|     |
|  (  |
 -----

Skip the inputs a, +  and b.
input: }
We don't have matching open brace in the stack.  So, the given expression is an imbalanced expression.
|    |
| (  |
 ----

Example For Balanced Expression:
expression: (a + b)
input: (
Input is open brace.  So, push it into the stack.

|     |
|  (  |
 -----

Skip the inputs a, +  and b.
input: )
We have matching open brace in the stack.  So, the given expression is a balanced expression.
|    |
| (  |
 -----

See Also:
C Program To Implement Postfix To Infix Conversion
C Program To Implement Postfix To Prefix Conversion
C Program To Implement Infix To Prefix Conversion
C Program To Implement Infix To Postfix Conversion
How To Evaluate Postfix Expressions
C Program To Evaluate Postfix Expression Using Array
C Program To Evaluate Postfix Expression Using Linked List
How To Balance The Given Expressions
C Program For Balancing Expressions Using Array
C Program For Balancing Expressions Using Linked List


No comments:

Post a Comment