Need help with string calculation

Hello everyone!

I have a bit of a tricky problem to solve. I have a string with some data in it that I want to calculate, but wrapping my head around the required code is proving understandably difficult. The following is my current code:

String calculation = "\"int myResult = 7+6/5+2*(4-3)+1\"";

void setup() {
  Serial.begin(115200);

  Serial.println("STARTING COMMAND: " + calculation);
  Serial.println();
  Serial.println("OUTPUT WE WANT FROM DEFINING BRACKETS FUNCTION: (((7+(6/5))+(2*(4-3)))+1)");
  Serial.println("OUTPUT WE  GET FROM DEFINING BRACKETS FUNCTION: " + calculate(calculation));
  Serial.println("CALCULATION COMPLETE");
}

void loop() { }

String calculate(String string) {
  String result = removeStartingVariableDefinition(string);
  result = addDefiningBracketsAroundCalculation(result);
  return result;
}

String removeStartingVariableDefinition(String string) {
  string.replace(" ",""); string.replace("\n",""); string.replace(";",""); //Remove invalid characters
  return string.substring(string.indexOf('=') + 1,string.length()); //return everything after the equals sign
}

String addDefiningBracketsAroundCalculation(String in) {
  //Iterate over every symbol and ask if it's a number or operation
  for(int i = 0; i < in.length(); i++) {
    
  }
}

First, I remove anything that is not directly part of the calculation (Like line ends, spaces, variables declaration, etc). Then, I wanna put brackets around each individual part of it. For example, I wanna put turn this:

7+6/5+2*(4-3)+1

Into this:

(((7+(6/5))+(2*(4-3)))+1)

That way, the next part of code can individually interpret the code and calculate each individual section. However, wrapping the brackets around the code using BIMDAS and also avoiding segmenting bracketed sections of the calculation is proving difficult. As you can see, addDefiningBracketsAroundCalculation() is currently empty (save for the iteration over all characters in the calculation).

I am aware that alot of people will question why I need this in the first place, and the answer to that is "I am building some software designed to use an SD card as the arduino's variable memory." I am aware that there are ways to change the bootloader to do this already, but I wanna do it just using a standard, unmodified Mega 2560 (Arduino Uno if I can) with the default bootloader. I have most of the other code madeup already, but I am developing this function in it's own file for now to test if I can get it to work. I am also aware that this task is better suited for a RPi, but I still want to use the arduino despite this.

The reason I wanna do this is because with using files as variables, you can dynamically define variables, check if a variable exists, and have lists like python and C# do with variable array lengths that you can append to later if wanted. I'm effectively rewriting the whole system from scratch, simply because I can.

But back to the current issue at hand, I was wondering if someone could help me with getting the brackets in their correct positions for the next section of code to work? I am fully expecting it to be a function that iterates over itself multiple times until it's complete. Any help is appreciated, and if you want to know more about the code I'm writing (ASDOS, Arduino SD Operating System) I'd be happy to elaborate.

Thanking you in advance,
Andrey

So, it sounds like you already know this is insane, so that's good.

It sounds like you want to essentially write a scripting language. I think you're going through this at the wrong angle. It might be a good idea to do some reading on parsers/parsing and grammars in general.

The simplest type of parser that I can think of is a recursive descent parser. Downsides are obviously the heavy use of the stack, which might not be the best approach on a memory restricted device, but I find it the easiest to understand. Recursive descent parser - Wikipedia

But you're gonna need some background in grammars in order to understand any of this.

If you're just trying to do really simple calculations like you're doing right now, your approach MIGHT work - but if you want to add more features, symbols to the grammar, I think it might get tricky and convoluted.

Ok, first i do have to tell you that using the 'String' class here is really not such a good plan. You should be using c-strings (char-array) instead. With the program likely to grow quite a bit and run for quite a while, the memory fragmentation may cause you issues later on, and by that time t is going to be a lot of work to change.

Also i don't think you need to put braces around everything. What you should do is, in this order :
1- Check for number of closing and opening braces.
2- Look for deepest nested brace pair.
3- Do calculation within that in order * / + -
3- Do last 2 steps until calculation is completed.

This is all still going from the idea that on the other side of the '=' there will only be one argument.
Anyway, the function that you should write first is one that deals with step '2' in a way that it solves
"2 + 3 * 4 / 6 ="
I would do that in this way :

1- Search for highest priority mathematical procedure
2- Extract digits into numbers on the left side and on the right side of the operator
3- perform calculation.
4- Replace calculation with result
5- Repeat until all operators are gone.

Maybe this article on codeproject could be of interest to you: Simple Guide to Mathematical Expression Parsing.

Thankyou to everyone who helped me wrap my head around this. Now I am on the home stretch with the following code:

