Разрабатываем парсер математических выражений
Автор: 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
Новые статьи и публикации
- 2026-07-10 » Корпоративный сайт, который показывает масштаб компании, укрепляет доверие и ведет клиента к целевому действию
- 2026-07-10 » Сайт бронирования, который превращает интерес клиента в прямую бронь, запись или заявку
- 2026-07-10 » Образовательный сайт под ключ
- 2026-07-03 » Аналитика нового поколения: как Яндекс Метрика превращает данные в управляемые конверсии
- 2026-07-03 » Прорыв в инфлюенс-маркетинге: Яндекс Директ научился оптимизировать рекламу в Telegram и MAX под реальные продажи
- 2026-07-03 » Нейросетевой дуэт: как Gorgona и Argus меняют правила игры в контекстной рекламе Яндекса
- 2026-07-03 » Рекламная революция в «Яндекс Директе»: с 14 июля текстово-графические объявления окончательно уступают место комбинаторным
- 2026-07-03 » Макс запустил тест комментариев в публичных каналах
- 2026-07-01 » Уникальность текста: когда копировать контент можно, а когда нельзя
- 2026-07-01 » Локальный поиск в 2026 году: как алгоритмы ранжируют бизнес
- 2026-07-01 » ПромоСтраницы Яндекса: инструмент, который меняет правила игры в контент-маркетинге
- 2026-07-01 » Контент для строительных компаний: какими текстами наполнить сайт, чтобы он приносил клиентов
- 2026-07-01 » Искусство диалога с ИИ: как составить промпт, чтобы нейросеть поняла вас с полуслова
- 2026-06-26 » Новый виток эффективности: товарные объявления в Директе теперь работают на ретаргетинг мобильных приложений
- 2026-06-26 » Характеристики товаров в Товарной галерее Яндекса: как одна деталь увеличивает продажи на 4%
- 2026-06-26 » Новая реальность контент-маркетинга: треть цитируемых ChatGPT страниц невидимы для Google
- 2026-06-26 » Конец текстово-графических объявлений: Яндекс Директ переводит ЕПК на комбинаторный формат
- 2026-06-26 » Конец эпохи: Google окончательно отключает блокировщики рекламы в Chrome
- 2026-06-10 » Новые штрафы за неисполнение правил авторизации
- 2026-06-10 » Новая реальность: MAX под прицелом
- 2026-06-10 » Банки и операторов связи обяжут компенсировать похищенное мошенниками
- 2026-06-10 » Что такое «белый VPN» и чем он отличается от обычного?
- 2026-06-10 » Когда ИИ придумывает «факты»: анатомия кризиса вымышленной статистики
- 2026-06-10 » Автостратегии Яндекс.Директа: стоит ли использовать в 2026 году
- 2026-06-10 » SMM в 2026: от охватов к доверию — полный гид по стратегии
- 2026-06-10 » Яндекс.Директ вышел на новый уровень: теперь реклама в каналах «Макса» с точным таргетингом
- 2026-06-10 » РСЯ с 1 июля прекращает сотрудничество с партнерами-физлицами: что делать, чтобы не потерять доход
- 2026-06-10 » Макс становится супераппом: бесконтактная оплата через СБП в несколько секунд
- 2026-06-05 » Как Яндекс передал площадкам управление собственным контентом
- 2026-06-05 » Как создавать гайды и инструкции с помощью нейросетей
Одного яйца два раза не высидишь. К. Прутков |
Мы создаем сайты, которые работают! Профессионально обслуживаем и продвигаем их !
Как мы работаем
Заявка
Позвоните или оставьте заявку на сайте.
Консультация
Обсуждаем что именно Вам нужно и помогаем определить как это лучше сделать!
Договор
Заключаем договор на оказание услуг, в котором прописаны условия и обязанности обеих сторон.
Выполнение работ
Непосредственно оказание требующихся услуг и работ по вашему заданию.
Поддержка
Сдача выполненых работ, последующие корректировки и поддержка при необходимости.
Мы создаем практически любые сайты от продающих страниц до сложных, высоконагруженных и нестандартных веб приложений! Наши сайты это надежные маркетинговые инструменты для успеха Вашего бизнеса и увеличения вашей прибыли! Мы делаем красивые и максимально эффектные сайты по доступным ценам уже много лет!
Комплексный подход это не просто продвижение сайта, это целый комплекс мероприятий, который определяется целями и задачами поставленными перед сайтом и организацией, которая за этим стоит. Время однобоких методов в продвижении сайтов уже прошло, конкуренция слишком высока, чтобы была возможность расслабиться и получать \ удерживать клиентов из Интернета, просто сделав сайт и не занимаясь им...
Мы оказываем полный комплекс услуг по сопровождению сайта: информационному и техническому обслуживанию и развитию Интернет сайтов.
Контекстная реклама - это эффективный инструмент в интернет маркетинге, целью которого является увеличение продаж. Главный плюс контекстной рекламы заключается в том, что она работает избирательно.