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.

Answer 1

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.