Given a string expression, check whether it is balanced.

• key point:
  1. last unclosed should be closed first
• approaches
  1. stack is one approach
  2. 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));