Tuesday, September 10, 2013

Checking whether the paranthesis are balanced in the expression

Problem
 Checking whether the paranthesis are balanced in the expression

Solution
Method 1 - Using stacks
Stacks can be used to compare the paranthesis.  Whenever we find the opening paranthesis we push it in the stack, and whenever we find closing paranthesis, we pop it out from stack. When the expression finishes and stack is not empty, then it means that paranthesis are not balanced otherwise they are.

Example 1
Consider the following expression {([])}
Example 2


Example 3


Example 4



Pseudocode
Algorithm checkBalance(expression)
// Returns true if the parentheses, brackets, 
    and braces in an expression are paired correctly.
isBalanced = true
while ( (isBalanced == true) and not at end of expression)
{ nextCharacter = next character in expression
 switch (nextCharacter)
 { case '(': case '[': case '{':
   Push nextCharacter onto stack
   break
  case ')': case ']': case '}':
   if (stack is empty)  isBalanced = false
   else
   { openDelimiter = top of stack
    Pop stack
    isBalanced = true or false according to whether openDelimiter and
     nextCharacter are a pair of delimiters
   }
   break
 }
}
if (stack is not empty)  isBalanced = false
return isBalanced

Thanks

0 comments:

Post a Comment