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

Post a Comment

Popular posts from this blog

Unicode output from an Arduino.

Image
I have been working hard on a second edition for my book called "Practical Arduino C". The new edition has an extra chapter focusing on adding an Internet capability to Arduino boards plus some additional data structures. Overall, the text has been polished and the index extended and tidied. I have also changed the way the book is being published and sold. This has halved the retail price while still ensuring fast delivery when ordered from Amazon ( Amazon UK link here ). One item that featured in the first edition has been dropped as with hindsight it became clear that it did not add to the reader's learning experience. It made sense therefore to move the section on Unicode output over the Arduino serial interface to a blog post here. Unicode Characters The Arduino C is a great tool for manipulating, displaying and communicating ASCII encoded characters, which is perfect if the language you want to use is based upon the Latin character set. Most recent programming
Read more

Arduino: How to scroll long text on OLED screen

 While exploring a new and tiny SSD 1306 OLED screen as a useful user interface I hit on the need to scroll some longish text across the screen. This did not seem to be a feature of the Adafruit library I was using to run the device. So I am introducing this working demo of my solution to the problem. The solution is to position the start point of the text in steps towards the left and beyond the left hand edge of the screen. The screen "clips" the text and displays all it can across the width of the screen. The demo includes some fixed text at the top of the screen and scrolls the long text below. #include <SPI.h> #include <Wire.h> #include <Adafruit_SSD1306.h> #define SCREEN_WIDTH 128 // OLED display width, in pixels #define SCREEN_HEIGHT 32 // OLED display height, in pixels #define OLED_RESET -1 // Reset pin # (or -1 if sharing Arduino reset pin) #define SCREEN_ADDRESS 0x3C ///< See datasheet for Address; 0x3D for 128x64, 0x3C for 128x32 Adafr
Read more

Arduino Regular Expressions

The first chapter of a wonderful book titled “Beautiful Code” (O’Reilly 2007) was written by Brian Kernighan who described an episode from when he and Rob Pyke were writing a book together called “The Practice of Programming”. They wanted to include a discussion on regular expressions but also wanted to include the code of an implementation. Existing code bases would have been a book length by themselves. Rob Pyke developed 30 lines of C code in less than two hours that implements a substantial part of the day to day usage of regular expressions. The code can be described as beautiful for its elegant efficiency. The final line of the chapter reads “I don’t know of another piece of code that does so much in so few lines while providing such a rich source of insight and further ideas”. The code handles the following constructs: Character Meaning c Matches any literal character (in this case ‘c’) . (full stop) Matches any single character
Read more