Resolva a equação da string para resultar em C

Question

Gostaria de saber se alguém tem informações ou experiência sobre como fazer algo que soa simples, mas não se parece com isso ao tentar programá -las. A idéia é: dê uma string contendo uma equação, como: "2*x = 10", por exemplo (isso é simples, mas pode ser muito complexo, como o SQRT (54)*35 = x^2; e assim em ....) e o programa retornaria x = 5 e possivelmente daria um tronco de como ele chegou lá.

Isso é factível? Se sim, alguém tem liderança? Para informações, existe este site (http://www.numberempire.com/equationsolver.php) que faz a mesma coisa no PHP, mas não é de código aberto.

Obrigado por qualquer ajuda !

Answer 1

Isso é chamado de "análise" e, embora a ciência da computação já tenha resolvido esse problema, não é simples até que você o entenda minuciosamente. Há uma disciplina inteira de ciência do computador que descreve como resolver esse problema. Em C, você deve definir a gramática de sua entrada (possivelmente com regras de precedência) e depois executar Análise lexical em sua contribuição, então analisar o resultado e, finalmente, avalie sua árvore de análise.

Em idiomas como Ruby, no entanto, porque você tem um suporte tão completo para a manipulação de cordas e, como tem um tremendo poder de tempo de execução, pode resolver seu problema com uma única linha de código como assim:

puts(eval($_)) while gets

Sim, isso cobrirá mais do que você pede.

Answer 2

Em primeiro lugar, você deve definir corretamente quais tipos de equações você pode ter como entrada. Em seguida, você deve criar uma boa abstração para representar a equação, por exemplo, uma classe polinomial. Quando você quiser usar expressão mais complexa, escolha uma árvore para expressões numéricas. A análise pode ser bastante fácil se você tiver boas regras para converter a expressão em notação de prefixo, a avaliação é fácil usando pilhas. Depois de ter árvores ou polinômios artitméticos, você pode implementar transformações para calcular as variáveis.

Answer 3

Se as equações forem complexas, certamente não serão poucas linhas de código C/C ++.

Para equações lineares, você teria que simular um dos métodos descritos nos livros de álgebra linear. O código disso é pequeno o suficiente.

Answer 4

Você pode tentar vincular no Sympy ao seu código C (ou C ++) e usá -lo para resolver suas equações.

IIRC, o Sympy tem esse tipo de funcionalidade. Além disso, deve ser mais fácil manipular a sequência de entrada para uma equação utilizável dentro do Python e depois passá -la para a Sympy para resolver.

Answer 5

Haverá duas partes no seu problema: analisar as equações e resolvê -las simbolicamente. Não vou dizer muito sobre o primeiro, já que outras respostas já cobriram bem esse tópico; Minha recomendação pessoal seria escrever um analisador de descida recursiva simples para expressões na notação de prefixo.

A segunda parte, resolvendo as equações analiticamente, será complicada. De um modo geral, existem classes especiais de equações para as quais existem métodos padrão para encontrar uma solução analítica:

• Sistemas de equações lineares: qualquer solucionador linear direto. Se você deseja mostrar as etapas explicitamente e o número de equações/incógnitas é pequeno, eu recomendaria algo simples como eliminação gaussiana sem valor ou regra de Cramer.
• Sistema de equações polinomiais: equivalente, após substituição variável, para encontrar raízes de polinômios únicos. Se eles tiverem grau <= 4, existem fórmulas para soluções exatas. NB: Para o grau 3 e 4, essas fórmulas não são agradáveis.
• Soluções racionais para um sistema de equações polinomiais com coeficiente racional: faça substituição variável como acima. Em seguida, força bruta usando o teste zero racional.
• Outros tipos de equações: boa sorte. Para [sistemas de] equações não lineares mais complicadas, se você pode se contentar com soluções numéricas (não analíticas), consulte o método de Newton.

Answer 6

Uma correção: essa não é álgebra linear, que geralmente significa matriculares de múltiplas equações e incógnitas.

Seu exemplo certamente não é complexo.

O que você precisa é de uma expressão simples de expressão e analisador. Analise a equação em uma árvore de sintaxe abstrata e passe a árvore para avaliá -la.

Se você estivesse escrevendo java, pode parecer isto. Outro exemplo é Symja. Talvez seja inspiração suficiente para você criar o seu próprio para C ++.

Você também pode querer olhar para o alfa de Mathematica e Wolfram. Stephen Wolfram é um dos melhores matemáticos e cientistas da computação do mundo. Ele tem muitas coisas que você pode reutilizar com uma vantagem, em vez de escrever você mesmo.

Você terá que definir o que você quer dizer com "resolver" e o que você espera ter retornado.

Existem soluções simbólicas e soluções numéricas. Qual deles voce quer dizer? Ambos são igualmente válidos, mas são diferentes. Você aplicará técnicas diferentes, dependendo da sua resposta.

Outro ponto: existem muitas técnicas para "resolver" equações que dependem muito do tipo de equação. Se você me der algo como f(x) = 0 Penso em algoritmos de localização de raiz como o método de Newton. Se você me der uma equação diferencial comum, posso tentar um método de substituição ou integração numérica usando o Runge-Kutta. Se você me der uma equação diferencial parcial, posso aplicar diferença finita, elemento finito ou técnicas de elementos de limite. (Não me inicie em PDEs elípticos, parabólicos e hiperbólicos.)

O ponto é que sua pergunta é muito genérica e a resposta depende muito do que você está tentando fazer. Mais detalhes podem ajudar.

Answer 7

Em geral, você terá que analisar a expressão em alguma representação interna. Muitos livros de álgebra lineares sugerem o uso de matrizes (ou std::vector) para representar os coeficientes. O expoente do termo é definido por sua posição no vetor.

Por exemplo, a expressão:

 2 + 3x + 5x^2

Pode ser representado como uma matriz ou std::vector:

std::vector<int> expression;
expression[0] = 2; // 2 * x ^ 0
expression[1] = 3;
expression[2] = 5;

Escrever uma função de avaliação se torna trivial e deixado como um exercício para o leitor.

A solução de várias equações se torna mais complexa. Existem bibliotecas e algoritmos existentes para isso. Uma pesquisa no Google deve criar algo bom. :-)

Sugiro começar com termos simples e construir um analisador para isso. Uma vez que isso funcione, você também pode alterar o analisador para aceitar nomes de funções.

Se você está tentando simplificar uma expressão que tenha termos em ambos os lados do =, apenas escreva as etapas que você normalmente daria ao resolver manualmente. Experimente algumas equações diferentes para reduzir algumas regras. Agora implemente essas regras em C ++.