How to perform an algebraic expression on a string in C

Question

My program has the following objective::

Given a function, my program replaces the function'X(s)' by any number.

The code below exemplifies what was said.

//funcao a ser trabalhada
char funcao[150]  = "(x^2)*5";
int tamanho = strlen(funcao);

//Substitui o x da funcao por um valor dado
    for(int i = 0; i < tamanho; i++) {
        if(funcao[i] == 'x')
            funcao[i] = '2';
    }

The result of this procedure returns me the string "(2 2)*5".

How to calculate this equation?

Answer 1

The usual ways to solve this problem is by either writing a parser (as suggested by Maniero; a simple example - in Javascript - here) that generates an abstract representation of the data, or perhaps converting the expression to the Inverse Polish Notation in a process of Parsing simpler and then evaluating it (here a PDF with instructions, in Pascal - I do not know the source well, I found in Google).

The first form is more flexible (in the related question, the result was used to solve simple equations of the second degree), but the second is simpler. I’ll give you an explanation well simplified here (because implementing in C is kind of boring, especially for me who have little experience) along with links to implementation references, so you can study them more deeply.

1. The purpose of postfixed notation is to pass all operators pro final - and not pro middle - of their operands. For example the expression:

   1 + 2 * 3

   This would be in the postfixed notation:

   1 2 3 * +
   

   Already the expression:

   (1 + 2) * 3

   Would look like this:

   1 2 + 3 *
   

   Etc. To interpret these expressions, consider that each operator applies to the last two operands read, removing them from the list and replacing them all with the result of the operation. The next operator does the same, and the process continues until only about a single number on the list (more details below).

   An advantage of this notation is that parentheses are unnecessary - any expression can be represented in a way that the computation occurs in the desired correct order.

   • The conversion between the infix and posfixo formats can be done through the shunting algorithm-Yard.

     To understand it, consider that each operator has both a precedence how much a associativity: apply first, for example, and both associate to the left. A - B - C applies as (A - B) - C and not as A - (B - C), but A^B^C applies as A^(B^C) and not the other way around. Subexpressions in parentheses apply before the rest.

     The algorithm works by reading each token (number, operator, open parenthesis or close parenthesis) of the input and then placing it either on the output or in a stack. Numbers always go to the output. Operators go to the stack, but before they remove from the stack (sending to the output) any operator whose precedence is less or less-or-equal to it (depending on the associativity). Open parentheses go to the stack, and close parentheses demycle everything until the corresponding parentheses open and play in the output.

     1 + 2 * 3     []
     _ + 2 * 3     []       1
       _ 2 * 3     [+]      1
         _ * 3     [+]      1 2
           _ 3     [+, *]   1 2
             _     [+, *]   1 2 3
                   [+]      1 2 3 *
                   []       1 2 3 * +
     
     (1 + 2) * 3   []
     _1 + 2) * 3   [(]
      _ + 2) * 3   [(]      1
        _ 2) * 3   [(, +]   1
          _) * 3   [(, +]   1 2
           _ * 3   []       1 2 +
             _ 3   [*]      1 2 +
               _   [*]      1 2 + 3
                   []       1 2 + 3 *
     
     1 + 2*3 / (4 ^ (5+6) )   []
     _ + 2*3 / (4 ^ (5+6) )   []                   1
       _ 2*3 / (4 ^ (5+6) )   [+]                  1
         _*3 / (4 ^ (5+6) )   [+]                  1 2
          _3 / (4 ^ (5+6) )   [+, *]               1 2
           _ / (4 ^ (5+6) )   [+, *]               1 2 3
             _ (4 ^ (5+6) )   [+, /]               1 2 3 *
               _4 ^ (5+6) )   [+, /, (]            1 2 3 *
                _ ^ (5+6) )   [+, /, (]            1 2 3 * 4
                  _ (5+6) )   [+, /, (, ^]         1 2 3 * 4
                    _5+6) )   [+, /, (, ^, (]      1 2 3 * 4
                     _+6) )   [+, /, (, ^, (]      1 2 3 * 4 5
                      _6) )   [+, /, (, ^, (, +]   1 2 3 * 4 5
                       _) )   [+, /, (, ^, (, +]   1 2 3 * 4 5 6
                        _ )   [+, /, (, ^]         1 2 3 * 4 5 6 +
                          _   [+, /]               1 2 3 * 4 5 6 + ^
                              [+]                  1 2 3 * 4 5 6 + ^ /
                              []                   1 2 3 * 4 5 6 + ^ / +
     

     Example in C in rosettacode.

2. To evaluate an expression in the postfixed notation, it is necessary to use a stack. Each read element is stacked if it is a number, and if it is an operator it pops two numbers and applies the operator to the same:

   1 2 3 * +    []
   _ 2 3 * +    [1]
     _ 3 * +    [1, 2]
       _ * +    [1, 2, 3]
         _ +    [1, (2*3)] -> [1, 6]
           _    [(1+6)]    -> [7]
   
   1 2 + 3 *    []
   _ 2 + 3 *    [1]
     _ + 3 *    [1, 2]
       _ 3 *    [(1+2)] -> [3]
         _ *    [3, 3]
           _    [(3*3)] -> [9]
   
   1 2 3 * 4 5 6 + ^ / +   []
   _ 2 3 * 4 5 6 + ^ / +   [1]
     _ 3 * 4 5 6 + ^ / +   [1, 2]
       _ * 4 5 6 + ^ / +   [1, 2, 3]
         _ 4 5 6 + ^ / +   [1, (2*3)] -> [1, 6]
           _ 5 6 + ^ / +   [1, 6, 4]
             _ 6 + ^ / +   [1, 6, 4, 5]
               _ + ^ / +   [1, 6, 4, 5, 6]
                 _ ^ / +   [1, 6, 4, (5+6)] -> [1, 6, 4, 11]
                   _ / +   [1, 6, (4^11)] -> [1, 6, 4194304]
                     _ +   [1, (6/4194304)] -> [1, 0.00000143]
                       _   [(1+0.00000143)] -> [1.00000143]
   

   Example in C in rosettacode.

Answer 2

If you are not limited to the basic standard and can use POSIX (which describes the function popen()), then passes the string to an external calculator, for example bc.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int calculo(const char *expression) {
    FILE *bc;
    char command[1000];
    char result[1000];

    snprintf(command, sizeof command, "echo '%s' | bc", expression);
    bc = popen(command, "r");
    if (!bc) return -1;
    if (!fgets(result, sizeof result, bc)) return -1;
    pclose(bc);
    return strtol(result, NULL, 10);
}

int main(void) {
    // funcao a ser trabalhada
    char funcao[150] = "(x^2)*5";
    int tamanho = strlen(funcao);

    // Substitui o x da funcao por um valor dado
    int i;
    for (i = 0; i < tamanho; i++) {
        if (funcao[i] == 'x') funcao[i] = '2';
    }
    int valor = calculo(funcao);
    printf("%s ==> %d\n", funcao, valor);
    return 0;
}

On my machine, the result of the executable is

% ./a.out
(2^2)*5 ==> 20