String calculation = "int myResult = 7+6/5+2*(4-3)+2*(4+8*(2-3)+7*(2+4)) + (2/2)";

void setup() {
  Serial.begin(115200);
  Serial.println(calculate(calculation));
  Serial.println("CALCULATION COMPLETE");
}

void loop() { }

String calculate(String string) {
  //Here we wanna essentially get rid of anything that isn't the calculation itself
  string.replace(" ",""); string.replace("\n",""); string.replace(";",""); //Remove invalid characters
  string = string.substring(string.indexOf('=') + 1,string.length()); //return everything after the equals sign
  
  string = calculateBrackets(string);
  return finalCalculation(string);
}

String calculateBrackets(String in) {
  //This will trigger to calculate any brackets already existing to make the compiling process much faster and simpler
  //"7+6/5+2*(4-3)+2*(4+8*(2-3)+7*(2+4))" should become "7+6/5+2*1+2*38"
  //Should also be able to handle "2*(4+8*(2-3)+7*())"
  
  while (in.indexOf('(') > -1) {
    //We wanna find the deepest recursion of brackets until there are none left
    int index = 0;
    int deepestIndex = 0;
    int deepestIndexBracketStart = 0;
    for (int i = 0; i < in.length(); i++) {
      if (in[i] == '(') {
        index++;
        if ((i > deepestIndexBracketStart) and (index > deepestIndex)) { deepestIndexBracketStart = i; deepestIndex = index; }
      } else if (in[i] == ')') { index--; }
    }
    
    int deepestIndexBracketEnd = 0;
    int i = deepestIndexBracketStart;
    while (true) { if (in[i] == ')') { deepestIndexBracketEnd = i; break; } i++; }
    
    //We have found the deepest recursion. Now work backwards to calculate each bracket one by one
    in = in.substring(0,deepestIndexBracketStart) + finalCalculation(in.substring(deepestIndexBracketStart + 1,deepestIndexBracketEnd)) + in.substring(deepestIndexBracketEnd + 1,in.length());
  }
}

String finalCalculation(String in) {
  //Here is where we finally do the calculation. All brackets have been taken care of, all invalid characters have been removed. Now all we need is to finally finish it up
  Serial.println(in);
  return "0";
}

This code successfully pulls out and calculates each individual bracket from most nested to least nested until all that's left is the final calculation to do. The only thing left to build is the finalCalculation() function that takes in a calculation and completes it (Haven't decided how, but it will probably calculate it in 2 steps. First being multiplication and division from left to right, the second being addition and subtraction left to right with what's left).

Will keep you all updated to my progress

seems like a recursive algorithm would work

process a string, a basic expression as a numeric followed by an operator followed by a number and replacing that substring with the numeric result of the operation and resulting in a new string with one less operation.

then process that string until all that's left is a single numeric symbol

1. This is the parse tree (Fig-1) of the expression you want to evaluate.
parse.png
Figure-1:

2. This is the sketch that saves your expression as string in the array named myData[].

char calculation[] = "\"int myResult = 7+6/5+2*(4-3)+1\"";
char myData[20] = "";
int i = 0, j = 0;
char x, y;

void setup()
{
  Serial.begin(9600);
  do
  {
    x = calculation[i];
    i++;
  }
  while (x != '=');
  do
  {
    y = calculation[i];
    myData[j] = y;
    i++;
    j++;
  }
  while (y != 0x22);
  myData[j - 1] = '\0';
  Serial.print(myData); //7+6/5+2*(4-3)+1
}

void loop() { }

