Анализатор выражений Lisp в Java (используя только один стек)
Я пытаюсь реализовать простой оценщик выражений Lisp с использованием Java. На самом деле существует множество информации по этому вопросу, но, похоже, все они используют два отдельных стека для получения результата. Мне интересно, возможно ли реализовать такую программу, используя только один стек и как может выглядеть какой-то псевдокод для этого.
Благодарю.
Для получения дополнительной информации о чем я говорю, обратитесь к
2 ответа
Оба интерпретатора, с которыми вы связались, делают очень важное предположение: что +, -, * и т. Д. Являются двоичными функциями, то есть они всегда принимают ровно два аргумента. В реальном Лиспе можно сказать (+ 1 2 3 4 5) суммировать кучу чисел. Но, если вы готовы принять упрощающее предположение, что арность каждого оператора известна, то вы определенно можете сделать это только с одним стеком. Ключ: переверните стопку вверх дном.
У переводчиков, с которыми вы связаны, есть стеки:
дно -> ( + ( - 2 1 ) 4 ) <- top (мы нажимаем и высовываемся отсюда)
Но вы также можете прочитать выражение назад и справа и построить стек следующим образом:
верх -> ( + ( - 2 1 ) 4 ) <- низ
Тогда вы по сути получите RPN, обратная польская запись. RPN очень хорошо играет со стеками.
Алгоритм такой:
- Если вы видите круглые скобки, игнорируйте их
- Если вы видите операнд, поместите его в стек
- Если вы видите оператора, вызовите его. Оператор выскакивает столько значений, сколько ему нужно, а затем помещает свой результат в стек
Взять, к примеру, ( + ( - 2 1 ) 4 ), Вот как алгоритм будет работать:
Стек: пусто Чтение: ) Действие: скобки игнорируются. Оставил: ( + ( - 2 1 ) 4
Стек: пусто Чтение: 4 Действие: операнд помещен в стек. Оставил: ( + ( - 2 1 )
Стек: 4 Чтение: ) Действие: скобки игнорируются. Оставил: ( + ( - 2 1
Стек: 4 Чтение: 1 Действие: операнд помещен в стек. Оставил: ( + ( - 2
Стек: 1 4 Чтение: 2 Действие: операнд помещен в стек. Оставил: ( + ( -
Стек: 2 1 4 Чтение: -Действие: оператор вызван. Это вытолкнет 2 и 1 из стека, а затем нажмите 2-1=1 на него. Оставил: ( + (
Стек: 1 4 Чтение: ( Действие: скобки игнорируются. Оставил: ( +
Стек: 1 4 Чтение: + Действие: оператор вызван. Это вытолкнет 1 и 4 из стека, а затем нажмите 1+4=5 на него. Оставил: (
Стек: 5 Чтение: ( Действие: скобки игнорируются. Слева: ничего
Готово! Результат 5, как и ожидалось.
PS про игнорирование скобок. Это будет работать идеально, если введенное вами выражение правильно сформировано, но оно может принимать некорректно сформированные выражения и придавать им бессмысленные значения. например (+ - + 1 2 3 4) интерпретируется как (+ (- (+ 1 2) 3) 4), Если вы хотите предотвратить такое поведение, просто поместите закрывающие скобки в стек. Когда приходит время вызывать оператор, извлекайте аргументы и добавьте один дополнительный токен. Убедитесь, что токен близкий друг, иначе выведите ошибку. Как только у вас будет результат, поместите его в стек. Убедитесь, что следующий токен, который вы прочитали, является открытым пареном, а затем отбросьте его.
PPS это все становится намного сложнее, если, как в реальном Лиспе, аргументы функций сами могут быть функциями. Тогда у вас нет удобного различия между оператором / операндом, на который опирается RPN, и вам нужно уделять больше внимания скобкам как элементам группировки. Я не уверен, что вы могли бы сделать полноценный оценщик выражений Lisp с переменной arity и functions-as-operands только с одним стеком.
Надеюсь, что это поможет вам калькулятор в стиле LISP без стека