I'm developing this program that should receive an expression from the user and do the calculation. Ex:
Enter an expression
3 * 5-1
14
My problem is how to handle the expression sent by the user. It was recommended to use something like eval , but I did not find anything equivalent in the C language. Does anyone have something equivalent?
In C there is no "eval" or anything similar to running runtime code.
So the only way to execute an expression like this is to create a sub-language. You need to set 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 the .
Expressions written in this notation are executed as follows:
The expression 3*5-1 would be written in inverse polite notation as 3 5 * 1 - . The great advantage of this notation is that parentheses are not required. If the expression were 3*(5-1) , the equivalent polynomial would be 3 5 1 - * . Executing this type of expressions is trivial with the algorithm above. Now the real problem: How to transform an expression into the usual notation for inverse polynomial notation?
For this there is an algorithm called Shunting Yard .
Assuming all of your operators are associative from the left (ie + , - , * , / ), it can be described as:
As long as there are symbols to read ...
If it's an operator (let's call it o1 ), then:
o2 ) such that the o1 precedence is less than o2 , move o2 to output.
o1 on the stack. If it's a parentheses lock:
Example:
Consider the expression 2*3+4*(5-6) .
Apply 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 - * + |
+--------------+---------------------------+------------------+-------------------+
Result: 2 3 * 4 5 6 - * +
Run as a reverse 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 |
+--------------+---------------+
Result: 2
If you can use something ready, see libmatheval or my library #
With ae , just make 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 once, which dilutes the cost in multiple evaluations. Here is a complete example of a table that uses 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();
There is no standard eval() function in C. The solution to your problem is to look for a library that already does the same thing as eval() does or develop 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 according to the found operators. 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 - Do the calculations between a left and a 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 it is only to solve what is in parentheses first. For example:
(3*5 + 2) - 1 => 17 - 1
Another easy solution is to integrate your program into a scripting language. Take a look at Moon , which is very easy to integrate into a C program.
Solution based on popen
Okay, okay, I'll admit it's a bit cheating. But as this question was asked last year, no one will give for it: -)
#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
What if we're not on Linux?
If unhappily we are not in Unix, we can always try to replace line 4 with:
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));
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 variable functions.
At the time of college I did a mathematical function interpreter with variables in Delphi for the subject of operational research and I used it in various optimization algorithms where you could type a function and the program found the point (s) maximum (s) and / or minimum (s). It's not as complicated as it sounds. Too bad it does not have the source code at 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 it in production, so it ended up being in the prototype phase, that is, it was not 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 a lot better, but maybe it helps 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 this is the simplest and least efficient kind of interpreter. I do not remember exactly the theory, but I've learned in the field of compilers in college and 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 the @epx site ), nor calculations for the values.
This technique basically consists of implementing a syntactic parser with a method for each grammar rule, from the most complex to the simplest.
If anyone has something to add, feel free to comment.