A Uno stack based calculator

I had a lot of fun writing a simple BASIC interpreter to run on an Arduino but I could only get my version to run on an Arduino Due. Storing and manipulating lines of BASIC code required lots of available SRAM. I therefore decided to experiment to see if I could get something of worth to run on a Uno or Nano that applied similar programming techniques.

I decided upon a program that can evaluate floating point numeric expressions. This had the utility of showing how my integer BASIC could be simply adapted to using floating point arithmetic as well as demonstrating the process of parsing and tokenising an expression while using a stack to evaluate a result.

This program works just fine with the standard Serial Monitor window with expressions being entered to the “Send” text box although you should check that the “Line Ending” drop down list at the bottom right of the window is set for one of the options that includes a carriage return and/or newline.

Code Commentary

The code can be downloaded from the web site supporting my Arduino C book.

The loop() function
void loop() {
   if(Serial.available()) {
    char c = Serial.read();
    switch(c) {
      case 10:
      case 13:
        processBuffer();
        break;
      default:
      if(buffPos <= BUFFSIZE-1) {
        buff[buffPos++] = c;
      }
    }
  }
}

Stores incoming characters from the serial port until a carriage return or newline char triggers the processBuffer() function to start the tokenising and evaluation process.

The processBuffer() function

This function calls the getNextToken function repeatedly until the input buffer end is reached. Two pointers are used to track progress through the buffer with pptr pointing to the start of any numeric values found. The other pointer (nptr) points to the end of any value or operator found ready to start the search for the next one. Values and operators are added to the statItems[] array as they are identified.

Once the input buffer has been tokenised the validateExp() function is called to validate the expression with error codes being returned when necessary. If the expression is deemed valid then evalExp() is called to return a float result ready to be displayed using the Serial Monitor. If an expression is invalid then an error message is displayed.

The validateExp() function

This function simply ensures that values and operators turn up in the right order and that parentheses are balanced.

The evalExp() function

float evalExp() {
  Stack<int> opStack;
  Stack<float> valStack; // create a value stack and operator stack
  int op;
  float r, l;
  for(int i = 0; i < statItemCount; i++) {
    if(statItems[i].sType == NUM) {
      valStack.push(statItems[i].fVal);
      continue;
    }
    if(statItems[i].sType == OPERATOR) {
      if(statItems[i].iVal == LEFTPAREN) {
        opStack.push(LEFTPAREN);
        continue;
      }
      if(statItems[i].iVal == RIGHTPAREN) {
        while(opStack.peek() != LEFTPAREN) {
          op = opStack.pop();
          r = valStack.pop();
          l = valStack.pop(); // get the order right before left
          valStack.push(doArith(op, l, r));
        }
        opStack.pop(); //remove the left paren
        continue;
      }
      // another operator
      while(opStack.stackCount() > 0) {
        if(opStack.peek() >= statItems[i].iVal){
          // while any existing operators have higher precedence
          op = opStack.pop();
          r = valStack.pop();
          l = valStack.pop(); // get the order right before left
          valStack.push(doArith(op, l, r));
        } else {
          break;
        }
      }
      opStack.push(statItems[i].iVal); // push the new op
    }
  }
  // work back through the stack
  while(opStack.stackCount() > 0) {
      op = opStack.pop();
      r = valStack.pop();
      l = valStack.pop();
      valStack.push(doArith(op, l, r));
  }
  return valStack.pop();
}

This function creates two stacks class instances. One to store floating point values and the other to store operators. One stack could be used but two stacks have been used for code clarity. The function reads the list of tokens from left to right pushing values and operators onto the relevant stacks. If a right parenthesis is identified then operators currently on the stack are applied to values on the stack working backwards (LiFo) until a left parenthesis is identified. This ensures that sub-expressions within parentheses are evaluated first. Before adding a new operator, the relevant stack is checked to see if the previous operator has a higher precedence than the new operator and, if this is so, the higher precedence operator is applied to the last two values on the numeric stack.

Once all of the operators and values have been added to their stacks then the evaluation proceeds back through the stacks. The floating point calculations are performed by the doArith() function that takes the left and right hand values together with the operator as arguments. The division operation checks for divide by zero and sets the error code if that that occurs.

The doArith() function

float doArith(int op, float lVal, float rVal) {
  switch(op) {
    case MULTIPLY:
      return lVal * rVal;
    case DIVIDE:
      if(rVal == 0) {
          errCode = 21;
          return 0;
      }
      return lVal / rVal;
    case MINUS:
      return lVal - rVal;
    case PLUS:
      return lVal + rVal;
    default:
      return 0;
  }
}

Pretty much what you might expect

Grab a copy of the complete code from the book web site.
You could also get a copy of my book from Amazon.

Comments

Popular posts from this blog

BASIC for Arduinos

Caenorhabditis Elegans (C. Elegans) Nematode Project

Arduino 2048