L'ajout des Conditions et des Fonctions d'un Analyseur de Mathématiques
https://stackoverflow.com/questions/3262889
-
16-09-2020 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai un arbre binaire en fonction mathématique analyseur d'expression, je l'ai construite, qui fonctionne très bien pour la "normale" des mathématiques, comme: (3.5 * 2) ^ 1 / (1 << 6).cependant, je voudrais élargir un peu pour ajouter un ternaire opérateur de sélection, de mise en miroir l'une de C: {expr} ? {true-expr} : {false-expr}.Je tiens également à ajouter des fonctions, comme sin(x) ou ave(...).
J'ai cependant aucune idée de comment le gérer cela (en raison de la façon dont l'évaluation des travaux), je ne peux rien trouver sur le web qui couvre ce, au moins dans un non-grammaire basée sur (je voudrais éviter de grammaire analyseur de générateurs pour cela, si possible).
Mon analyseur œuvres actuelles de l'évaluation d'une expression infix et immédiatement de le convertir à un arbre, puis à partir de là, l'arbre peut être évalué, c'est à dire:sa vous bog standard de l'arborescence d'expression.
actuellement, mon évaluateur ressemble à ceci:
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;
}
Des conseils/pointeurs/conseils ou des liens utiles sur la façon dont je peux l'accomplir?
Un petit ensemble d'exemples (comme demandé):
Ce que j'ai déjà travailler
Entrée: 2 * (3 ^ 1.5) - 4 / (1 << 3)
Sortie: 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
Ce que je veux ajouter
Entrée: (GetDay() == 31) ? -15.5 : 8.4
Sortie: 8.4
Sortie le 31: -15.5
Entrée: max([0],20) (où [0] désigne argument 0, et [0] = 35)
Sortie: 20
Entrée: (GetField('employees','years_of_service',[0]) >= 10) ? 0.15 : 0.07 (où [0] est l'argument 0, et [0] est réglé sur un index valide)
De sortie (si years_of_service pour la emplyee est à moins de 10: 0.15
le reste de Sortie: 0.07
De son fond de maths avec certains C inspiré ajouts, à l'exception d'arguments ne sont pas transmis par son nom, mais plutôt de l'index, et les cordes sont échappés par des guillemets doubles.
Une fois que j'ai au final peu fait, je suis en espérant que soit le bytecode de la compilation ou JIT, comme je suis de rabotage de les utiliser pour des choses comme les jeux ou les mathématiques reliant les programmes, où le jeu d'entrée de données est constant, mais le jeu de données d'entrée peuvent changer, mais son être fréquemment utilisé, il doit être "rapide", et il doit être utilisable par des non-programmeurs.
La solution
La bonne chose à faire pour ?et :dépend de l'arbre produit par l'analyseur.Je vais faire semblant de l'analyseur génère un arbre comme
?
b :
t f
D'abord vous avez besoin de ne pas évaluer les arbres avant de l'interrupteur, et la plupart des endroits vous modifiez quelque chose comme
fLeft + fRight;
en
EvaluateTree(pNode->pLeft) + EvaluateTree(pNode->pRight);
Avec + remplacés par les divers opérateurs.
Pour ?:vous n' ....
case ':': return 0.0f; /* this is an error in the parse tree */
case '?': if (!(pNode && pNode->pLeft && pNode->pRight &&
pNode->pRight->pLeft && pNode->pRight->pRight))
/* another error in the parse tree */
return 0.0f;
return EvaluateBool(pNode->pLeft) ?
EvaluateTree(pNode->pRight->pLeft) :
EvaluateTree(pNode->pRight->pRight) ;
Pour une définition de EvaluateBool vous avez deux choix.Comme en C est plus ou moins
BOOL EvaluateBool(Node* pNode)
{
return (EvaluateTree(pNode) == 0.0) ? FALSE : TRUE;
}
Ensuite, vous devez les définitions des termes"<"et amis que le retour de 0,0 pour de faux, et d'autre chose pour vrai.La valeur -1 est un très populaire vraie valeur, bien que généralement pour le stockage des booléens dans ints.
La plus structurée, est de déplacer tous les opérateurs like '<'que le retour des valeurs booléennes dans le corps de EvaluateBool, et de le faire fonctionner plus ou moins comme EvaluateTree n'.
Enfin, au lieu de faire de l'opérateur ternaire ?:l'utilisation de deux nœuds, vous pouvez également modifier la définition du nœud (et de l'analyseur) d'avoir jusqu'à trois sous les arbres, puis la plupart des opérateurs disposent de deux arbres, mais ?:aurait trois.Peut-être quelque chose comme
case '?': return EvaluateBool(pNode->pLeft) ?
EvaluateTree(pNode->pMiddle) :
EvaluateTree(pNode->pRight) ;
Mais alors vous allez avoir à réécrire votre pré-commande, dans l'ordre, après l'ordre de l'arbre traversals.
Deuxième partie, les fonctions.Une façon de le faire est de stocker le nom de la fonction dans szValue.Une autre est d'avoir un tas de différentes valeurs pour nType selon la fonction.Vous aurez à chercher une règle dans l'analyseur, et l'utiliser ici dans l'interpréteur.Vous pourriez faire quelque chose comme...
else if(nType == TOKEN_CALL)
return EvaluateFunc(pNode);
Puis EvaluateFunc pourrait ressembler à quelque chose comme
number_t EvaluateFunc(Node* pNode)
{
if ((pNode == NULL) || (pNode->szValue == NULL))
return 0.0f;
if (0 == strcmp('cos', pNode->szValue))
return my_cos(EvaluateTree(pNode->pLeft));
else if (0 == strcmp('gcd', pNode->szValue))
return my_gcd(EvaluateTree(pNode->pLeft),
EvaluateTree(pNode->pRight));
/* etc */
else /* unknown function */ return 0.0f;
}
Ressemble à un projet intéressant, profitez-en!
Autres conseils
Je pense que vous devriez changer votre "Nœud" struct avoir un tableau des enfants, au lieu de "pLeft" et "pRight".Une fonction sin() a un argument/enfant.Le conditionnel (ternaire) de l'opérateur a trois arguments/enfants.
