Парсинг математических выражений
(в C90) (Linux)
вход:
sqrt(2 - sin(3*A/B)^2.5) + 0.5*(C*~(D) + 3.11 +B)
a
b /*there are values for a,b,c,d */
c
d
вход:
cos(2 - asin(3*A/B)^2.5) +cos(0.5*(C*~(D)) + 3.11 +B)
a
b /*there are values for a,b,c,d */
c
d
вход:
sqrt(2 - sin(3*A/B)^2.5)/(0.5*(C*~(D)) + sin(3.11) +ln(B))
/*max lenght of formula is 250 characters*/
a
b /*there are values for a,b,c,d */
c /*each variable with set of floating numbers*/
d
Как видите, формула инфикса во входных данных зависит от пользователя. Моя программа примет формулу и значение n-кортежей. Затем он вычисляет результаты для каждого значения a,b,c и d. Если вам интересно, я говорю, результат программы - график. / иногда я думаю, что я возьму ввод и сохраню в строке. тогда возникает другая идея: "Я должен хранить формулу в структуре", но я не знаю, как я могу построить код на основе структуры. /
на самом деле, я не знаю, как сохранить формулу в программном коде, чтобы я мог выполнять свою работу. можешь ли ты показать мне?
/* a,b,c,d is letters
cos,sin,sqrt,ln is function*/
5 ответов
Вам необходимо написать лексический анализатор для токенизации ввода (разбить его на составляющие части - операторы, знаки препинания, идентификаторы и т. Д.). Неизбежно, в итоге вы получите последовательность токенов.
После этого существует несколько способов оценки входных данных. Один из самых простых способов сделать это - преобразовать выражение в постфикс с помощью алгоритма шунтирования (оценка выражения с постфиксом - Easy с заглавной E).
Вы должны искать "абстрактные синтаксические деревья" и "деревья выражений", а также "лексический анализ", "синтаксис", "синтаксический анализ" и "теория компилятора". Чтение ввода текста и получение значения от него довольно сложно для большинства вещей (хотя мы часто пытаемся убедиться, что у нас есть простой ввод).
Первым шагом в создании парсера является запись грамматики для вашего языка ввода. В этом случае ваш язык ввода - это математические выражения, поэтому вы должны сделать что-то вроде:
expr => <function_identifier> ( stmt )
( stmt )
<variable_identifier>
<numerical_constant>
stmt => expr <operator> stmt
(Я не написал такую грамматику {ищите BNF а также EBNF} через несколько лет, поэтому я, вероятно, допустил несколько вопиющих ошибок, которые любезно укажет кто-то другой). Это может стать намного сложнее в зависимости от того, как вы обрабатываете приоритет оператора (умножение и устройство перед сложением и вычитанием типа), но смысл грамматики в этом случае - помочь вам написать синтаксический анализатор.
Есть инструменты, которые помогут вам сделать это (yacc, bison, antlrи другие), но вы можете сделать это и вручную. Есть много способов сделать это, но у всех них есть одна общая черта - стек. Для обработки такого языка требуется нечто, называемое автоматом нажатия, что является просто причудливым способом сказать что-то, что может принимать решения на основе нового ввода, текущего состояния и верхнего элемента стека. Решения, которые он может принять, включают толкание, выталкивание, изменение состояния и объединение (поворот 2+3 в 5 это форма объединения). Объединение обычно называют производством, потому что оно дает результат.
Из различных распространенных типов парсеров вы почти наверняка начнете с рекурсивного приличного парсера. Они обычно пишутся непосредственно на языке программирования общего назначения, таком как C. Этот тип синтаксического анализатора состоит из нескольких (часто многих) функций, которые вызывают друг друга, и они в конечном итоге используют системный стек в качестве стека автоматов.
Еще одна вещь, которую вам нужно сделать, это записать различные типы слов и операторов, составляющих ваш язык. Эти слова и операторы называются лексемами и представляют собой токены вашего языка. Я представил эти токены в грамматике <like_this>кроме скобок, которые представляли сами.
Скорее всего, вы захотите описать свои лексемы с помощью набора регулярных выражений. Вы должны быть знакомы с ними, если вы используете grep, sed, awk, или же perl, Они представляют собой способ описания так называемого обычного языка, который может обрабатываться чем-то, что называется конечным автоматом. Это просто причудливый способ сказать, что это программа, которая может принимать решение об изменении состояния, рассматривая только его текущее состояние и следующий ввод (следующий символ ввода). Например, часть вашего лексического описания может быть:
[A-Z] variable-identifier
sqrt function-identifier
log function-identifier
[0-9]+ unsigned-literal
+ operator
- operator
Есть также инструменты, которые могут генерировать код для этого. lex который является одним из них, тесно интегрирован с программой генерации парсера yacc, но так как вы пытаетесь учиться, вы также можете написать свой собственный код токенизатора / лексического анализа на C.
После того, как вы проделали все это (вероятно, это займет у вас много времени), вам понадобится, чтобы ваш синтаксический анализатор построил дерево для представления выражений и грамматики входных данных. В простом случае оценки выражений (например, при написании простой программы-калькулятора командной строки) ваш парсер может оценить формулу при обработке ввода, но для вашего случая, как я понимаю, вам нужно будет создать дерево (или Обратное польское представление, но деревья проще на мой взгляд).
Затем, после того как вы прочитали значения переменных, вы можете пройтись по дереву и вычислить фактическое число.
Возможно, самое простое, что можно сделать, это использовать встроенный язык, такой как Lua или Python, для которого оба языка написаны на C. К сожалению, если вы пойдете по маршруту Lua, вам придется преобразовать двоичные операции в вызовы функций, в которых В этом случае, вероятно, проще использовать Python. Так что я пойду по этому пути.
Если вы просто хотите вывести результат на консоль, это действительно просто, и вам даже не придется слишком углубляться во встраивание Python. С тех пор вам нужно всего лишь написать однострочную программу на Python для вывода значения.
Вот код Python, который вы можете использовать:
exec "import math;A=<vala>;B=<valb>;C=<valc>;D=<vald>;print <formula>".replace("^", "**").replace("log","math.log").replace("ln", "math.log").replace("sin","math.sin").replace("sqrt", "math.sqrt").replace("cos","math.cos")
Обратите внимание, что замены сделаны в Python, так как я уверен, что это проще сделать в Python, а не C. Также обратите внимание, что если вы хотите использовать xor('^'), вам придется удалить .replace("^","**") и использовать ** для питания.
Я не знаю достаточно C, чтобы рассказать вам, как сгенерировать эту строку в C, но после этого вы можете использовать следующую программу для ее запуска:
#include <Python.h>
int main(int argc, char* argv[])
{
char* progstr = "...";
Py_Initialize();
PyRun_SimpleString(progstr);
Py_Finalize();
return 0;
}
Вы можете найти больше информации о внедрении Python в C здесь: Расширение Python и Документация по встраиванию
Если вам нужно использовать результат расчета в вашей программе, есть способы прочитать это значение из Python, но вам придется ознакомиться с ними самостоятельно.
Кроме того, вы должны просмотреть свои сообщения в SO и другие сообщения, касающиеся бинарных деревьев. Реализуйте это, используя древовидную структуру. Траверс как инфикс для оценки. Там было несколько отличных ответов на древовидные вопросы.
Если вам нужно сохранить это (для сохранения, как в файле), я предлагаю XML. Синтаксический анализ XML должен заставить вас по-настоящему оценить, насколько легко ваше назначение.
Прочтите этот пост: http://blog.barvinograd.com/2011/03/online-function-grapher-formula-parser-part-2/ Он использует библиотеку ANTLR для синтаксического анализа математического выражения, в частности, используется вывод JavaScript, но ANTLR имеет много выходов, таких как Java, Ruby, C++, C#, и вы должны иметь возможность использовать грамматику в посте для любого языка вывода.