Thread: Calculator with linked Lists

I have been give this code and i should create a calculator with linked lists.
The input always alternates between integer numbers and operators ('+', '-', '*', '/'), starting with a number. This is followed by any number of numbers and operators.
These entries should be saved in a linked list. Each node in the list can store both a char for the operator and an integer for a number. In addition, the node contains an enum type that indicates whether it is an operator or a number.
Each new node is inserted at the end of the list and the list should be output after each insertion.
The input is terminated with an '=' (and always follows a number). This operator is no longer added to the list.

thats not the entire task but some of it. i dont exactly know where to start.

insert

Code:

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


enum node_type {
    operator_type,
    number_type
};


struct node {
    char operator;          //Jeder Knoten enthält immer nur entweder einen
    int number;             //Operator oder eine Zahl, nicht beides
    enum node_type type;
    struct node* next;
};


struct node* createOperatorNode(char operator);
struct node* createNumberNode(int number);


struct node* findFirstPointOperator(struct node* head); // NULL, wenn nicht gefunden
struct node* findFirstDashOperator(struct node* head); // NULL, wenn nicht gefunden


struct node* findPreviousNode(struct node* head, struct node* node);
void removeAfterNode(struct node* node);


struct node* addLast(struct node* head, struct node* newNode);


void printList(struct node* head);


int main()
{
    
    return 0;
}

The technique I would use is quite an advanced one - a finite state machine.

It is where you keep track of where you are in the expression (i.e. expecting an operator or a number) and act accordingly character by character.

I quickly wrote this up as an example of how it could be implemented:

Code:

#include <stdio.h>
enum state {
   s_start_num,
   s_num,
   s_operator,
   s_error,
   s_end
};


enum state f_start_num(int c, int *v) {
   if(c == ' ') {
     return s_start_num;
   }


   *v = 0;
   // A zero can not have any following digits, only an operator
   if(c == '0') {
     printf("Value of %d\n",*v);
     return s_operator;
   }

   // A non-zero number
   if(c >= '1' && c <= '9') {
     *v = *v+c-'0';
     return s_num;
   }

   // Unexpected input
   printf("Expecting number\n");
   return s_error;
}


enum state f_num(int c, int *v) {
   // We are expecting digits
   if(c >= '0' && c <= '9') {
     *v = (*v * 10) + (c-'0');
     return s_num;
   }
   // If we get anything but a digit, "unget() the character and then look for an operator
   printf("Value of %d\n",*v);
   ungetc(c,stdin);
   return s_operator;
}


enum state f_operator(int c) {
   switch(c) {
     case ' ':
         return s_operator; // Ignoring spaces
     case '+':
     case '-':
     case '*':
     case '/':
         printf("Operator '%c'\n",c);
         return s_start_num;
     case '=':
         printf("Equals sign\n");
         return s_end;
   }
   printf("Expecting operator\n");
   return s_error;
}




int main(int arg, char *argv[])
{
   int state = s_start_num;
   int v;
   while(state != s_end) {
      int c = getchar();
      if(c == EOF)
        state = s_error;
      switch(state) {
         case s_start_num: state = f_start_num(c, &v);  break;
         case s_num:       state = f_num(c, &v);        break;
         case s_operator:  state = f_operator(c);       break;
         default:
            printf("Unknown state\n");
            return 0;
      }
   }
}

Here's the some example output, breaking "13+33+0=" into it's parts.

Code:

$ echo "13+33+0=" | ./main
Value of 13
Operator '+'
Value of 33
Operator '+'
Value of 0
Equals sign

The super tricky bit is the ungetc() call, where it knows it has reached the end of the number but is not ready to decide what to do with the operator.

You will of cause need to do more than just print the parts of the expression.

Ah well, I'll show myself out then...