Evaluate a simple mathematical expression with limited tools, no arrays, and no library functions

Question

Here's a question from the last year's first "Intro to programming" exam at my uni:

Using the getchar() function read an input sequence consisting of numbers, + and - signs. The output should be the result of those arithmetical operations.

For example, if the input is 10+13-12+25-5+100, the output should be 131.

Now, given that I have a little bit of C experience before attending uni, this problem seems easy to solve using pointers, arrays, etc.

But here's the catch: on the exam you can only use things that the students were taught so far. And given that this exam is only like a month after the start of the school year, your options are fairly limited.

You can only use variables, basic input/output stuff, operators (logical and bitwise), conditional statements and loops, functions.

That means no: arrays, strings, pointers, recursion, structures, or basically any other stuff that makes this easy.

How in the hell do I do this? Today is the second time I've spent 3 hours trying to solve this. I have solved it successfully, but only after "cheating" and using arrays, string functions (strtol), and pointers. It's important for me to know how to solve it by the rules, as I'll have similar stuff on the upcoming exam.

Edit: my attempts so far have amounted to using the while loop combined with getchar() for input, after which I just get stuck. I don't have the slightest idea of what I should do without using more "tools".

Answer 1

The solution is quite simple, but it might not be obvious for a beginner. I will not provide a complete program, but rather outline the steps needed to implement this with only a few variables.

First of all, it's important to notice two things:

1. Your input can only contain one of -, + or any digit (0123456789).
2. The getchar() function will read one character of input at a time, and will return EOF when the end of the input is reached or an error occurs.

Now, onto the solution:

1. Start by reading one character at a time, in a loop. You will only stop if you reach end of input or if an error occurs:

   int c;
   
   while ((c = getchar()) != EOF) {
       // logic here
   }
   

2. Start with an accumulator set to 0, and "add" digits to it every time you encounter a digit.

   // outside the loop
   int acc = 0;
   
   // inside the loop
   if (/* c is a digit */)
           acc = acc * 10 + (c = '0');
   

   Hint: that /* c is a digit */ condition might not be simple, you can put this in the else of the check for - and +.

3. Every time you encounter either - or +, remember the operation, and each time you encounter an operator, first perform the previous operation and reset the accumulator.

   // outside the loop
   int op = 0;
   int result = 0;
   
   // inside the loop
   if (c == '+' || c == '-') {
       if (op) {
           // there already is a previous operation to complete, do it
           if (op == '+')
               result += acc;
           else
               result -= acc;
       } else {
           // first operation encountered, don't do anything yet
           result = acc;
       }
   
       acc = 0; // reset
       op = c; // remember the current operation for the future
   }
   

4. When you reach the end of the input (i.e. you exit the loop), perform the last operation (same logic inside the if from point 3).

5. Output the result:

   You would normally write something like:

   printf("%d\n", result);
   

   However, if you cannot use string literals ("%d\n") or the printf() function, you will have to do so manually using putchar(). This is basically the opposite of what we did before to scan numbers into an accumulator.

   1. Print the sign first if needed, and make the value positive:

      if (result < 0) {
          putchar('-');
          result = -result;
      }
      

   2. Find the maximum power of 10 that is lower than your number:

      int div = 1;
      
      while (result / div / 10)
          div *= 10;        
      

   3. Use the power to extract and print each digit by division and modulo by 10:

      while (div) {
          putchar('0' + ((result / div) % 10));
          div /= 10;
      }
      

      Note: the '0' + at the beginning is used to convert digits (from 0 to 10) to the relative ASCII character.

   4. End with a newline:

      putchar('\n');
      

Answer 2

When writing a parser, I typically find myself that I "buffer" the next operation that "will be done". When the input changes state - you are reading digits, but then you read an operation - then you execute the "buffered" action and buffer the next operation that will be done in the future.

Example:

10+13-12
^^        - we read 10
  ^       - result=10  - we buffer that we *will* have to do + in the future
   ^^     - reading 13
     ^    - och we stopped reading numbers!
            we execute _buffered_ operation `+` , so we do result += 13
            and buffer `-` to be done in the future
      ^^  - we read 12
        ^ - och, EOF! we execute buffered operation `-` , so we do result -= 12
          - etc.

The code:

#include <stdio.h>
int main() {
    int result = 0; // represents current result
    int temp = 0; // the temporary number that we read into
    int op = 0; // represents the _next_ operation that _will_ be done
    while (1) {
        int c = getchar();
        switch (c) {
        // we read an operation, so we should calculate _the previous_ operation
        // or this is end of our string
        case '+': case '-': case EOF:
            if (op == 0) {
                // we have nothing so far, so start with first number
                result = temp;
            } else if (op == '+') {
                result += temp;
            } else if (op == '-') { 
                result -= temp;
            }
            // the next operation we will do in future is stored in op
            op = c;
            // current number starts from 0
            temp = 0;
            break;
        case '0': case '1': case '2': case '3': case '4':
        case '5': case '6': case '7': case '8': case '9':
            // read a digit - increment temporary number
            temp *= 10;
            temp += c - '0';
            break;
        }
        // we quit here, the result for last operation is calculated above
        if (c == EOF) {
            break;
        }
    }
    printf("%d\n", result);
   
    // As I see it was mentioned that "%d\n" is a string,
    // here's the simplest algorithm for printing digits in a number.
    // Extract one digit from the greatest position and continue up
    // to the last digit in a number.

    // Take negative numbers and throw them out the window.
    if (result < 0) {
         putchar('-');
         result = -result;
    }
    // Our program currently supports printing numbers up to 10000.
    int divisor = 10000;
    // 000100 should print as 100 - we need to remember we printed non-zero
    int was_not_zero = 0;
    while (divisor != 0) {
        // extract one digit at position from divisor
        int digit = result / divisor % 10;
        // if the digit is not zero, or
        // we already printed anything
        if (digit != 0 || was_not_zero) {
            // print the digit
            putchar(digit + '0');
            was_not_zero = 1;
        }
        // the next digit will be to the right
        divisor /= 10;
    }
    putchar('\n');
}