java算法,问题如下?


问:假设有一字符串长度无穷大,内容只有 {} 六个。
结果:返回Boolean
规则: 必须成对出现,可以嵌套,但不能错位。如:
A = "{[()()[]{}] }...({[]}{}())" True
B = " {] {(){}[]}()}()}...((((){}[]" False 因:红色部分出现错位
要求:利用JAVA或JavaScript算法实现

算法 数据结构和算法

我看了电视 10 years, 2 months ago

利用栈可以做到。一个一个字符地看,遇到左括号就压栈,遇到右括号就判断栈顶元素是否为对应的左括号,如果对应,栈顶元素出栈,继续判断下一个字符;如果不对应,则配对错误,返回false。如果到最后一个字符也可以找到栈顶元素匹配,而且这时栈为空,则返回true,否则false。《数据结构》教材好像有,严蔚敏版。

这货是杯具 answered 10 years, 2 months ago


更新3:谢@brayden同学提醒,已经改正并简化了代码。


更新2:发现自己怎么这么热心,顺便把JavaScript版本也写了吧,放在最后。


更新1:下班回家重新整理了一下格式,原理正如楼下@DerrickChan同学所说,利用了栈的数据结构。

最近比较忙,如果需要JavaScript版本的话请告知。


来个Java的吧,提供个思路,想翻译成JavaScript也不难,就先不写了。

代码如下:

UnitTest.java


 public class UnitTest {
    public static void main(String[] args) {
        Checker checker = new Checker();
        String s1 = "{[()()[]{}]}({[]}{}())";
        String s2 = "{]{(){}[]}()}()}((((){}[]";
        System.out.println(checker.check(s1));
        System.out.println(checker.check(s2));
    }
}

Checker.java


 public class Checker {
    private char[][] css = { { '(', ')' }, { '[', ']' }, { '{', '}' } };
    private char[] cs = null;
    private char[] stack = null;
    private int index = 0;

    public boolean check(String s) {
        cs = s.toCharArray();
        stack = new char[cs.length];
        for (char c : cs)
            if (!isEndding(c))
                push(c);
            else if (!isPair(pop(), c))
                return false;
        if (index == 0)
            return true;
        index = 0;
        return false;
    }

    public void push(char c) {
        stack[index++] = c;
    }

    private char pop() {
        return index == 0 ? '\0' : stack[--index];
    }

    private boolean isEndding(char c) {
        for (int i = 0; i != css.length; ++i)
            if (c == css[i][1])
                return true;
        return false;
    }

    private boolean isPair(char c1, char c2) {
        for (int i = 0; i != css.length; ++i)
            if (c1 == css[i][0] && c2 == css[i][1])
                return true;
        return false;
    }
}

UnitTest.js


 var s1 = "{[()()[]{}]}({[]}{}())";
var s2 = "{]{(){}[]}()}()}((((){}[]";
var css = "()[]{}";
var stack = {};
var index = 0;
console.log(check(s1));
console.log(check(s2));

function check(cs) {
    for (var i = 0; i != cs.length; ++i) {
        var c = cs[i]
        if (!isEndding(c))
            push(c);
        else if (!isPair(pop(), c))
            return false;
    }
    if (index == 0) 
        return true;
    index = 0;
    return false;
}

function push(c) {
    stack[index++] = c;
}

function pop() {
    return index == 0 ? '\0' : stack[--index];
}

function isEndding(c) {
    console.log();
    for (var i = 0; i != css.length; i = i + 2)
        if (c == css[i + 1])
            return true;
    return false;
}

function isPair(c1, c2) {
    for (var i = 0; i != css.length; i = i + 2)
        if (c1 == css[i] && c2 == css[i + 1])
            return true;
    return false;
}

clouder answered 10 years, 2 months ago

Your Answer