Como armazenar a expressão matemática na lista de c ++

5

Eu estou analisando uma expressão matemática infix para um formulário postfix. Eu quero armazená-lo em uma lista como [4.5, 3, 0.25, +, -] para que eu possa processá-lo assim que for analisado. Eu poderia armazená-lo em uma string novamente, mas teria que analisá-lo duas vezes. O problema é que eu não sei como armazenar operadores e operandos na mesma lista . Pensei em duas classes de filhos de um pai comum, mas elas são totalmente diferentes.

Qual é a melhor maneira de conseguir isso?

    
por germanfr 10.06.2016 / 22:42
fonte

5 respostas

2

The problem is that I don't know how to store operators and operands in the same list

Considere o padrão de design composto :

Oartigomostraumexemplodeexpressãomatemática:

Issopermitequevocêconstruasuaprópriaárvore.Sevocêquiser,tambémpodearmazenartodososelementosemumalista,masdoThis()estáusandoaárvoreparapercorrer.

Oquepodeserumpoucoconfusoéquemostratodasasoperaçõescomométodos.Emvezdisso,vocêpoderiaarmazenaraoperaçãononódecomposição.RenomeiedoThis()paracalculate()eagoravocêpodechamarroot.calculate()paracalcularaexpressãointeira.Vocêseriacapazdefazerissoemqualquernó.Euteriaainterfaceassim:

<<interface>>Component---------+calculate()+getPrefixString()+getInfixString()+getPostfixString()+addElement(Componentcomponent)

Nadadissotiravocêdeterqueconsertarelementosaovisitarcadaumdeles.Aquiestáumamaneiradeevitarisso:

Agoravocêpodefazertodaaanálisenafrenteantesdeconstruiraárvore.doThis(),oucalculate()comoeurenomei,sabequaloperadorusarpolimorficamente.

Comotodosessestêmomesmotipo,Component,vocêestálivreparaarmazená-losemumalista,matrizouqualqueroutracoisa.Masamaneiracomoelesseligamaindaéumaárvore.

Vocêexpressouumapreocupaçãodeconstruçãoemrelaçãoànotaçãoinfixada.Considere o padrão do construtor . É bom na construção de compostos. O link que eu forneci leva você a refatorar exatamente esse caso. Acho que você encontrará energia suficiente para lidar com infix, prefixo e postfix.

    
por 11.06.2016 / 15:45
fonte
0

How to store math expression in c++ list

Considere as árvores

O fundamental aqui é que as notações de prefixo, infixo e postfix são apenas formas de apresentar expressões matemáticas. Ao armazenar você não precisa se importar com a forma como eles foram apresentados. O mais interessante sobre a árvore é que você pode traduzir expressões equivalentes nessas notações em árvores idênticas. E você pode converter a árvore para qualquer uma dessas notações.

Aqui está a mesma árvore, percorrida da mesma maneira a cada vez. A diferença é quando você pega o valor do nó. A diferença é o ponto. Quando você toca no ponto, você pega (ou abaixa) a letra. Ao girar o ponto, você obtém os caracteres nas três notações diferentes.


Prefixo:travessiadepré-encomenda


Infix:travessiaemordem


Postfix:travessiadepós-encomenda

Existeumaestruturadedadosemc++quefuncionabemparaisso.Chama-se btrees

    
por 11.06.2016 / 06:48
fonte
0

Embora eu ache que a resposta do CandiedOrange é uma abordagem melhor, como as árvores são muito mais úteis para executar operações em expressões, se tudo o que você quer fazer é armazená-lo e depois avaliá-lo, uma lista de postfix junto com um avaliador baseado em pilha é adequada e mais simples.

Quando você diz que não há nada em comum entre seus operandos e operadores, isso não é inteiramente verdade. Para executar sua expressão, você precisará visitar cada um deles em ordem, fornecendo uma pilha para eles trabalharem. Os operandos empurrarão um valor na pilha, enquanto os operadores exibirão um par de valores, realizarão um cálculo e enviarão o resultado. Ambos podem ter a mesma interface: são operações de pilha .

    
por 11.06.2016 / 13:39
fonte
0

