预序二叉搜索树表达式的java验证语法

huwehgph  于 2021-07-06  发布在  Java
关注(0)|答案(1)|浏览(210)

嘿,伙计们,对于一个赋值,我必须读入一个按顺序排列的二叉搜索树表达式:“(a(g))”,其中“a”是根,“g”是“a”的左子级。我一直在努力确保语法正确。例如,如果输入(a(g),则语法不正确,因为“a”没有右右括号。同样地,如果输入(ab(g))也是不正确的,因为每对括号只能有一个字母数字字符。我有验证括号正确数量的代码,但我一直在努力确保每对括号只包含一个字母数字字符。这就是我目前所拥有的。谢谢你的帮助/建议!

public static boolean balancedTree(String s) throws InvalidTreeSyntax {
    Stack<Character> stack = new Stack<Character>();
    for (int i = 0; i < s.length(); i ++) {
        char c = s.charAt(i);
        if (c == '(') {

            stack.push(c);

        } else if (c == ')') {
            if (stack.isEmpty() || stack.pop() != '(') { 

                return false;
            }
        }
    }
    return stack.isEmpty();
}
k3bvogb1

k3bvogb11#

首先需要确保您知道语法是什么:

tree: /* empty */
        | '(' letter tree tree ')'

    letter: 'a' | 'b' | ... | 'z'

然后解析器应该实际构造一棵树。很明显,这是一个递归函数。当函数的最顶层调用使用所有输入时,整个字符串是正确的。

相关问题