Разрабатываем парсер математических выражений
Автор: 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-09-30 » Таргетированная реклама в Максе: что тестирование инвентаря VK Рекламы значит для вашего бизнеса
- 2026-09-30 » Универсальные сегменты в Яндекс Аудиториях: как объединение email, телефона и ClientID повышает точность рекламы
- 2026-09-30 » Claude Sonnet 5.5: что новая модель Anthropic значит для вашего бизнеса и рекламы
- 2026-09-30 » Медийная реклама на Ozon с автоподбором аудитории: что это дает вашему бизнесу
- 2026-09-30 » Цифровой рубль и новые схемы мошенничества: как защитить свой бизнес
- 2026-09-25 » Россияне выбирают товары в классическом Поиске, но факты проверяют в нейровыдаче: что это значит для вашего бизнеса
- 2026-09-25 » Стоимость целевого действия в интернет-рекламе выросла на 17,4%: что это значит для вашего бизнеса и как реагировать
- 2026-09-25 » Telegram тестирует квадратный формат видеосообщений: что это значит для бизнеса и маркетинга
- 2026-09-25 » В Единой перфоманс-кампании станет проще продвигать товары и страницы каталога: что изменилось и как это использовать
- 2026-09-25 » Яндекс Метрика запустила бесплатные бенчмарки по индустриям: как малому бизнесу сравнивать себя с рынком
- 2026-09-18 » Telegram Ads открыл таргетинг на аудиторию ботов: как бизнесу использовать новый формат
- 2026-09-18 » ChatGPT начал показывать рекламу в диалогах на русском языке: что это меняет для вашего бизнеса
- 2026-09-18 » Половина покупателей используют ИИ-сервисы вместо чтения отзывов: как бизнесу не потерять клиента в новой реальности
- 2026-09-18 » Сбер выпустил первую модель ГигаЧата с логическим мышлением: что это значит для вашего бизнеса
- 2026-09-18 » Новый статус «Надежный бизнес» в Поиске Яндекса: что это дает интернет-магазинам и сайтам услуг
- 2026-09-09 » Революция в охватной рекламе: как «Панорама» в Директе меняет правила игры для малого и среднего бизнеса
- 2026-09-09 » Новый рубеж для видеоконтента: как монетизация Rutube Shorts открывает возможности для бизнеса
- 2026-09-09 » Новая эра автоматизации: как Алиса AI для бизнеса меняет правила игры на рынке ИИ-агентов
- 2026-09-09 » Больше баллов — больше отзывов: как новые настройки награды в «Баллах за отзывы» Яндекса помогут вашему бизнесу расти
- 2026-09-09 » Поддельные приложения Rutube, VK Видео и Макс в топах App Store: что это значит для вашего бизнеса и как защитить свои цифровые активы
- 2026-09-02 » Лимит дохода самозанятых могут поднять почти вдвое: что это значит для вашего бизнеса
- 2026-09-02 » Новые отчеты Яндекс Метрики: как анализировать удержание и ценность пользователей
- 2026-09-02 » Google сделал ИИ-ответы стандартом поиска: как это меняет правила игры для вашего бизнеса
- 2026-09-02 » Идентификация доменов через Госуслуги с 1 сентября 2026 года: что изменилось для вашего бизнеса и как не потерять сайт
- 2026-09-02 » Цифровой рубль стал обязательным: что меняется для бизнеса с 1 сентября 2026 года
- 2026-08-25 » Статистика каналов в Максе: почему это важно для вашего бизнеса
- 2026-08-25 » Долгожданный контакт: как появление @AdSupport меняет правила игры в Telegram-рекламе
- 2026-08-25 » Скидка, которая видит покупателя насквозь: как новый инструмент Яндекса превращает бюджет в продажи
- 2026-08-25 » Новая эра телевизионной рекламы: как Яндекс Директ превращает экран в витрину
- 2026-08-25 » Отзывы как двигатель продаж: как обратная связь клиентов продвигает ваш сайт в поиске
Самый лучший человек тот, который живет преимущественно своими мыслями и чужими чувствами, самый худший сорт человека - который живет чужими мыслями и своими чувствами. Из различных сочетаний этих четырех основ, мотивов деятельности - все различие людей. Люди, живущие только своими чувствами, - это звери. Толстой Лев Николаевич - (1828-1910) - великий русский писатель. Его творчество оказало огромное влияние на мировую литературу |
Мы создаем сайты, которые работают! Профессионально обслуживаем и продвигаем их !
Как мы работаем
Заявка
Позвоните или оставьте заявку на сайте.
Консультация
Обсуждаем что именно Вам нужно и помогаем определить как это лучше сделать!
Договор
Заключаем договор на оказание услуг, в котором прописаны условия и обязанности обеих сторон.
Выполнение работ
Непосредственно оказание требующихся услуг и работ по вашему заданию.
Поддержка
Сдача выполненых работ, последующие корректировки и поддержка при необходимости.
Мы создаем практически любые сайты от продающих страниц до сложных, высоконагруженных и нестандартных веб приложений! Наши сайты это надежные маркетинговые инструменты для успеха Вашего бизнеса и увеличения вашей прибыли! Мы делаем красивые и максимально эффектные сайты по доступным ценам уже много лет!
Комплексный подход это не просто продвижение сайта, это целый комплекс мероприятий, который определяется целями и задачами поставленными перед сайтом и организацией, которая за этим стоит. Время однобоких методов в продвижении сайтов уже прошло, конкуренция слишком высока, чтобы была возможность расслабиться и получать \ удерживать клиентов из Интернета, просто сделав сайт и не занимаясь им...
Мы оказываем полный комплекс услуг по сопровождению сайта: информационному и техническому обслуживанию и развитию Интернет сайтов.
Контекстная реклама - это эффективный инструмент в интернет маркетинге, целью которого является увеличение продаж. Главный плюс контекстной рекламы заключается в том, что она работает избирательно.