Receive an expression and calculate in C
I am developing this little 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 treat the expression sent by the user. I was recommended to use something like eval, but I did not find anything equivalent in the C language.
5 answers
In C there is no "eval" or anything similar to run code at runtime.
So the only way to execute an expression like this is by creating 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 Reverse Polish Notation.
Expressions written in this notation are executed as follows:
- create an empty stack.
- when reading a number, add it to the top of the stack.
- when reading an operator, remove the last two elements from the stack, apply the operation and add the resulting number to it.
- at the end of the process (no more input) there should be only one element in the stack, the result.
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 required. If the expression was 3*(5-1), the equivalent polish would be 3 5 1 - *. Running these kinds of expressions is trivial with the algorithm above. Now the real problem: How to turn an expression in the usual notation to the Reverse Polish Notation?
For this there is an algorithm called Shunting Yard.
Assuming all its operators are associative by the left (i.e.: +, -, *, /), he it can be described like this:
-
As long as there are symbols to be read...
- if it is a number, add to the output.
-
If it is an operator (let's call it
o1), then:- as long as there is an operator at the top of the temporary stack (let's call
o2) such that the precedence ofo1is less thano2, moveo2to the output. - put
o1in the stack.
- as long as there is an operator at the top of the temporary stack (let's call
- if it is an opening of parentheses, put it in the temporary stack
-
If it is a parenthesis closure:
- as long as the top of the temporary stack is not an opening of parentheses, throw the top operator at the output.
- remove the parenthesis opening from the temporary stack.
- when you no longer have to read, move all the operators on the stack to the output.
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 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 |
+--------------+---------------+
Result: 2
If you can use something ready, see libmatheval or My Moon-based library Ae .
With ae, just do v=ae_eval(s), where s is a string containing the expression to be evaluated. This expression can contain variables defined before. ae compiles each expression only once, which dilutes the cost in multiple evaluations. Below is a complete example of use 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();
There is no standard eval() function in C. The solution to your problem is to look for a library that already does the same as eval() does, or to develop on your 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 based on the operators found. For example:
"3*5-1" seria quebrado em [3, *, 5, -, 1]
2-make sure 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 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 it gets more complicated, but just solve what is in parentheses first. For example:
(3*5 + 2) - 1 => 17 - 1
Other solution easier is to integrate your program into a scripting language. Take a look at Lua , which is quite easy to integrate into a program made in C.
Popen based solution
Ok, ok, I admit it's a bit cheating. But since this question was asked last year, no one will find 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 BC manual . Testing:
$ calcula
4+4^100
--> 1606938044258990275541962092341162602522202993782792835301380
What if we're not on Linux?
If unfortunately we are not on 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 won't be in C, but I hope to help with a possible implementation in this language. ;)
In most compilable languages, whether in "machine code" or bytecode , there is this problem related to interpreting formulas or variable functions.
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 various optimization algorithms where you could enter a function and the program would find its maximum and/or minimum Point(s). It's not as complicated as it sounds. A pity not to 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 has not been extensively tested, is subject to bugs and only supports operations more basic mathematics. In addition, this implementation was made for Java 1.4, so it also does not use several new features of the language. I'm sure this code could be much better, but maybe it helps so that a C++version can be created.
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 type of interpreter that exists. I do not remember exactly the theory, but I learned in the matter of compilers in college and always brought a cost-effective code in the sense that it is simple to implement and meets well simpler requirements. That is, it is not good to implement an HP12C (if you want one, go to the website of @epx), nor 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 someone has something to complement, feel free to comment.