批处理之家's Archiver

523066680 发表于 2017-9-6 17:30

[JS]分享一段代码,通过"栈"判断多重括号是否配对

代码来自《learninng javascript data structures and algorithms》[code]
function matches(open, close)
{
    var opens = "([{",
        closers = ")]}";
    return opens.indexOf(open) == closers.indexOf(close);
}

function parenthesesChecker(symbols)
{
    var stack = new Stack();
    var balanced = true;
    var index = 0;
    var symbol, top;

    while (index < symbols.length && balanced)
    {
        symbol = symbols.charAt(index);
        if (symbol == '(' || symbol == '[' || symbol == '{')
        {
            stack.push(symbol);
        }
        else
        {
            if (stack.isEmpty())
            {
                balanced = false;
            }
            else
            {
                top = stack.pop();
                if ( !matches(top, symbol) )
                {
                    balanced = false;
                }
            }
        }

        index++;
    }

    if (balanced && stack.isEmpty())
    {
        return true;
    }
   
    return false;
}

console.log(parenthesesChecker('{{([][])}()}'));
console.log(parenthesesChecker('[{()]'));


function Stack()
{
    var items = [];

    this.push = function(element) { items.push(element); };

    this.pop = function() { return items.pop(); };

    this.peek = function() { return items[items.length-1]; };

    this.isEmpty = function() { return items.length == 0; };

    this.size = function() { return items.length; };

    this.clear = function() { items = []; };

    this.print = function() { console.log(items.toString()); };

    this.toString = function() { return items.toString(); };
}[/code]

523066680 发表于 2017-9-6 17:38

[i=s] 本帖最后由 523066680 于 2017-9-6 17:44 编辑 [/i]

虽然可以直接通过 数组 push 和 pop 直接实现。
但 js 实现的这个"栈"还是有点意思。

页: [1]

Powered by Discuz! Archiver 7.2  © 2001-2009 Comsenz Inc.