Parsing mathematical expressions with two values that have parentheses and minus signs

Question

I'm trying to parse equations like the ones below, which only have two values or the square root of a certain value, from a text file:

100+100

-100-100

-(100)+(-100)

sqrt(100)

by the minus signs, parentheses and the operator symbol in the middle and the square root, and I have no idea how to start off... I've got the file part done and the simple calculation parts except that I couldnt get my program to solve the equations in the above.

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

main(){
    FILE *fp;
    char buff[255], sym,sym2,del1,del2,del3,del4;
    double num1, num2;
    int ret;
    fp = fopen("input.txt","r");

    while(fgets(buff,sizeof(buff),fp)!=NULL){
        char *tok = buff;
        sscanf(tok,"%lf%c%lf",&num1,&sym,&num2);

        switch(sym){
            case '+': printf("%lf\n", num1+num2);
                    break;
            case '-': printf("%lf\n", num1-num2);
                    break;
            case '*': printf("%lf\n", num1*num2);
                    break;
            case '/': printf("%lf\n", num1/num2);
                    break;
            default: printf("The input value is not correct\n");
                    break;
        }
    }
    fclose(fp);
}

That is what I have written for the other basic operations without parentheses and the minus sign for the second value and it works great for the simple ones. I'm using a switch statement to calculate the add, sub, mul and div operations but I'm not sure how to properly use the sscanf function (if I am not using it properly) or if there is another way, such as using a function like strtok to properly parse the parentheses and the minus signs. Any kind help?

Answer 1

Parsing expressions, with parentheses and unequal operator precedence, is THE standard parsing example in just about every compiler textbook in existence. Function calls aren't USUALLY part of that example, but they are simple enough to add. Rather than go trial-and-error, your life will be a lot easier in the long run if you learn how to do it for real.

The most accessible introduction to building hand-constructed parsers I have seen is Jack Crenshaw's "Let's Build A Compiler".

The most accessible textbook I've seen on compiler construction is Wirth's "Compiler Construction". It describes hand-coded recursive descent parsing.

The canonical references on compiler construction are the various Dragon Books. I personally used the Green Dragon Book and found it usable, although the focus is on mechanically-generated LALR parsers rather than hand-coded parsers.

Answer 2

A better approach There are many ways to parse and evaluate expressions as a recursive data structure. Any expression can be defined as following:

expression -> term + term - term

term -> factor*factor/factor
factor -> variabler، number، expression as 10 +5*B consist of 2 terms 10، 5*B.

Second term contains 2 factors 5 and B.

Here is a sequence you will follow

1. input an expression as 9/3-(100 5)
2. the parser gets the first term 9/3.
3. get each factor and divide the integers the result is 3
4. get the second term term (100 56). Start recursively analysing the second sub expression.
5. get each terms and add them. The result is 156: return from the recursive call, 3-156 =3.

This is complex concept that takes time to get used to.

If you want an example tell me. (I didn't give example because it will be very long). But if you want an example I will happily give you one).

If you feel confused you can google " recursive expression parsing".

Answer 3

You should build AST(Abstract Syntax Tree). Build it with respect for precedence so multiplication/division comes first before subtraction or addition. Parentheses also should be handled but that only sound complex in theory.

My simple parser I wrote some time ago

As you can see from the source code I am using templates. Just simple linked lists which let me distinguish input such as VALUE OPERATION VALUE(1+2 or 3*6).

When I meet parentheses like 1+2*(4+5) only 1+2 and 4+5 matches a template, so I reduce them and I have VAL*(VAL). Now OPEN_PAREN VALUE CLOSE_PAREN) matches a template and so I reduce it into VAL. Now I have VAL*VAL. And that's all.

The source code was written for learning purposes by me so I tried to keep it clean and small. In case you need an explanation, feel free to ask in the comments.