Given a string expression, check whether it is balanced.
- key point:
- last unclosed should be closed first
- approaches
- stack is one approach
- squeeze with two cursors
// My solution with O(n)
// [] {} () should be balanced in an expression
var parenthesis = ['(',')','{','}','[',']'];
var expression = 'ddd{[([a+++{}+]ddddb)]}';
// Make use of two cursors leftIndex and rightIndex, to get closer to the center gradually
var balancedParenthesis = function(){
var i=0;
var j=expression.length-1;
var res = true;
while(i<=j){
var leftIndex = parenthesis.indexOf(expression[i]);
if(leftIndex !== -1){
var rightIndex = parenthesis.indexOf(expression[j]);
if(rightIndex !== -1){
// ')(' this is not balanced
if(rightIndex-leftIndex==1){
// continue
// rightIndex = -1;
// leftIndex = -1;
i++;
j--;
}else{
// Q: how to give the error index in the unbalanced expression
res = false;
break;
}
}else{
j--;
}
}else{
i++;
}
}
return res;
}
console.log(balancedParenthesis(expression));
