时间戳

首页 > 解决方案 > 验证 Pre-Order Binary Search Tree 表达式的语法

java - 验证 Pre-Order Binary Search Tree 表达式的语法

问题描述

嘿伙计们，对于一个作业，我必须在用户输入的有序二叉搜索树表达式中读取如下：“（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();
}

标签： java

解决方案

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

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

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

然后你的解析器实际上应该构造一棵树。这显然是一个递归函数可以做到这一点。当函数的最顶层调用消耗所有输入时，整个字符串都是正确的。

推荐阅读