Разрабатываем парсер математических выражений
Автор: Meander
Дата: 5 апреля 2012 года
Как-то меня заинтересовала тема интерпретации строки символов, вводимой пользователем во время выполнения программы, как математического выражения. Порывшись в сети, нашел несколько книг по теории, несколько примеров исходников калькуляторов и т.д. Было обнаружено несколько фактов. Во-первых, все парсеры были рекурсивны, во-вторых, большинство реализовано на плохо знакомом мне Паскале и, наконец, представляли собой весьма необозримый код.
Тогда мной небыли обнаружены примеры простых парсеров Страуструпа и Шилдта, хотя и они достаточно громоздки. Однако, на сайте emaxx я наткнулся на простой и компактный парсер строки. Этот парсер работал с двумя стеками, осуществлял преобразование в обратную польскую нотацию и одновременно вычислял значение за время пропорциональное длине строки.
Мы будем искать в строке зарегистрированные последовательности символов. Зарегистрированные последовательности это, вообще говоря, единственно возможные под последовательности, которые априори можно встретить в строке. Числовые константы, ввиду их огромного разнообразия, нет смысла предопределять. Их достаточно просто обнаружить и определить, так как они состоят из цифр и символа разделителя целой и дробной частей. Поэтому, если мы не обнаружили вначале строки зарегистрированную лексему, возможно здесь число. Ну, а если и не число, значит в этом месте неизвестный символ.
Та строка, которую мы написали в окне редактирования, осмыслена с точки зрения синтаксиса, т.е. с нашей точки зрения. С точки зрения компьютера это случайный набор символов. С нашей точки зрения строка осмыслена, т.к. содержит последовательность лексем, а не символов. Поэтому и компьютер должен искать не символы, а лексемы.
Поиск лексем следует начинать с самых длинных в порядке уменьшения длины. Сначала ищем самую длинную, потом – на один символ короче и т.д. Это необходимо, чтобы избежать двусмысленной ситуации, когда некоторая последовательность символов, соответствующая короткой лексеме, входит целиком в начальный фрагмент длинной лексемы. Например, мы можем ввести символьную константу или переменную с именемsinus, но если вести поиск произвольно, или, начиная с коротких последовательностей, то возникнет ошибка: неизвестный аргументusфункцииsin.
Теперь следует определиться со способом поиска лексем входящих в состав строки. Если упорядочить набор библиотечных лексем в порядке уменьшения длины последовательности символов. Затем сравнивать последовательно наборы символов библиотечных лексем с начальным фрагментом строки той же длины. Но можно не упорядочивать совокупность библиотечных лексем по длине. Достаточно знать число символов в самой длинной лексеме, брать фрагмент строки соответствующей длины и сравнивать с последовательностями, имеющимися в библиотеке. В этом случае, если фрагмент не найден, берем последовательность на один символ короче (или убираем последний символ из, уже, набранной на предыдущем этапе) и повторяем поиск. Так дойдя до одного символа, и не найдя его, предполагаем, что вначале находится число. Если фрагмент обнаружен, то добавляем соответствующий элемент в виртуальную строку, а реальную строку укорачиваем на n первых символов (где n – это длина обнаруженного фрагмента). Затем повторяем все рекурсивно, пока не исчерпаем строку, либо не встретим ошибку.
Мы завершили рассмотрение вопроса о разборе строки на лексемы и формировании некоторого вектора (виртуальной строки) заполненного структурами, содержащими необходимые в дальнейшем атрибуты лексем.
Широкую группу синтаксических ошибок можно предупредить, рассмотрев случаи возможного и не возможного положения лексем в выражении.
Введем обозначения:
- “NVC” – числа, переменные, константы;
- “)” – закрывающие скобки;
- “(” – открывающие скобки;
- “BU” – операции бывающие либо унарными, либо бинарными;
- “B” – всегда бинарные операции;
- “U” – всегда унарные операции.
| Начало строки | Конец строки | ||
|---|---|---|---|
| Могут быть | Не могут быть | Могут быть | Не могут быть |
| “NVC” | “)” | “NVC” | “(” |
| “(” | “B” | “)” | “B” |
| “BU” | “U” | ||
| “U” | “BU” | ||
Теперь случаи промежуточного положения элементов перед текущей лексемой.
| Текущая лексема | “…” - может быть | “…” – не может быть |
|---|---|---|
| “…”“(” | “(”,“BU”,“U”,“B” | “NVC”,“)” |
| “…”“NVC” | “(”,“BU”,“U”,“B” | “NVC”,“)” |
| “…”“BU” | “(”,“BU”,“U”,“B”,“NVC” | любая допустима |
| “…”“B” | “NVC”,“)” | “(”,“BU”,“U”,“B” |
| “…”“U” | “(”,“BU”,“U”,“B” | “NVC”,“)” |
| “…”“)” | “NVC”,“)” | “(”,“BU”,“U”,“B” |
Оставлять комментарии могут только зарегистрированные пользователи.
Если вы не являетесь зарегистрированным пользователем, то вам необходимо зарегистрироваться. Регистрация бесплатна. Если вы уже зарегистрированы на CodeNet, то вам необходимо ввести логин и пароль в верхней (Alt-U) части страницы.
Источник: http://feedproxy.google.com/~r/codenet/read/~3/yAomH-BisX0/
|
Автор: MeanderДата: 5 апреля 2012 года Как-то меня заинтересовала тема интерпретации строки символов, вводимой пользователем во время выполнения программы, как математического выражения. Порывшись в |
РэдЛайн, создание сайта, заказать сайт, разработка сайтов, реклама в Интернете, продвижение, маркетинговые исследования, дизайн студия, веб дизайн, раскрутка сайта, создать сайт компании, сделать сайт, создание сайтов, изготовление сайта, обслуживание сайтов, изготовление сайтов, заказать интернет сайт, создать сайт, изготовить сайт, разработка сайта, web студия, создание веб сайта, поддержка сайта, сайт на заказ, сопровождение сайта, дизайн сайта, сайт под ключ, заказ сайта, реклама сайта, хостинг, регистрация доменов, хабаровск, краснодар, москва, комсомольск |
Дайджест новых статей по интернет-маркетингу на ваш email
Новые статьи и публикации
- 2024-04-17 » 23 сервиса для эффективного экспресс-аудита любого сайта
- 2024-04-08 » Яндекс переходит на новую версию Wordstat
- 2024-04-08 » Яндекс интегрировал в свой облачный сервис эмпатичную нейросеть
- 2024-04-08 » Новая версия нейросети Claude превзошла по мощности аналоги Google и OpenAI
- 2024-04-08 » Как пользоваться GPT 4 и Claude бесплатно и без VPN
- 2024-03-13 » Стратегии SEO на 2024 год
- 2024-03-13 » Как использовать анимацию с помощью JavaScript-библиотеки GSAP
- 2024-03-13 » Использование GSAP 3 для веб-анимации
- 2024-03-13 » Cогласование топографической съёмки с эксплуатирующими организациями
- 2024-02-19 » Теряются лиды? Как настроить сквозную аналитику
- 2024-02-17 » Мерч и IT: на что обратить внимание в 2024 году
- 2024-02-16 » Копируем с RSync: основные примеры синхронизации файлов
- 2024-02-15 » Лучшие noCode AI платформы для создания диалоговых ботов
- 2024-02-14 » Факторы ранжирования Google 2024 — исследование Semrush
- 2024-02-12 » Перенос сайта на другой хостинг
- 2024-02-05 » В России сформирован реестр хостинг-провайдеров
- 2024-02-04 » Использование SSH для подключения к удаленному серверу Ubuntu
- 2024-02-03 » Подключаемся к серверу за NAT при помощи туннеля SSH. Простая и понятная инструкция
- 2024-02-02 » Настройка CI/CD для Gitlab-репозитория: схемы и гайд по шагам
- 2024-02-01 » GitLab CI Pipeline. Запуск сценария через SSH на удаленном сервере
- 2024-01-29 » Introduction to GitLab’s CI/CD for Continuous Deployments
- 2024-01-26 » Настройка GitLab CI/CD
- 2024-01-25 » Установка shell gitlab runner
- 2024-01-25 » Установка и регистрация gitlab-runner в docker контейнере
- 2024-01-25 » Переменные Gitlab-Ci
- 2024-01-25 » Настройка CI/CD в GitLab для синхронизации проекта с веб-серверами
- 2024-01-25 » Копирование файлов scp
- 2024-01-21 » Бездепозитные бонусы от казино: обзор условий и правил использования
- 2024-01-18 » Современная обработка ошибок в PHP
- 2024-01-18 » Пример шаблона проектирования MVC в PHP
Гораздо больше людей сдавшихся, чем побежденных. |
Мы создаем сайты, которые работают! Профессионально обслуживаем и продвигаем их !
Как мы работаем
Заявка
Позвоните или оставьте заявку на сайте.
Консультация
Обсуждаем что именно Вам нужно и помогаем определить как это лучше сделать!
Договор
Заключаем договор на оказание услуг, в котором прописаны условия и обязанности обеих сторон.
Выполнение работ
Непосредственно оказание требующихся услуг и работ по вашему заданию.
Поддержка
Сдача выполненых работ, последующие корректировки и поддержка при необходимости.
Мы создаем практически любые сайты от продающих страниц до сложных, высоконагруженных и нестандартных веб приложений! Наши сайты это надежные маркетинговые инструменты для успеха Вашего бизнеса и увеличения вашей прибыли! Мы делаем красивые и максимально эффектные сайты по доступным ценам уже много лет!
Комплексный подход это не просто продвижение сайта, это целый комплекс мероприятий, который определяется целями и задачами поставленными перед сайтом и организацией, которая за этим стоит. Время однобоких методов в продвижении сайтов уже прошло, конкуренция слишком высока, чтобы была возможность расслабиться и получать \ удерживать клиентов из Интернета, просто сделав сайт и не занимаясь им...
Мы оказываем полный комплекс услуг по сопровождению сайта: информационному и техническому обслуживанию и развитию Интернет сайтов.
Контекстная реклама - это эффективный инструмент в интернет маркетинге, целью которого является увеличение продаж. Главный плюс контекстной рекламы заключается в том, что она работает избирательно.