 |
|
|
|
Арифметические выражения: анатомия, разбор, программирование
Арифметические выражения: Недостойно одаренному человеку тратить, подобно рабу, часы на вычисления. Готфрид В.Лейбниц Вне всяких сомнений, арифметические выражения поистине вездесущи. Алгоритмы их трансляции просты, по-своему изящны и универсальны. Знакомство с ними может сослужить добрую службу любому программисту Что есть сейчас Во многих языках программирования предусмотрены конструкции для вычисления арифметических выражений. Например, в JavaScript есть встроенная функция eval (), которой в качестве аргумента передается строка, содержащая выражение, команду или последовательность команд; следующий сценарий: <HTML> <HEAD> <TITLE>Арифметические выражения (функция eval ())</TITLE> </HEAD> <BODY> <SCRIPT LANGUAGE="JavaScript" TYPE="text/javascript"> document.write (eval ("(40 + 2) * 5")); </SCRIPT> </BODY> </HTML> отобразит в браузере ответ: 210. Сходная функция имеется также в PHP, Perl и многих других интерпретируемых языках. В языке программирования Java (начиная с версии 6) добавлена похожая функциональность: import javax.script.ScriptEngineManager; import javax.script.ScriptEngine;
public class Test { public static void main (String[] args) { ScriptEngineManager mgr = new ScriptEngineManager (); ScriptEngine engine = mgr.getEngineByName ("JavaScript"); try { System.out.println(engine.eval ("(40 + 2) * 5")); } catch (Exception ex) { ex.printStackTrace (); } } } Нетрудно видеть, что здесь производятся вызов интерпретатора JavaScript и передача ему в качестве аргумента строки, представляющей собой арифметическое выражение. Но как такие выражения фактически вычисляются? Это отнюдь неочевидно, и в этой статье я расскажу, что происходит «за кулисами». Для начала небольшое напоминание о том, что такое стек. Стек: главный герой В своей знаменитой книге «Искусство программирования» (см. любое издание) Дональд Э.Кнут приводит следующее определение: «Стек – это линейный список, в котором все операции вставки и удаления (и, как правило, операции доступа к данным) выполняются только на одном из концов списка». Иными словами, стек – это память, доступ к элементам которой организован по принципу «последним вошел, первым вышел» (или LIFO, от англ. Last In First Out). Стек представляет собой упорядоченную структуру данных, состоящую из отдельных элементов (ячеек). Элементы служат местом хранения данных. Данные, хранящиеся в элементах стека, могут быть любыми: числами, символами или иными более сложными структурами; это определятся назначением стека и способом его реализации. У стека имеется дно – место, начиная с которого в нем накапливаются элементы; очевидно, что в пустом стеке нет ни одного элемента. Новый элемент всегда помещается (синонимы – проталкивается, заносится; соответствующий англ. термин push) на место, указываемое вершиной стека; ранее имевшиеся данные утапливаются вглубь. Вместо термина «вершина» часто используется термин «голова». Удаление (синонимы – выталкивание, снятие; соответствующий англ. термин pop) элемента производится в обратном порядке начиная с того, на который указывает голова стека. Количество элементов, находящихся в стеке в данный момент времени, характеризует его глубину; очевидно, что глубина пустого стека равна 0. Глубина может быть ограничена наперед заданной величиной или быть неограниченной. Разумеется, на практике даже самый большой стек рано или поздно заполнится, и вся выделенная ему память будет занята. Такая ситуация называется переполнением стека (overflow). С другой стороны, возможна и противоположная ситуация (underflow), то есть попытка выборки из пустого стека. Качественная реализация стека должна «уметь» обрабатывать и предотвращать эти ситуации. План действий Обработка всякого арифметического выражения разбивается на три последовательных этапа:
Первые два этапа коротко называются трансляцией выражения. Вообще алгоритмы, лежащие в основе трансляции арифметических выражений, служат основой трансляции многих других конструкций языков программирования. В примерах программного кода используется язык программирования Java (версии 6 и старше). Я рекомендую скачать исходный код (он невелик – чуть больше 300 строк) и, читая статью, сверяться с ним. Статью целиком читайте в журнале «Системный администратор», №10 за 2013 г. на страницах 68-73. |
АЛЕКСЕЙ ВТОРНИКОВ,Комментарии отсутствуют
| Добавить комментарий |
|
Комментарии могут оставлять только зарегистрированные пользователи |
|
