Adicionar Condicionais e Funções para um Analisador de Matemática

Question

Eu tenho uma árvore binária com base matemática analisador de expressão que eu construí, que funciona muito bem para o 'normal' de matemática, como: (3.5 * 2) ^ 1 / (1 << 6).no entanto, eu gostaria de expandir um pouco para adicionar um ternário operador de seleção, espelhando a partir de um C: {expr} ? {true-expr} : {false-expr}.Eu também gostaria de adicionar funções, como sin(x) ou ave(...).

Eu no entanto não tenho nenhuma idéia de como a lidar com isso (devido à forma como a avaliação de obras), nem eu posso encontrar qualquer coisa na web que cobre isso, pelo menos não de gramática com base caminho, eu gostaria de evitar grammer geradores de analisador para isso, se possível).

Minha analisador atual funciona pela avaliação de um infix expressão e imediatamente convertê-lo para uma árvore, depois de lá a árvore pode ser avaliado, ou seja:seu você bog padrão de árvore de expressão.

atualmente o meu avaliador fica assim:

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;
}

Alguma dica/indicadores/conselhos ou links úteis sobre como posso fazer isso?

---

Um pequeno conjunto de exemplos (conforme pedido):

O que eu já tenho

Entrada: 2 * (3 ^ 1.5) - 4 / (1 << 3)

Saída: 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

O que eu quero adicionar

Entrada: (GetDay() == 31) ? -15.5 : 8.4

Saída: 8.4

Saída no dia 31: -15.5

Entrada: max([0],20) (onde [0] denota o argumento 0, e [0] = 35)

Saída: 20

Entrada: (GetField('employees','years_of_service',[0]) >= 10) ? 0.15 : 0.07 (onde [0], é um argumento a 0, e [0] é definido como um índice válido)

De saída (se years_of_service para o emplyee é menor que 10: 0.15

outra Saída: 0.07

É basicamente matemática com alguns C inspirada adições, exceto argumentos não são passados pelo nome, mas, ao invés de índice, e seqüências de escape aspas simples em vez de dobra.

Quando eu tiver o bit final feito, eu estou esperando para compilar o bytecode ou JIT-lo, como eu estou planejando usar isso para coisas como jogos ou matemática dependentes de programas, onde o conjunto de entrada de dados é constante, mas o conjunto de entrada podem mudar, mas o seu ser usado com frequência, por isso precisa ser "rápido", e ele precisa ser usado por não-programadores.

Answer 1

A coisa correta a fazer para ?e :depende da árvore produzida pelo analisador.Vou fingir que o analisador gera uma árvore, como

      ?
  b       :
        t   f

Primeiro você precisa avaliar as árvores antes do interruptor, e a maioria dos lugares que você alterar algo como

fLeft + fRight;

em

EvaluateTree(pNode->pLeft) + EvaluateTree(pNode->pRight);

Com + substituídos por todos os diversos operadores.

Para ?:você não ....

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) ;

Para uma definição de EvaluateBool você tem duas escolhas.A C forma é mais ou menos

BOOL EvaluateBool(Node* pNode)
{
    return (EvaluateTree(pNode) == 0.0) ? FALSE : TRUE;
}

Em seguida, você precisa de definições de"<'e seus amigos que retornam 0.0 para false, e qualquer outra coisa para true.O valor -1 é muito popular verdadeiro valor, embora geralmente para armazenar bools em ints.

A forma mais estruturada é mover todos os operadores like '<'que retornam booleanos para o corpo de EvaluateBool, e fazê-lo funcionar mais ou menos como EvaluateTree faz.

Finalmente, em vez de fazer o operador ternário ?:o uso de dois nós, você também pode alterar a definição de nó (e o parser) para ter até três sub-árvores, em seguida, a maioria dos operadores teria duas árvores, mas ?:seriam três.Talvez algo como

case '?': return EvaluateBool(pNode->pLeft) ?
                   EvaluateTree(pNode->pMiddle) : 
                   EvaluateTree(pNode->pRight) ;

Mas depois você vai ter de reescrever a sua pré-ordem, in-ordem, pós-ordem da árvore transversais.

Segunda parte, funções.Uma maneira que você poderia fazer é armazenar o nome da função no szValue.Outra é ter um monte de diferentes valores para nType dependendo da função.Você vai ter que escolher alguma regra do analisador, e usá-lo aqui no interpretador.Você poderia fazer algo do tipo...

else if(nType == TOKEN_CALL)
    return EvaluateFunc(pNode);

Em seguida, EvaluateFunc pode parecer algo como

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;
}

Parece um projeto divertido, divirta-se!

Answer 2

Eu acho que você deve mudar o seu "Nó" estrutura para ter uma matriz de crianças, em vez de "pLeft" e "pRight".Uma função como o sin() tem um argumento/criança.O condicional (ternário) operador tem três argumentos/crianças.