46
I am developing this program that should receive an expression from the user and do the calculation. Ex:
Insert an expression
3*5-1
14
My problem is how to handle the user-sent expression. I was recommended to use something like eval, but I found nothing equivalent in the language C. Someone has something equivalent?
47
In C there is no "Eval" or anything similar to execute Runtime code.
So the only way to execute an expression like this is to create a sub-language. You need to define a grammar, write a parser and finally, create a interpreter. In the particular case of mathematical expressions, there is a simple shortcut, which is the use of inverse polish notation.
Expressions written in that notation are executed as follows:
The expression 3*5-1 would be written in reverse Polish notation as 3 5 * 1 -. The great advantage of this notation is that parentheses are not necessary. If the expression were 3*(5-1), the Polish equivalent would be 3 5 1 - *. Running such expressions is trivial with the above algorithm. Now the real problem: How to transform an expression into the usual notation for the Polish inverse notation?
For that there is an algorithm called Shunting Yard.
Assuming all your operators are left-associative (ie: +, -, *, /), it can be described like this:
As long as there are symbols to be read...
If you’re an operator (let’s call it o1), then:
o2) such that the precedence of o1 is less than o2, move o2 to the exit.o1 in the pile.If it’s a parenthesis closure:
Example:
Consider the expression 2*3+4*(5-6).
Apply the Shunting Yard:
Símbolo Lido Ação Pilha Temporária Saída
+--------------+---------------------------+------------------+-------------------+
| 2 | Por na saída | | 2 |
+--------------+---------------------------+------------------+-------------------+
| * | Por na pilha | * | 2 |
+--------------+---------------------------+------------------+-------------------+
| 3 | Por na saída | * | 2 3 |
+--------------+---------------------------+------------------+-------------------+
| + | Mover da pilha para saída | | 2 3 * |
| | Por na pilha | + | 2 3 * |
+--------------+---------------------------+------------------+-------------------+
| 4 | Por na saída | + | 2 3 * 4 |
+--------------+---------------------------+------------------+-------------------+
| * | Por na pilha | + * | 2 3 * 4 |
+--------------+---------------------------+------------------+-------------------+
| ( | Por na pilha | + * ( | 2 3 * 4 |
+--------------+---------------------------+------------------+-------------------+
| 5 | Por na saída | + * ( | 2 3 * 4 5 |
+--------------+---------------------------+------------------+-------------------+
| - | Por na pilha | + * ( - | 2 3 * 4 5 |
+--------------+---------------------------+------------------+-------------------+
| 6 | Por na saída | + * ( - | 2 3 * 4 5 6 |
+--------------+---------------------------+------------------+-------------------+
| ) | Mover da pilha para saída | + * ( | 2 3 * 4 5 6 - |
| | Anular com '(' | + * | 2 3 * 4 5 6 - |
+--------------+---------------------------+------------------+-------------------+
| | Pilha toda para saída | | 2 3 * 4 5 6 - * + |
+--------------+---------------------------+------------------+-------------------+
Upshot: 2 3 * 4 5 6 - * +
Run as an inverse Polish notation:
Símbolo Lido Pilha
+--------------+---------------+
| 2 | 2 |
+--------------+---------------+
| 3 | 2 3 |
+--------------+---------------+
| * | 6 |
+--------------+---------------+
| 4 | 6 4 |
+--------------+---------------+
| 5 | 6 4 5 |
+--------------+---------------+
| 6 | 6 4 5 6 |
+--------------+---------------+
| - | 6 4 -1 |
+--------------+---------------+
| * | 6 -4 |
+--------------+---------------+
| + | 2 |
+--------------+---------------+
Upshot: 2
That’s what I call "A Lady Reply". Congratulations...
This site is also very instructive: http://www.buildyourownlisp.com/
13
If you can use something ready, see libmatheval or my library ae moon-based.
With ae, just do v=ae_eval(s), where s is a string containing the expression to be evaluated. This expression may contain variables defined before. ae compiles each expression a single time, which dilutes the cost into multiple evaluations. Below is a complete use example that tables a quadratic function:
ae_open();
ae_set("a",1);
ae_set("b",-5);
ae_set("c",6);
for (x=0.0; x<4.0; x+=0.25)
{
ae_set("x",x);
printf("%g\t%g\n",x,ae_eval("a*x^2+b*x+c"));
}
ae_close();
cool! (+1): in addition to the request still uses variables. I was also impressed with the "libmatheval" (apt-get intalall libmatheval) which I was unaware of.
7
Solution based on popen
Okay, okay, I admit it’s a little cheating. But since this question was asked last year, no one will notice :-)
#include <stdio.h>
int main(){
char s[100],com[100];
sprintf(com,"echo '%s'|bc -l",fgets(s,100,stdin));
FILE* calc=popen(com,"r");
printf("--> %s",fgets(s,100,calc));
}
popen allows you to "communicate" with an external command (in this case read its output).
See also manual bc. Testing:
$ calcula
4+4^100
--> 1606938044258990275541962092341162602522202993782792835301380
And if we’re not on Linux?
If unfortunately we are not on Unix, we can always try to replace line 4 by:
sprintf(com,"ssh uma.maq.unix 'echo \"%s\"| bc -l'",fgets(s,100,stdin));
or install Perl and
sprintf(com,"perl -e 'print eval \"%s\"'",fgets(s,100,stdin));
7
There is no function eval() standard in C. The solution to your problem is to look for a library that already does the same as the eval() does or develops on its own a function that interprets the expression and returns the result (which is good for learning).
In this case, a simple solution would be an algorithm of the type:
1 - Break the expression depending on the operators found. For example:
"3*5-1" seria quebrado em [3, *, 5, -, 1]
2 - Check that there are no errors in the expression.
3 - Analyze what is number and what is operator.
4 - Make the calculations between a left and right element considering the precedence that you will use. For example:
3 * 5
And then:
15 - 1
5 - Repeat until you have only one element, which will be the result.
If you use parentheses the thing gets more complicated, but just solve what is between parentheses first. For example:
(3*5 + 2) - 1 => 17 - 1
Another easier solution is to integrate your program into a scripting language. Take a look at Moon, which is very easy to integrate into a program made in C.
6
My answer will not be in C, but I hope to help in a possible implementation in this language. ;)
In most compilable languages, either in "machine code" or bytecode, there is this problem related to the interpretation of formulas or functions of variables.
At the time of college I did an interpreter of mathematical functions with variables in Delphi for the subject of operational research and used it in several optimization algorithms where you could type a function and the program found the maximum point(s) and/or minimum(s) of it. It’s not as complicated as it sounds. Too bad you don’t have the source code on hand now.
Some time later, already working with Java, I made another implementation of a class to facilitate the interpretation of simple expressions. I never got to use in production, so ended up staying in the prototype phase, that is, it has not been extensively tested, is subject to bugs and only supports the most basic mathematical operations. In addition, this implementation was made for Java 1.4, so it also does not use several new language features. I’m sure this code could be much better, but it might help to create a C version++.
import java.math.BigDecimal;
import java.text.MessageFormat;
/**
* Calcula o resultado de uma dada expressão, de acordo com os coeficientes definidos.
*
* A expressão é uma fórmula matemática válida, podendo conter os coeficiente (variáveis),
* operadores ("+", "-", "*", "/" e "^" -> adição, subtração, multiplicação, divisão e
* potenciação) e parêntesis.
*
* Os coeficientes podem ser refenciados na fórmula pelo índice do vetor entre chaves {n}
* ou pelas letras de "A" a "Z", sendo "A" equivalente ao índice 0 (zero) do vetor.
*
* Exemplos: "({0} + {1} + {2}) - {3}" ou "(A + B) / (C - D) ^ 2"
*
* Precedência de Operadores (quando não há parêntesis):
* 1. Potenciação
* 2. Multiplicação e Divisão
* 3. Adição e subtração
*/
public class Expressao {
private static int TIPO_NUMERO = 1;
private static int TIPO_OPERADOR = 2;
private static int TIPO_PONTO = 3;
private static int TIPO_LETRA_AZ = 4;
private static int TIPO_CHAVE_ABRIR = 5;
private static int TIPO_CHAVE_FECHAR = 6;
private static int TIPO_PARENTESIS_ABRIR = 7;
private static int TIPO_PARENTESIS_FECHAR = 8;
private static String parentesisFaltando = "Parêntesis faltando a partir da posição {0}!";
private static String valorEsperado = "Coeficiente ou número esperado na posição {0}!";
private static String numeroEsperado = "Número esperado na posição {0}!";
private static String indiceEsperado = "Índice de coeficiente esperado na posição {0}!";
private static String chaveEsperada = "Chave de fechamento esperada na posição {0}!";
private static String divisaoPorZero = "Divisão por zero na posição {0}!";
private static String operadorEsperado = "Operador esperado na posição {0}!";
private static String indiceInvalido = "Índice de coeficiente inválido na posição {0}!";
private int posExpressao;
private int tipoElemento;
private char letra;
private String expressao;
private BigDecimal[] coeficientes;
/**
* Atalho para execução alternativa
*/
public static BigDecimal calcular(String expressao, BigDecimal[] coeficientes) {
try {
Expressao exp = new Expressao(expressao, coeficientes);
return exp.calcular();
} catch (Exception e) {
LogLE.logError(e);
return Calc.ZERO;
}
}
/**
* Atalho para execução alternativa
*/
public static BigDecimal calcular(String expressao, String[] coeficientes) {
try {
Expressao exp = new Expressao(expressao, coeficientes);
return exp.calcular();
} catch (Exception e) {
return Calc.ZERO;
}
}
/**
* Atalho para execução alternativa
*/
public static BigDecimal calcular(String expressao, Object[] coeficientes) {
try {
Expressao exp = new Expressao(expressao, coeficientes);
return exp.calcular();
} catch (Exception e) {
LogLE.logError(e);
return Calc.ZERO;
}
}
/**
* Constrói um avaliador para a expressão e respectivos coeficientes (variáveis)
*
* Exemplo: new Expressao("(A + B + C) - D", new BigDecimal[] {v1, v2, v3, v4}
*/
public Expressao(String expressao, BigDecimal[] coeficientes) throws Exception {
this.expressao = expressao.replaceAll("\\s", "").toUpperCase();
this.coeficientes = coeficientes;
this.posExpressao = -1;
}
/**
* Constrói um avaliador para a expressão e respectivos coeficientes (variáveis)
*
* Exemplo: new Expressao("({0} + {1} + {2}) - {3}", new String[] {s1, s2, s3, s4}
*/
public Expressao(String expressao, String[] coeficientes) throws Exception {
this.expressao = expressao.replaceAll("\\s", "").toUpperCase();
this.coeficientes = new BigDecimal[coeficientes.length];
for (int i = 0; i < coeficientes.length; i++) {
this.coeficientes[i] = Calc.toBigDecimal(coeficientes[i]);
}
this.posExpressao = -1;
}
/**
* Constrói um avaliador para a expressão e respectivos coeficientes (variáveis)
* Os coeficientes podem ser String, BigDecimal, Integer ou Double
*
* Exemplo: new Expressao("({0} + {1} + {2}) - {3}", new Object[] {o1, o2, o3, o4}
*/
public Expressao(String expressao, Object[] coeficientes) throws Exception {
this.expressao = expressao.replaceAll("\\s", "").toUpperCase();
this.coeficientes = new BigDecimal[coeficientes.length];
for (int i = 0; i < coeficientes.length; i++) {
if (coeficientes[i] == null) {
this.coeficientes[i] = Calc.ZERO;
} else if (coeficientes[i] instanceof String) {
this.coeficientes[i] = Calc.toBigDecimal((String) coeficientes[i]);
} else if (coeficientes[i] instanceof BigDecimal) {
this.coeficientes[i] = Calc.toBigDecimal((BigDecimal) coeficientes[i]);
} else if (coeficientes[i] instanceof Double) {
this.coeficientes[i] = Calc.toBigDecimal(((Double) coeficientes[i]).doubleValue());
} else if (coeficientes[i] instanceof Integer) {
this.coeficientes[i] = Calc.toBigDecimal(((Integer) coeficientes[i]).intValue());
} else {
//tenta converter o objeto para String e depois para BigDecimal
this.coeficientes[i] = Calc.toBigDecimal(coeficientes[i].toString());
}
}
this.posExpressao = -1;
}
//retorna verdadeiro se o próximo caracter for o início de um valor válido com ou sem sinal
private boolean ehValorSinal() {
return tipoElemento == TIPO_NUMERO || tipoElemento == TIPO_CHAVE_ABRIR || tipoElemento == TIPO_PARENTESIS_ABRIR ||
(tipoElemento == TIPO_OPERADOR && (letra == '+' || letra == '-') || tipoElemento == TIPO_LETRA_AZ);
}
/**
* Avalia a expressão de acordo com os coeficientes definidos e retorna o resultado
*/
public BigDecimal calcular() throws Exception {
BigDecimal resposta = Calc.ZERO;
proximoElemento();
if (!EOF()) {
if (!ehValorSinal()) {
Erro(valorEsperado);
}
resposta = expressaoPrecedencia();
}
while (!EOF()) {
if (tipoElemento == TIPO_OPERADOR) {
char operador = letra;
proximoElemento();
if (!ehValorSinal()) {
Erro(valorEsperado);
}
BigDecimal outroValor = expressaoPrecedencia();
if (operador == '+') {
resposta = Calc.soma(resposta, outroValor);
} else if (operador == '-') {
resposta = Calc.subtrai(resposta, outroValor);
}
} else {
Erro(operadorEsperado);
}
}
return resposta;
}
//avalia uma expressão com precedência 1, atualmente multiplicação e divisão (analisador sintático)
private BigDecimal expressaoPrecedencia() throws Exception {
BigDecimal resposta = expressaoPrecedencia2();
while (!EOF() && (tipoElemento == TIPO_OPERADOR && (letra == '*' || letra == '/'))) {
char operador = letra;
proximoElemento();
if (ehValorSinal()) {
BigDecimal outroValor = expressaoPrecedencia2();
if (operador == '*') {
resposta = Calc.multiplica(resposta, outroValor);
} else if (operador == '/') {
if (Calc.ehZero(outroValor)) {
Erro(divisaoPorZero);
}
resposta = Calc.divide(resposta, outroValor);
}
}
}
return resposta;
}
//avalia uma expressão com precedência 2, atualmente a potenciação (analisador sintático)
private BigDecimal expressaoPrecedencia2() throws Exception {
BigDecimal resposta = valorSinal();
while (!EOF() && (tipoElemento == TIPO_OPERADOR && letra == '^')) {
char operador = letra;
proximoElemento();
if (ehValorSinal()) {
BigDecimal outroValor = valorSinal();
if (operador == '^') {
resposta = Calc.potencia(resposta, outroValor);
}
}
}
return resposta;
}
//avalia um valor válido na expressão com ou sem um operador unitário (analisador sintático)
private BigDecimal valorSinal() throws Exception {
//operador unitário
if (tipoElemento == TIPO_OPERADOR && (letra == '+' || letra == '-')) {
char operadorUnitario = letra;
proximoElemento();
BigDecimal valor = valor();
if (operadorUnitario == '-') {
valor = Calc.multiplica(valor, -1);
}
return valor;
} else {
return valor();
}
}
//avalia um valor válido na expressão: {n}, 9.99, 9.99, (...), A (analisador sintático)
private BigDecimal valor() throws Exception {
if (tipoElemento == TIPO_PARENTESIS_ABRIR) {
int numParentesis = 1;
int posIni = posExpressao + 1;
do {
proximoElemento();
if (letra == '(') {
numParentesis++;
} else if (letra == ')') {
numParentesis--;
}
} while (numParentesis > 0 && posExpressao < expressao.length());
if (posExpressao >= expressao.length()) {
Erro(parentesisFaltando);
} else {
proximoElemento();
Expressao exp = new Expressao(Texto.cortar(expressao, posIni, posExpressao - posIni - 1), coeficientes);
return exp.calcular();
}
} else if (tipoElemento == TIPO_CHAVE_ABRIR) {
//coeficiente
proximoElemento();
if (EOF() || tipoElemento != TIPO_NUMERO) {
Erro(indiceEsperado);
}
int indice = numeroInteiro();
if (EOF() || tipoElemento != TIPO_CHAVE_FECHAR) {
Erro(chaveEsperada);
}
if (indice >= coeficientes.length || indice < 0) {
Erro(indiceInvalido);
}
proximoElemento();
return Calc.toBigDecimal(coeficientes[indice]);
} else if (tipoElemento == TIPO_NUMERO) {
//número
return numeroReal();
} else if (tipoElemento == TIPO_LETRA_AZ) {
int indice = letra - 'A';
if (indice >= coeficientes.length || indice < 0) {
Erro(indiceInvalido);
}
proximoElemento();
return Calc.toBigDecimal(coeficientes[indice]);
}
Erro(valorEsperado);
return null;
}
//avalia um número real no formato 9.99 (analisador sintático)
private BigDecimal numeroReal() throws Exception {
String numero = numeroTexto();
if (!EOF() && tipoElemento == TIPO_PONTO) {
proximoElemento();
if (!EOF() && tipoElemento == TIPO_NUMERO) {
numero += "," + numeroTexto();
} else {
Erro(numeroEsperado);
}
}
return Calc.toBigDecimal(numero);
}
//avalia um número inteiro (analisador sintático)
private int numeroInteiro() {
return Integer.parseInt(numeroTexto());
}
//avalia uma sequência de caracteres numéricos (analisador sintático)
private String numeroTexto() {
String num = new String(new char[] {letra});
do {
proximoElemento();
if (!EOF() && tipoElemento == TIPO_NUMERO) {
num += letra;
}
} while (!EOF() && tipoElemento == TIPO_NUMERO);
return num;
}
//analisador léxico
private void proximoElemento() {
if (posExpressao < expressao.length() - 1) {
letra = expressao.charAt(++posExpressao);
} else {
posExpressao++;
letra = 0;
}
tipoElemento = 0;
switch (letra) {
case '{':
tipoElemento = TIPO_CHAVE_ABRIR;
break;
case '}':
tipoElemento = TIPO_CHAVE_FECHAR;
break;
case '(':
tipoElemento = TIPO_PARENTESIS_ABRIR;
break;
case ')':
tipoElemento = TIPO_PARENTESIS_FECHAR;
break;
case '.':
tipoElemento = TIPO_PONTO;
break;
case '+':
case '-':
case '*':
case '/':
case '^':
case '%':
tipoElemento = TIPO_OPERADOR;
break;
default:
if (letra >= 'A' && letra <= 'Z') {
tipoElemento = TIPO_LETRA_AZ;
} else if (letra >= '0' && letra <= '9') {
tipoElemento = TIPO_NUMERO;
}
break;
}
}
//verifica se chegou ao final da expressão
private boolean EOF() {
return posExpressao >= expressao.length() ;
}
//lança um erro (Exception com descrição) quando encontrar qualquer problema na avaliação da expressão
private void Erro(String mensagem) throws Exception {
throw new Exception(MessageFormat.format(mensagem, new Object[] { Calc.imprimeInt(posExpressao) }));
}
//rotinas de inicialização de vetor com Strings
public static BigDecimal[] getVetor(String v1, String v2) {
return new BigDecimal[] {Calc.toBigDecimal(v1), Calc.toBigDecimal(v2)};
}
public static BigDecimal[] getVetor(String v1, String v2, String v3) {
return new BigDecimal[] {Calc.toBigDecimal(v1), Calc.toBigDecimal(v2), Calc.toBigDecimal(v3)};
}
public static BigDecimal[] getVetor(String v1, String v2, String v3, String v4) {
return new BigDecimal[] {Calc.toBigDecimal(v1), Calc.toBigDecimal(v2), Calc.toBigDecimal(v3), Calc.toBigDecimal(v4)};
}
public static BigDecimal[] getVetor(String v1, String v2, String v3, String v4, String v5) {
return new BigDecimal[] {Calc.toBigDecimal(v1), Calc.toBigDecimal(v2), Calc.toBigDecimal(v3),
Calc.toBigDecimal(v4), Calc.toBigDecimal(v5)};
}
public static BigDecimal[] getVetor(String v1, String v2, String v3, String v4, String v5, String v6) {
return new BigDecimal[] {Calc.toBigDecimal(v1), Calc.toBigDecimal(v2), Calc.toBigDecimal(v3),
Calc.toBigDecimal(v4), Calc.toBigDecimal(v5), Calc.toBigDecimal(v6)};
}
//com BigDecimals
public static BigDecimal[] getVetor(BigDecimal v1, BigDecimal v2) {
return new BigDecimal[] {v1, v2};
}
public static BigDecimal[] getVetor(BigDecimal v1, BigDecimal v2, BigDecimal v3) {
return new BigDecimal[] {v1, v2, v3};
}
public static BigDecimal[] getVetor(BigDecimal v1, BigDecimal v2, BigDecimal v3, BigDecimal v4) {
return new BigDecimal[] {v1, v2, v3, v4};
}
public static BigDecimal[] getVetor(BigDecimal v1, BigDecimal v2, BigDecimal v3, BigDecimal v4, BigDecimal v5) {
return new BigDecimal[] {v1, v2, v3, v4, v5};
}
public static BigDecimal[] getVetor(BigDecimal v1, BigDecimal v2, BigDecimal v3, BigDecimal v4, BigDecimal v5, BigDecimal v6) {
return new BigDecimal[] {v1, v2, v3, v4, v5, v6};
}
//com Objects
public static Object[] getVetor(Object v1, Object v2) {
return new Object[] {v1, v2};
}
public static Object[] getVetor(Object v1, Object v2, Object v3) {
return new Object[] {v1, v2, v3};
}
public static Object[] getVetor(Object v1, Object v2, Object v3, Object v4) {
return new Object[] {v1, v2, v3, v4};
}
public static Object[] getVetor(Object v1, Object v2, Object v3, Object v4, Object v5) {
return new Object[] {v1, v2, v3, v4, v5};
}
public static Object[] getVetor(Object v1, Object v2, Object v3, Object v4, Object v5, Object v6) {
return new Object[] {v1, v2, v3, v4, v5, v6};
}
}
I think that’s the simplest and least efficient interpreter there is. I don’t remember exactly the theory, but I learned in the compiler class in college and I always brought a cost-effective code in the sense that it’s simple to implement and meets simpler requirements. That is, it is not good to implement an HP12C (if you want one, go to site of @epx), or calculations for the stock exchange.
This technique basically consists of implementing a parser with a method for each grammar rule, from the most complex to the simplest.
If anyone has anything to add, feel free to comment.
Browser other questions tagged c mathematics parser eval
You are not signed in. Login or sign up in order to post.
I think that I C doesn’t have
eval, and that you need to basically build a parser of mathematical expressions.– bfavaretto
In pure C there is nothing, or you will have to write your own library, which is something really interesting, worth learning, or looking for some library ready. Google suggested this one: http://expreval.sourceforge.net
– C. E. Gesser
This is one of the "n" reasons why low-level language (C, C++) is not used except when very necessary. There’s always the need to interpret something and it’s always trouble. What many programs do is incorporate an interpreter of a more or less established language (Javascript, Python, Lua) to become "Scriptable" and/or interpret high-level structures more easily.
– epx
@epx Interpreted languages have the facility to rely on their own interpreter to solve expressions. But if the type of expression you want to evaluate does not use the same language syntax, the problem would be the same.
– C. E. Gesser
@epx Also, run
evalon something typed by the user is at least dangerous.– Guilherme Bernal
@epx, I would already say the opposite: using a language interpreted only by "Eval" can lead to very large insecurity situations in the system. Using Eval in user-typed text is very dangerous and can lead to code Injection: http://en.wikipedia.org/wiki/Code_injection#Dynamic_evaluation_vulnerabilities.
– user568459
@Guilhermebernal did not speak at any time of using "Eval". I talked about interpreting data, whether XML, JSON, a mathematical expression, a configuration file... all of this always appears in a system of sufficiently large size. " Any sufficiently complicated C or FORTRAN program contains a improvised, poorly specified, bugle and slow implementation of half of Common Lisp."
– epx
eval, my dear friend, it’s just notevilbecause of a letter. It really can be evil, but hackers/Ammers love it :)– Paulo Roberto Rosa
@epx, there are libraries already with high level of development and well established for C that interpret all these types of data that you cited. If the programmer prefers to do it alone instead of searching a library on the Internet, the language is not to blame...
– user568459