Блог

Главная - Вопросы по программированию - Проверка синтаксиса выражения дерева двоичного поиска предварительного заказа

Проверка синтаксиса выражения дерева двоичного поиска предварительного заказа

#java

#java

Вопрос:

Привет, ребята, итак, для задания я должен прочитать в двоичном дереве поиска по порядку ввода пользователем выражение, подобное этому: «(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();
}

Комментарии:

1. Не могли бы вы предоставить больше тестовых примеров, тот, который вы указали в вопросе, имеет только один дочерний элемент. Как будут выглядеть входные данные, если у вас есть два дочерних элемента для a?

2. @RohanSharma Извините за это, в случае простого дерева с одним корнем и двумя дочерними элементами оно должно выглядеть следующим образом: (a (g) (b)) где ‘a’ — корень, а ‘g’ и ‘b’ — дочерние элементы. На данный момент я просто пытаюсь сделать это как можно проще.

3. Вы пробовали подход, при котором вы также помещаете алфавиты в свой стек, и когда вы сталкиваетесь с закрывающей скобкой, вы сначала вынимаете алфавит, а затем проверяете, есть ли у top открывающая скобка

4. Также рассмотрим, например, что у a нет ни одного правильного дочернего элемента, в этом случае входные данные выглядят так (a (g)) или так (a(g) ())?

5. @RohanSharma Привет, Рохан! Если дочернего элемента нет, и пользователь вводит пустую пару круглых скобок, это должно вызвать исключение.

Ответ №1:

Сначала вам нужно убедиться, что вы знаете, что это за синтаксис:

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

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

Тогда ваш анализатор должен фактически построить дерево. Очевидно, что это рекурсивная функция, которая это сделает. Вся строка верна, когда самый верхний вызов вашей функции потребляет все входные данные.

Метки: