Разрабатываем парсер математических выражений
Автор: 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-29 » «Адаптация бюджета» в Яндекс Директе: как автоматически масштабировать рекламу без потери эффективности
- 2026-07-29 » Overlay в РСЯ: новый формат мобильной рекламы, который не раздражает пользователей
- 2026-07-29 » «Панорама» в Яндекс Директе: новый уровень охватной рекламы для вашего бизнеса
- 2026-07-29 » Карточки товаров и отзывы на маркетплейсах: что по закону считается рекламой, а что нет
- 2026-07-29 » Комментарии в приватных каналах «Макс»: новый инструмент для бизнес-коммуникаций
- 2026-07-23 » Как ошибки в AI-ответах портят репутацию компании
- 2026-07-23 » Маркировка рекламы в 2026 году: фатальные ошибки, которые обойдутся вашему бизнесу в полмиллиона рублей
- 2026-07-23 » Нейросети в дизайне сайтов и графике: революция, эволюция или угроза?
- 2026-07-23 » РСЯ открыла инструмент авторасстановки рекламы для всех партнеров: как автоматизация меняет правила монетизации
- 2026-07-23 » Контент для стоматологических клиник: какими текстами наполнить сайт, чтобы пациенты записывались сами
- 2026-07-22 » Продающие анимированные баннеры для вашего бизнеса
- 2026-07-22 » Услуги таргетолога по настройке рекламы ВКонтакте (ВК)
- 2026-07-19 » GEO / AISEO / AEO для B2C
- 2026-07-19 » GEO / AISEO / AEO для B2B
- 2026-07-15 » ИИ-агент как сотрудник: права, журнал действий и управление доступом через BearPass
- 2026-07-15 » Как проверить юриста, адвоката или нотариуса онлайн: пошаговое руководство для бизнеса
- 2026-07-15 » Телефон в вашем кармане действительно следит: кто, зачем и как это остановить
- 2026-07-15 » Куки и трекеры: какую информацию о вас собирают сайты и как это отключить
- 2026-07-15 » Почему корпоративный мессенджер — это не роскошь, а необходимость для бизнеса
- 2026-07-15 » Реклама на Авито, которая реально работает
- 2026-07-15 » Реклама на Авито, которая реально работает
- 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 » Уникальность текста: когда копировать контент можно, а когда нельзя
Самый лучший человек тот, который живет преимущественно своими мыслями и чужими чувствами, самый худший сорт человека - который живет чужими мыслями и своими чувствами. Из различных сочетаний этих четырех основ, мотивов деятельности - все различие людей. Люди, живущие только своими чувствами, - это звери. Толстой Лев Николаевич - (1828-1910) - великий русский писатель. Его творчество оказало огромное влияние на мировую литературу |
Мы создаем сайты, которые работают! Профессионально обслуживаем и продвигаем их !
Как мы работаем
Заявка
Позвоните или оставьте заявку на сайте.
Консультация
Обсуждаем что именно Вам нужно и помогаем определить как это лучше сделать!
Договор
Заключаем договор на оказание услуг, в котором прописаны условия и обязанности обеих сторон.
Выполнение работ
Непосредственно оказание требующихся услуг и работ по вашему заданию.
Поддержка
Сдача выполненых работ, последующие корректировки и поддержка при необходимости.
Мы создаем практически любые сайты от продающих страниц до сложных, высоконагруженных и нестандартных веб приложений! Наши сайты это надежные маркетинговые инструменты для успеха Вашего бизнеса и увеличения вашей прибыли! Мы делаем красивые и максимально эффектные сайты по доступным ценам уже много лет!
Комплексный подход это не просто продвижение сайта, это целый комплекс мероприятий, который определяется целями и задачами поставленными перед сайтом и организацией, которая за этим стоит. Время однобоких методов в продвижении сайтов уже прошло, конкуренция слишком высока, чтобы была возможность расслабиться и получать \ удерживать клиентов из Интернета, просто сделав сайт и не занимаясь им...
Мы оказываем полный комплекс услуг по сопровождению сайта: информационному и техническому обслуживанию и развитию Интернет сайтов.
Контекстная реклама - это эффективный инструмент в интернет маркетинге, целью которого является увеличение продаж. Главный плюс контекстной рекламы заключается в том, что она работает избирательно.