Постфиксная валидация записи?

Question

Каким будет хороший способ оценить строку (массив, что-то), которая содержит выражение постфикса (например: 35 +), чтобы проверить на достоверность?

Answer 1

Здесь я предполагаю, что вы подразумеваете под valid то, что выполнение кода никогда не опустошит стек и оставит одно значение в стеке. Если у вас есть более строгое понятие валидности, вам понадобится более сложная проверка.

Если вы хотите проверить правильность такого типа, нет необходимости оценивать строку, и вы можете использовать счетчик , а не стек. Счетчик отслеживает количество значений, которые будут в стеке, если вы оценили. Для упрощения предположим, что у вас есть только литералы, бинарные операторы и унарные операторы. Этот алгоритм использует специальную операцию декремент : если при уменьшении счетчик становится меньше нуля, строка недопустима:

1. Инициализировать счетчик на 0.
2. Когда вы видите литерал, увеличивайте счетчик.
3. Когда вы видите бинарный оператор, уменьшите счетчик дважды, затем увеличьте его.
4. Когда вы видите унарный оператор, уменьшите счетчик, затем увеличьте его.
5. В конце строки, если счетчик равен 1, и если он никогда не опускался ниже 0, строка действительна.

Answer 2

Постфиксное выражение допустимо тогда и только тогда, когда:

1) Первые два элемента являются операндами (значениями), а

2) Последний элемент является оператором, а

3) Для каждого n значений существует n-1 оператор (ы), и

4) В списке из n элементов, начиная с индекса i = 0 для i 1), следует ( к-1) операторы. Когда k = 1, число следующих операторов = k = 1.

Answer 3

Алгоритм: поддерживать стек и сканировать постфиксное выражение слева направо - Если элемент является числом, вставьте его в стек - Если элемент является оператором O, поп дважды и получите A и B соответственно. подсчитывать Боа и толкнуть его обратно в стек - Когда выражение заканчивается, число в стеке есть окончательный ответ

// Для достоверности Если у вас осталось только одно число в стеке, его правильное выражение

// Если у вас осталось более одного числа в стеке и нет оператора, то это неправильно

// Если у вас один или нет числа в стеке и оставлены операторы, то это неправильно

Answer 4

Чтобы проверить, является ли выражение постфикса допустимым или нет: (если входные данные находятся в массиве char) 1. Количество операндов должно быть равно нет. операторов + 1. Для проверки сохраните контрольную переменную. проверить = 0. Увеличивайте это для каждого операнда и уменьшайте для каждого оператора. Если, наконец, его значение равно 1, то выражение допустимо.

2. Первые 2 элемента массива должны быть операндами. Никакое постфиксное выражение не может иметь оператор в качестве 1-го или 2-го элемента. Проверьте это с помощью оператора управления.