Для установки нажмите кнопочку Установить расширение. И это всё.

Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.

4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день
и почти забыл как выглядит оригинальная Википедия.
Статистика
На русском, статей
Улучшено за 24 ч.
Добавлено за 24 ч.
Что мы делаем. Каждая страница проходит через несколько сотен совершенствующих техник. Совершенно та же Википедия. Только лучше.
.
Лео
Ньютон
Яркие
Мягкие

Алгоритм сортировочной станции

Из Википедии — свободной энциклопедии

Алгоритм сортировочной станции — способ разбора математических выражений, представленных в инфиксной нотации. Может быть использован для получения вывода в виде обратной польской нотации или в виде абстрактного синтаксического дерева. Алгоритм предложен Эдсгером Дейкстрой и назван им «алгоритм сортировочной станции», поскольку напоминает действие железнодорожной сортировочной станции.

Так же, как и вычисление значений выражений в обратной польской записи, алгоритм работает при помощи стека. Инфиксная запись математических выражений чаще всего используется людьми, её примеры: 2+4 и 3+6*(3-2). Для преобразования в обратную польскую нотацию используется 2 строки: входная и выходная, и стек для хранения операторов, еще не добавленных в выходную очередь. При преобразовании алгоритм считывает 1 символ и производит действия, зависящие от данного символа.

Энциклопедичный YouTube

  • 1/3
    Просмотров:
    371
    350
    1 084
  • Технология и управление станций и узлов. Лекция. Бородин А. Ф.
  • Разбор задачи 1352 acmp.ru Формирование поезда. Решение на C++
  • Видеолекция Имитационное моделирование транспортных процессов

Субтитры

Алгоритм

  • Пока не все токены обработаны:
  • Прочитать токен.
  • Если токен — число, то добавить его в очередь вывода.
  • Если токен — функция, то поместить его в стек.
  • Если токен — разделитель аргументов функции (например запятая):
  • Пока токен на вершине стека не открывающая скобка, перекладывать операторы из стека в выходную очередь. Если в стеке не было открывающей скобки, то в выражении пропущен разделитель аргументов функции (запятая), либо пропущена открывающая скобка.
  • Если токен — оператор op1, то:
  • Пока присутствует на вершине стека токен оператор op2, чей приоритет выше или равен приоритету op1, и при равенстве приоритетов op1 является левоассоциативным:
    • переложить op2 из стека в выходную очередь;
  • Положить op1 в стек.
  • Если токен — открывающая скобка, то положить его в стек.
  • Если токен — закрывающая скобка:
  • Пока токен на вершине стека не является открывающей скобкой, перекладывать операторы из стека в выходную очередь.
  • Выкинуть открывающую скобку из стека, но не добавлять в очередь вывода.
  • Если токен на вершине стека — функция, переложить её в выходную очередь.
  • Если стек закончился до того, как был встречен токен открывающая скобка, то в выражении пропущена скобка.
  • Если больше не осталось токенов на входе:
  • Пока есть токены операторы в стеке:
  • Если токен оператор на вершине стека — скобка, то в выражении присутствует незакрытая скобка.
  • Переложить оператор из стека в выходную очередь.
  • Конец.

Каждый токен-число, функция или оператор выводится только один раз, а также каждый токен-функция, оператор или круглая скобка будет добавлен и удален из стека по одному разу. Постоянное количество операций на токен, линейная сложность алгоритма O(n).

Ссылки

Эта страница в последний раз была отредактирована 2 мая 2021 в 07:19.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).