(eu assumo e espero que você queira codificar em genuíno C ++ 11 ou C ++ 14 usando o seu pacotes padrão e biblioteca de utilitários ; não use uma variante anterior do C ++; certifique-se de ter um compilador recente : em junho de 2016, use GCC versão 5 ou 6 e / ou Clang / LLVM versão 3.7 ou 3.8 , ambos software livre )

Você provavelmente deseja representar a árvore de sintaxe abstrata (AST) de suas expressões analisadas. Leia mais sobre análise . Você pode querer ler os primeiros capítulos do Dragon Book . Ou codifique um analisador de descendência recursivo . Ou use algum gerador de parser (muitas vezes chamado incorretamente de compiladores de compiladores ) como ANTLR3 ou bisão GNU - ou algum yacc -). BTW, seu problema é semelhante a um dos exemplos dados na documentação de bison ( infix calc ).

Você não organizará sua AST como uma lista de C ++ , mas como uma árvore . Por exemplo, você pode ter uma superclasse (abstrata) comum class expr e ter uma subclasse abstrata para as folhas class leaf_expr: public class expr com subclasses finais concretas como class int_expr: public leaf_expr para literais inteiros (por exemplo, 12 ), class var_expr: public leaf_expr para variáveis (por exemplo %código%). Você terá uma superclasse x para nós binários contendo os campos ponteiro inteligente (provavelmente class binary_expr : class_expr ...) para sub-árvores esquerda e direita - com subclasses finais concretas std::shared_ptr<expr> etc para nós de soma (por exemplo, para class sum_expr : public class binary_expr ).

Se você precisar obter uma tradução de postfix do seu AST, definirá uma outra representação para expressões de postfix, talvez como uma lista de ponteiros inteligentes para componentes de postfix e defina outra hierarquia de classes para seus componentes do postfix: uma superclasse abstrata x+12 com várias subclasses class postfix (para um operando literal de inteiro postfix como class int_postfix ), 12 (para um operando variável postfix como class var_postfix ), x (para um operador postfix como class plus_postfix ), usando algumas superclasses abstratas intermediárias como + para operandos e class operand_postfix : public postfix e provavelmente class operator_postfix : public postfix e class unary_operator_postfix : public operator_postfix etc ...) ... e tem uma lista de ponteiros inteligentes destes ( por exemplo, class binary_operator_postfix : public operator_postfix ...). Então você pode facilmente codificar um transformador de AST para lista de postfix:

std::list<std::unique_ptr<postfix>> transform_ast_to_postfix
    (std::shared_ptr<expr>);

The problem is that I don't know how to store operators and operands in the same list

Você terá uma lista de indicadores inteligentes para uma superclasse comum, por exemplo, %código%. Em alguns casos (mas não no seu), você também pode considerar ter uma lista de objetos contendo um sindicato marcado . FWIW C ++ 17 lhe dará std :: any

(Você pode evitar explicitamente representando AST na memória e construir diretamente a lista de ponteiros inteligentes para std::list<std::unique_ptr<postfix>> elements em ações do seu analisador, mas acredito que construir o AST é mais fácil e mais geral)

Observe que um bom entendimento dos ponteiros e pontos inteligentes são essenciais . Usar ponteiros inteligentes em vez de ponteiros brutos (por exemplo, std::list<std::unique_ptr<postfix>> ) poderia ajudar você a escrever códigos mais limpos e evitar vazamentos de memória . Você deve entender RAII e provavelmente (em C ++ 11) a regra de cinco . Veja esta pergunta.

Você deve ler os Princípios de programação e programação da Stroustrup. pratica usando C ++

    
por 12.06.2016 / 08:24
fonte
-1

Se a expressão já estiver convertida em RPN / postfix, você precisará apenas de um vetor ou matriz básica. Crie uma estrutura de dados simples que contenha os valores e as informações do operador e envie cada item para a lista.

struct myToken {
   int tokType;  //1 = value, 2 = operator
   float tokVal;
   int opType; //1 = add, 2 = sub, 3 = mult, etc
}

Para reavaliar a expressão, basta iterar a lista. Você também pode estender isso para suportar chamadas de função, como sum () sqrt (), adicionando membros para rastrear um nome de função e o número de parâmetros necessários, e fazer com que seu avaliador de expressão os verifique.

    
por 12.06.2016 / 09:20
fonte