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