Algorithm to find whether the given expression is balanced or not:
- Read one character at a time.
- If the input character is an open brace, then push it in to the stack.
- 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.
- If the input character is a close brace and the stack is empty, then display "missing open brace" error message.
- 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.
- 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