У меня есть встроенный синтаксический анализатор математических выражений на основе двоичного дерева, который отлично работает для «нормальной» математики, например: (3.5 * 2) ^ 1 / (1 << 6). Тем не менее, я хотел бы немного расширить его, добавив троичный оператор выбора, отражающий оператор из C: {expr} ? {true-expr} : {false-expr}. Я также хотел бы добавить функции, такие как sin(x) или ave(...).
Я, однако, не имею ни малейшего понятия о том, как справиться с этим (из-за того, как работает оценка), и я не могу найти в Интернете ничего, что освещает это, по крайней мере, не на грамматическом уровне (я бы хотел избежать грамматический парсер для этого, если возможно).
Мой текущий синтаксический анализатор работает, вычисляя инфиксное выражение и немедленно преобразуя его в дерево, а затем оттуда можно вычислить дерево, т. Е. Его дерево стандартных выражений.
В настоящее время мой оценщик выглядит так:
struct Node
{
int nType;
union
{
unsigned long dwOperator;
BOOL bValue;
int nValue; //for indices, args & functions
number_t fValue;
char* szValue; //for string literals to pass to functions
};
Node* pLeft;
Node* pRight;
};
number_t EvaluateTree(Node* pNode)
{
if(pNode == NULL)
return 0.0f;
int nType = pNode->nType;
if(nType == TOKEN_OPERATOR)
{
number_t fLeft = EvaluateTree(pNode->pLeft);
number_t fRight = EvaluateTree(pNode->pRight);
switch(pNode->dwOperator)
{
case '+': return fLeft + fRight;
case '-': return fLeft - fRight;
case '*': return fLeft * fRight;
case '/': return fLeft / fRight;
case '^': return pow(fLeft,fRight);
case '_': return pow(fLeft,1.0f/fRight);
case '%': return fmod(fLeft,fRight);
//case '?': return bSelect = ?;
//case ':': return (bSelect) ? fLeft : fRight;
//case '>': return fLeft > fRight;
//case '<': return fLeft < fRight;
//case '>=': return fLeft >= fRight;
//case '<=': return fLeft <= fRight;
//case '==': return fLeft == fRight;
//case '!=': return fLeft != fRight;
//case '||': return fLeft || fRight;
//case '&&': return fLeft && fRight;
case '&': return static_cast<number_t>(static_cast<unsigned long>(fLeft) & static_cast<unsigned long>(fRight));
case '|': return static_cast<number_t>(static_cast<unsigned long>(fLeft) | static_cast<unsigned long>(fRight));
case '~': return static_cast<number_t>(~static_cast<unsigned long>(fRight));
case '>>': return static_cast<number_t>(static_cast<unsigned long>(fLeft) >> static_cast<unsigned long>(fRight));
case '<<': return static_cast<number_t>(static_cast<unsigned long>(fLeft) << static_cast<unsigned long>(fRight));
default:
{
printf("ERROR: Invalid Operator Found\n");
return 0.0f;
}
}
}
else if(nType == TOKEN_NUMBER)
return pNode->fValue;
else if(nType == TOKEN_CALL)
return CreateCall(pNode); //not implemented
else if(nType == TOKEN_GLOBAL)
return GetGlobal(pNode);
else if(nType == TOKEN_ARGUMENT)
return GetArgument(pNode);
else if(nType == TOKEN_STRING)
return 0.0f;
return 0.0f;
}
Какие-либо советы / указатели / советы или полезные ссылки о том, как мне это сделать?
Небольшой набор примеров (по запросу):
Что у меня уже работает
Ввод: 2 * (3 ^ 1.5) - 4 / (1 << 3)
Вывод: In-Order: 2.0 * 3.0 ^ 1.5 - 4.0 / 1.0 << 3.0
Pre-Order: - * 2.0 ^ 3.0 1.5 / 4.0 << 1.0 3.0
Post-Order: 2.0 3.0 1.5 ^ * 4.0 1.0 3.0 << / -
Result: 9.892304
Что я хочу добавить
Ввод: (GetDay() == 31) ? -15.5 : 8.4
Выход: 8.4
Выход на 31-е: -15.5
Ввод: max([0],20) (где [0] обозначает аргумент 0, а [0] = 35)
Выход: 20
Ввод: (GetField('employees','years_of_service',[0]) >= 10) ? 0.15 : 0.07 (где [0] - аргумент 0, а [0] - допустимый индекс)
Вывод (если year_of_service для emplyee меньше 10: 0.15
else Вывод: 0.07
Это в основном математика с некоторыми дополнениями, вдохновленными C, за исключением того, что аргументы передаются не по имени, а по индексу, а строки экранируются одинарными кавычками, а не удваиваются.
Когда у меня будет последний бит, я надеюсь либо скомпилировать байт-код, либо JIT, поскольку я планирую использовать это для таких вещей, как игры или математические программы, где данные входного набора постоянны, но входной набор может меняться, но его часто используют, поэтому он должен быть «быстрым» и использоваться непрограммистами.