Рекурсивно проверять, является ли строка допустимым выражением префикса? - PullRequest
Новая
       16

Рекурсивно проверять, является ли строка допустимым выражением префикса?

2 голосов
/ 12 октября 2011

Я довольно новичок в сообществе, но я видел несколько полезных постов здесь, поэтому я подумал, что спросить.

У меня есть домашний вопрос, в котором нас просят рекурсивно проверить, является ли данная строка действительным префиксным выражением, заданным двумя следующими правилами (стандартными):

  1. Переменные (a-z) являются префиксными выражениями
  2. Если O - бинарный оператор, а F и E - префиксные выражения, OFE

Теперь я как бы получаю оценку и смотрю на алгоритмы префикса в инфикс, но пока не могу понять, как реализовать только методы оценки (поскольку мне нужно только проверить, это действительно так, например, не + ab).

Я знаю, что большая часть реализации для этих проблем выполняется с использованием стеков, но я не понимаю, как бы я делал это рекурсивно здесь ... некоторая помощь была бы чрезвычайно признательна.

Ответы [ 2 ]

3 голосов
/ 12 октября 2011

Думайте об этом так. (Я не собираюсь писать код, потому что это то, что вам нужно учиться).

Вы хотите проверить, является ли определенная строка выражением префикса, поэтому у вас есть функция: 

boolean isPrefix(string)

Теперь есть два способа, которыми эта строка может быть префиксом:

  1. Это персонаж из a-z
  2. Это в формате O (префикс) (префикс)

Итак, во-первых, вы проверяете, имеет ли строка длину один и находится ли он между a-z, и если да, то ответ - да.

Далее вы можете проверить, начинается ли строка с O. Если это так, вам нужно проверить оставшуюся часть строки, чтобы увидеть, состоит ли она из двух выражений префикса (FE).

Итак, вы начинаете итерацию от 1 до длины и передаете каждую подстроку (0-> i, i-> length) в isPrefix (). Если обе подстроки также являются допустимыми префиксными выражениями, ответ - да.

В противном случае ответ - нет.

Это в значительной степени так, но реализация, однако, зависит от вас.

0 голосов
/ 12 октября 2011

Я не уверен, что полностью понимаю смысл этого, но я думаю, что у вас должен быть какой-то метод, например checkPrefixIn(String s), который просматривает только часть данного String, возвращает true, если это только префикс, false, если это только оператор (или недопустимый символ), или возвращаемое значение checkPrefixIn(partOfS), где partOfS является подстрокой ввода s

...