Арифметические выражения: анатомия, разбор, программирование::Журнал СА 10.2013
www.samag.ru
     
Поиск   
              
 www.samag.ru    Web  0 товаров , сумма 0 руб.
E-mail
Пароль  
 Запомнить меня
Регистрация | Забыли пароль?
О журнале
Журнал «БИТ»
Подписка
Где купить
Авторам
Рекламодателям
Магазин
Архив номеров
Вакансии
Контакты
   

ЭКСПЕРТНАЯ СЕССИЯ 2019


  Опросы

Какие курсы вы бы выбрали для себя?  

Очные
Онлайновые
Платные
Бесплатные
Я и так все знаю

 Читать далее...

1001 и 1 книга  
28.05.2019г.
Просмотров: 1321
Комментарии: 2
Анализ вредоносных программ

 Читать далее...

28.05.2019г.
Просмотров: 1426
Комментарии: 1
Микросервисы и контейнеры Docker

 Читать далее...

28.05.2019г.
Просмотров: 1099
Комментарии: 0
Django 2 в примерах

 Читать далее...

28.05.2019г.
Просмотров: 850
Комментарии: 0
Введение в анализ алгоритмов

 Читать далее...

27.03.2019г.
Просмотров: 1438
Комментарии: 0
Arduino Uno и Raspberry Pi 3: от схемотехники к интернету вещей

 Читать далее...

Друзья сайта  

Форум системных администраторов  

sysadmins.ru

 Арифметические выражения: анатомия, разбор, программирование

Архив номеров / 2013 / Выпуск №10 (131) / Арифметические выражения: анатомия, разбор, программирование

Рубрика: Разработка /  Кафедра   | Дополнительные материалы

Алексей Вторников АЛЕКСЕЙ ВТОРНИКОВ, разработчик ПО для банков и страховых компаний (хотя не отказывается от интересных задач в других областях). Основной «недостаток» – предпочитает командную строку любым IDE

Арифметические выражения:
анатомия, разбор, программирование

Недостойно одаренному человеку тратить, подобно рабу, часы на вычисления.

Готфрид В.Лейбниц

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

Что есть сейчас

Во многих языках программирования предусмотрены конструкции для вычисления арифметических выражений. Например, в 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.


Комментарии отсутствуют

Добавить комментарий

Комментарии могут оставлять только зарегистрированные пользователи

               Copyright © Системный администратор

Яндекс.Метрика
Tel.: (499) 277-12-41
Fax: (499) 277-12-45
E-mail: sa@samag.ru