How to properly parse numbers in an arithmetic expression, differentiating positive and negative ones?

Question

I have an assignment in my Data Structures class in which I have to program a calculator that solves arithmetic expressions with the 4 basic operations and parenthesis, the input is done via the stdin buffer and the same with the output.

It was easy at the beginning, the teacher provided us the algorithms (how to transform the expression from the infix to the postfix and how to evaluate it) and the only goal was for us to implement our own stack and use it, but the calculator itself does not work quite well, and I think it is because of my parser.

This is the algorithm, and my code, used to parse the numbers, operators and parenthesis while putting them into an array to store the expression in a way that it is easier to evaluate later.

// saida is an array of pairs of integers, the first value of the pair is the value of the info (the number itself or the ASCII value of the operator)
// The second value is an indicator of whether it is a number or a operator
for (i = 0; i < exp_size; i++) {
    c = expression[i];

    // If the current char is a digit, store it into a helper string and keep going until a non-digit is found
    // Then atoi() is used to transform this string into an int and then store it.
    if (c >= '0' && c <= '9') {
        j = 1, k = i+1;
        tempInt[0] = c;
        while(expression[k] >= '0' && expression[k] <= '9') {
            tempInt[j++] = expression[k];
            k++;
        }
        tempInt[j] = '\0';
        saida[saidaIndex][0] = atoi(tempInt);
        saida[saidaIndex++][1] = 0;
        i = k-1;
    }

    // If the character is an operator, the algorithm is followed.
    else if (c == '+' || c == '-' || c == '*' || c == '/') {
        while(pilha->size > 0 && isOpBigger( stack_top(pilha), c )) {
            saida[saidaIndex][0] = stack_pop(pilha);
            saida[saidaIndex++][1] = 1;
        }
        stack_push(c, pilha);
    }
    else if (c == '(') stack_push(c, pilha);
    else if (c == ')') {
        j = stack_pop(pilha);
        while(j != '(') {
            saida[saidaIndex][0] = j;
            saida[saidaIndex++][1] = 1;
            j = stack_pop(pilha);
        }
    }
}

The problem is, in this code I can't tell if a minus sign indicates a subtraction operator or a negative number (I know that a minus operator is a sum with a negative number, but it didn't helped me solving this problem), I thought of the following, none with success:

Every time there is a minus sign, store a plus sign instead and let the next number be itself * -1. Wouldn't work in case the next number is already a negative one or if the minus sign is before an expression with parenthesis like 1 + 2 - (3 * 4).
If there is a space after the minus sign, it is an operator, if not, it is a negative number. Wouldn't work because there are not those rules on the input.

I have no experience whatsoever in interpreters and I really don't know how to proceed. The code works perfectly with valid expressions without negative numbers, but not with weird ones like () + 3 - (), but that's another problem.

Thanks for any help.

Instead of for (i = 0; i < exp_size; i++) (which forces an increment by only 1 each iteration) try char *p = expression; while (*p) { test/increment as needed } which allows you to read forward and consume characters in expression as required. e.g. if (*p == '-') while (isblank (*p)) p++; (or other tests to that effect, e.g. for (, 0-9, etc.) that let you read forward in your expression to determine what you are dealing with? — David C. Rankin
I've never thought about iterating through a string this way, going to try it, thank you! — Mikael
When parsing any string this adds a great deal of flexibility. You know you will have a nul-byte at the end of every string, so simply walking down the string with while (*p) and reading/checking as needed allows you to do all sorts of things, like *(p + x) to read ahead (or behind). You can even use multiple pointers for bracketing sub-expressions within the string, e.g char *sp, *ep; for start and end pointers, which allows you to set if (*p == '(') sp = p; and continuing until if (*p = ')') ep = p; and then handling what is between sp and ep. — David C. Rankin
This really opens up new horizons for me, thank you again, will have that in mind! — Mikael

deamentiaemundi deamentiaemundi · Accepted Answer · 2016-08-28T23:55:16

That is the problem called "unary minus" and can in your case (no variables) get solved by substitution.

The operator - is an unary minus if it is

preceded by a left parenthesis
preceded by another operator
the first character of the input

Now instead of storing a - you store a different character like, say m and assign it a higher precedence than the other operators (or the same as the exponentiation operator if you have one).

Another tip: don't use spaces to indicate anything, an arithmetic expression must work without any spaces or it is not correct.

How to properly parse numbers in an arithmetic expression, differentiating positive and negative ones?

1 Answers