3. Write a parser to evaluate Fig-1 (ref: Post#3). You may also consult this book:
Compiler Design in C - Allen Holub

parse.png

Write a parser to evaluate Fig-1 (ref: Post#3).

i think the trick is to write code that can parse any tree

And of course this only really works of the result of a division is an integer, actually you may need to replace the result of the calculation to a reference to a variable instead of just the result if you want to make it float computation friendly.

Ok, so I've got something that is SO CLOSE to working. It technically does work, but I'm having a bit of a strange issue. Not sure to post it here since it's the same code, or in a seperate thread as it's a different issue, but here's the current code:

String calculation = "int myResult = 7+6/5+2*(4-3)+2*(4+8*(2-3)+7*(2+4)) + (2/2)";

void setup() {
  Serial.begin(115200);
  
  finalCalculation("7+8.415/9.815*4.17-2+9");
}

void loop() { }

String calculate(String string) {
  //Here we wanna essentially get rid of anything that isn't the calculation itself
  string.replace(" ",""); string.replace("\n",""); string.replace(";",""); //Remove invalid characters
  string = string.substring(string.indexOf('=') + 1,string.length()); //return everything after the equals sign
 
  string = calculateBrackets(string);
  return finalCalculation(string);
}

String calculateBrackets(String in) {
  //This will trigger to calculate any brackets already existing to make the compiling process much faster and simpler
  //"7+6/5+2*(4-3)+2*(4+8*(2-3)+7*(2+4))" should become "7+6/5+2*1+2*38"
  //Should also be able to handle "2*(4+8*(2-3)+7*())"
 
  while (in.indexOf('(') > -1) {
    //We wanna find the deepest recursion of brackets until there are none left
    int index = 0;
    int deepestIndex = 0;
    int deepestIndexBracketStart = 0;
    for (int i = 0; i < in.length(); i++) {
      if (in[i] == '(') {
        index++;
        if ((i > deepestIndexBracketStart) and (index > deepestIndex)) { deepestIndexBracketStart = i; deepestIndex = index; }
      } else if (in[i] == ')') { index--; }
    }
   
    int deepestIndexBracketEnd = 0;
    int i = deepestIndexBracketStart;
    while (true) { if (in[i] == ')') { deepestIndexBracketEnd = i; break; } i++; }
   
    //We have found the deepest recursion. Now work backwards to calculate each bracket one by one
    in = in.substring(0,deepestIndexBracketStart) + finalCalculation(in.substring(deepestIndexBracketStart + 1,deepestIndexBracketEnd)) + in.substring(deepestIndexBracketEnd + 1,in.length());
  }
}

int count_chars(String string, char ch) { int count = 0; for(int i = 0; i < string.length(); i++) { if (string[i] == ch) { count++; } } return count; }

String getNextNumber(String in, int symbolIndex) {
  bool running = true;
  String result = "";
  for (int i = symbolIndex + 1; running; i++) {
    if ((in[i] != '.') and (!isDigit(in[i]))) {
      running = false;
    } else { result += in[i]; }
    
    if (i == in.length()) { running = false; }
  }
  
  return result;
}

String getPrevNumber(String in, int symbolIndex) {
  bool running = true;
  String result = "";
  for (int i = symbolIndex - 1; running; i--) {
    if ((in[i] != '.') and (!isDigit(in[i]))) {
      running = false;
    } else { result = in[i] + result; }
    
    if (i == 0) { running = false; }
  }
  
  return result;
}

String finalCalculation(String in) {
  // Here is where we finally do the calculation. All brackets have been taken care of, all invalid characters have been removed. Now all we need is to finally finish it up
  // We should get on something like "7+8/9*4-2+9" and be able to equate it in two steps using getPreviousNumber() to help us
  // Step 1, multiplication and division: "7+8/9*4-2+9" becomes: "7+3.55555555555556-2+9"
  // Step 2, addition and subtraction: "7+3.55555555555556-2+9" becomes "17.55555555555556" plus or minus some error due to floating point precision
  
  //Step 1
  for (int i = 0; i < in.length(); i++) {
    if (in[i] == '*') {
      String a = getPrevNumber(in,i); String b = getNextNumber(in,i);
      int index = in.indexOf(a+"*"+b);
      
      in = in.substring(0,index) + String(a.toFloat()*b.toFloat()) + in.substring(index+a.length()+b.length()+1,in.length());
      i = index;
    } else if (in[i] == '/') {
      String a = getPrevNumber(in,i); String b = getNextNumber(in,i);
      int index = in.indexOf(a+"/"+b);
      
      in = in.substring(0,index) + String(a.toFloat()/b.toFloat()) + in.substring(index+a.length()+b.length()+1,in.length());
      i = index;
    }
  }
  
  for (int i = 0; i < in.length(); i++) {
    if (in[i] == '+') {
      String a = getPrevNumber(in,i); String b = getNextNumber(in,i);
      int index = in.indexOf(a+"+"+b);
      
      in = in.substring(0,index) + String(a.toFloat()+b.toFloat()) + in.substring(index+a.length()+b.length()+1,in.length());
      i = index;
    } else if (in[i] == '-') {
      String a = getPrevNumber(in,i); String b = getNextNumber(in,i);
      int index = in.indexOf(a+"-"+b);
      
      in = in.substring(0,index) + String(a.toFloat()-b.toFloat()) + in.substring(index+a.length()+b.length()+1,in.length());
      i = index;
    }
  }
  
  return in;
}

I'm aware that the number of strings I throw all over the place is a memory leak nightmare, but I just wanna get something working first before going backwards and altering it all to be effecient.

The new issue I'm having seems like a much simpler one. When turning a float into a string, it only gives 2 decimal places of accuracy. 3.1415926 when turned from a float to a string becomes "3.14". When multiplying it by 100 I see "314.16". So it seems to be correctly transforming it from one variable type to another, but it seems to want to ABSOLUTELY FORCE 2 decimal places max, which will throw out calculations quite a bit down the road. Any clues to this much simpler problem?

It's here: String(a.toFloat()-b.toFloat())

NOTE: Down the road, I'll be changing all of this code to work with char arrays rather than strings for performance and memory reasons, but just for now I wanna see if I can solve this issue

Any help is much appreciated.

Thanking you again in advance,
Andrey

you might be interested in the following Awk scipt which uses recursive functions It doesn't calculate the value, which is another challenge, but it parses the string while recognizing the digits and operators.

awk '
BEGIN  {
    dbg  = 1
    EOL  = -1
    qDig [0] = qOp [0] = 0
}

# ------------------------------------------------
function error (msg)  {
    printf "Error: %s\n", msg
    printf "%s\n", $1
    for (i = 1; i < idx-1; i++)
        printf " "
    printf "^\n"
    exit
}

# ------------------------------------------------
function getC (c)  {
    if (length($1) < idx)  {
        printf "getC: EOL\n"
        return EOL
    }

    c = substr($1, idx++, 1)
    if (dbg) printf " getC: %s\n", c
    return c
}

function ungetC ()  {
    if (dbg) printf " ungetC:\n"
    idx--
}

# ----------------------------------------------------------
function pushQ (q, s, i)  {
    i     = ++q [0]
    q [i] = s
}

function popQ (q, s, res)  {
    res   = q [q [0]--]

    if (0 > q [0])
        error("queue underflow")
}

function sizeQ (q)  {
    return q [0]
}

# ----------------------------------------------------------
function isDigit (c, res)  {
    if (dbg) printf "    isDigit: %s\n", c

    res = match(c, "[0-9]")
    if (res)  {
        printf "%20s %c\n", "isDigit:", c
        val0 = int(c)

 #      if (sizeQ(qOp))  {
 #          val0 = popQ(qDig)
 #          op   = popQ(qOp)

 #          if ("+" == op)
 #              val0 += val1
 #          else if ("-" == op)
 #              val0 -= val1
 #          else if ("*" == op)
 #              val0 *= val1
 #          else if ("/" == op)
 #              val0 /= val1
 #          else
 #              error(sprintf("invalid op %s", op))
 #      }
 #      else
 #          val0 = val1

        pushQ(qDig, val0)
        printf "%20s %d\n", "Value", val0
    }
    return res
}

# ------------------------------------------------
function isOp (c, res)  {
    if (dbg) printf "    isOp: %s\n", c

    res = match(c, "[+*/]") || "-" == c
    if (res)  {
        pushQ(qOp, c)
        printf "%20s %c\n", "isOp:", c
    }
    return res
}

# ----------------------------------------------------------
function getExprP ()  {
    if (dbg) printf "  getExprP:\n"

    val = getExpr(s)

    c = getC()
    if (isOp(c))  {
        getExpr(c)
        c = getC()
    }

    if (")" != c)
        error(sprintf("expected ), got %s", c))

    if (dbg) printf "   :getExprP\n"
}

# ------------------------------------------------
function getExpr (s)  {
    if (dbg) printf "  getExpr:\n"

    c = getC()

    if (EOL == c)  {
        printf "%20s\n", EOL
        next
    }
    else if (")" == c)  {
        ungetC()
    }
    else if ("(" == c)
        getExprP()
    else if (isDigit(c))  {
        printf "   getExpr: digit %c\n", c
        c = getC()
        if (isOp(c))
            getExpr()
        else
            ungetC()
    }
    else
        error("unexpected char")

    if (dbg) printf "   :getExpr\n"
}

# ------------------------------------------------
NF {
    print s
    idx = 1
    val = 0
    op  = ""
    print $1
    getExpr($1)
    printf " val %d\n", val
}' << **END**
(((7+(6/5))+(2*(4-3)))+1)
**END**

i believe two stacks are needed, one for values an one for operators. when an expression is recognized, the operator is applies to the top 2 value on the value stack and the result pushed back on the stack. Presumably the stack has one values at the end, the result of the computation

Ok, managed to solve the issue! Apparently it's a super simple one.

String(some_float_value)

^ This will always return 2 decimal places. HOWEVER, if you make the tiniest change to:

String(some_float_value,numberOfDecimalPlaces)

then it solves the problem.

To anyone down the line wanting the ability to turn a string into a calculation like this, here is the absolute final code (With exception to when I alter everything to work with char arrays instead of strings):

http://www.mediafire.com/file/b9320ax1csw27oj/Calculation_Parser.ino/file

EDIT: Just fixed up a bug where negative numbers would kill the script.

EDIT 2: Added the ability to calculate trigonometric functions (This made the file too big to no-longer fit in this forum post)

1 Like