Note: The full source code for this project can be found here.

Have you ever wondered how a digital calculator takes your written text expression and actually computes a result? Not to mention handling math errors, semantic errors or dealing with inputs like floating point numbers. I have!

I was thinking about this problem while doing engineering work for my Master’s thesis. I found myself spending a lot of time googling the same physical units over and over again to check conversions and consistency of my calculations.

The frustration of this repetitive task helped me soon realize that units and their conversions never change. I should therefore not have to look them up all the time, but could store the information once and then design a simple tool to help automate the conversion and consistency checking!

I ended up writing my own small command line calculator that parses a semantic math expression and computes the output with appropriate error handling. As an added challenge, it can fully handle expressions with SI units. This small “side-quest” greatly accelerated my workflow and honestly, I still use it every day while programming, while it only took me about two days to complete.

Note: The type of expression parser I designed is a recursive descent style parser that utilizes precedence climbing. I am not a linguist and unfamiliar with concepts such as context-free grammars.

In the following article, I will present my attempt at making a no-dependency, customizable micro-calculator that can parse math expressions with physical units and improve your engineering / math workflow in the command line.

I think this is not only a fun coding challenge, but also a useful one, and could act as a jumping-off point for any other semantic math processing system you are interested in! For me, this project took away a lot of the mystery about how semantic math programs operate. If you are a DIY coder with an interest in linguistics and math, then this article is for you.

Note: While I realize that there are existing libraries to solve this kind of problem, I saw this as a fun coding challenge for which I already had a good solution concept. I decided to implement it anyway and I am very happy with the result.

Existing programs include insect, qalculate!, wcalc.

One key difference to my solution is that the program does not require “launching” – it simply runs directly in the console.

My First Command Line Calculator

The main objective of the command line calculator is to be capable of parsing a human-readable mathematical expression with units, return the value if it can be evaluated and inform the user about the position of an error if not.

In the following section, I will explain how this can be implemented in standard C++ in about 350 lines of code to yield an elegant, home-made command line calculator.

To help visualize the algorithm and process, we will observe the following example mathematical expression:

which should correctly evaluate to 1.35 m.

Note: I use square brackets because bash doesn’t like round ones. The tildes are equivalent to minus signs ~ the reason for writing them like this is to differentiate binary subtraction.

Syntax of a Math + Unit Expression

The mathematical expression to be evaluated is represented by an unambiguous string of characters. To evaluate the expression, we need to answer a number of key questions:

1. How are numbers with units represented and how can they be operated on?
2. What are the permissible characters in the expression and what do they represent?
3. How are characters grouped to yield structures / operations with a mathematical meaning?
4. How do we transform the expression based on its structure to yield a mathematical evaluation?

Number and Unit Representation

In order to allow various operations to act on number-unit pairs, we must define their structure and their operators. I will briefly present how to implement such number-unit pairs in the following section.

SI Units – A simple C++ Implementation

In the International System of Units, physical quantities are represented by a product between 7 individual base-units: Time, Length, Mass, Electric Current, Thermodynamic Temperature, Amount of Substance and Luminosity.

Every physical quantity can be constructed from a product of powers of these units. We call the full compound unit of a value its “dimension”. We create a struct which reflects this by storing a vector of powers associated with each base unit:

struct unit{              // Generic SI Derived-Unit

  vector<double> dim;     // Vector of base-unit powers

  unit(){};               // Constructors
  unit(dlist d){
    for(auto&e: d)
      dim.push_back(e);
  }

};

void fatal(string err){
  cout<<err<<endl;
  exit(0);
}

//Comparison Operators
bool operator==(const unit& l, const unit& r){
  if(l.dim.size() != r.dim.size())
    fatal("Dimension mismatch");
  for(int i = 0; i < l.dim.size(); i++)
    if(l.dim[i] != r.dim[i]) return false;
  return true;
}

bool operator!=(const unit& l, const unit& r){
  return !(l == r);
}

We can define each base unit as a constant of type unit:

const unit D   = unit({0, 0, 0, 0, 0, 0, 0}); //No Dimension
const unit s   = unit({1, 0, 0, 0, 0, 0, 0});
const unit m   = unit({0, 1, 0, 0, 0, 0, 0});
const unit kg  = unit({0, 0, 1, 0, 0, 0, 0});
const unit A   = unit({0, 0, 0, 1, 0, 0, 0});
const unit K   = unit({0, 0, 0, 0, 1, 0, 0});
const unit mol = unit({0, 0, 0, 0, 0, 1, 0});
const unit cd  = unit({0, 0, 0, 0, 0, 0, 1});

We define a set of overloaded operators for the unit struct. Different units can be multiplied / divided but not added / subtracted. Addition / subtraction of identical units yields the same unit. It is not possible to use a non-dimensionless unit as a power, but a unit can be taken to a power:

unit operator+(unit l, unit r){
  if(l == r) return l;
  fatal("Unit mismatch in operator +");
}

unit operator-(unit l, unit r){
  if(l == r) return l;
  fatal("Unit mismatch in operator -");
}

unit operator/(unit l, unit r){
  if(l.dim.size() != r.dim.size())
    fatal("Dimension mismatch");
  for(int i = 0; i < l.dim.size(); i++)
    l.dim[i] -= r.dim[i];
  return l;
}

unit operator*(unit l, unit r){
  if(l.dim.size() != r.dim.size()) 
    fatal("Dimension mismatch");
  for(int i = 0; i < l.dim.size(); i++)
    l.dim[i] += r.dim[i];
  return l;
}

unit operator%(unit l, unit r){
  if(l == r) return l;
  fatal("Unit mismatch in operator %");
}

template<typename T>
unit operator^(unit l, const T f){
  for(int i = 0; i < l.dim.size(); i++)
    l.dim[i] *= f;
  return l;
}

Number-Unit Value Pairs

Numbers associated with units are called “values” given by:

struct val{
  double n = 1.0;  // Magnitude (default = unity)
  unit u;          // Dimension

  val(){};  //Dimensionless Single Value
  val(double _n, unit _u):n{_n},u(_u){};
};

bool operator==(const val& l, const val& r){
  if(l.u != r.u) return false;
  if(l.n != r.n) return false;
  return true;
}

Similarly to units, we define a set of overloaded operators which act between values to return a new value:

val operator+(val l, const val& r){
  l.u = l.u + r.u;
  l.n = l.n + r.n;
  return l;
}

val operator-(val l, const val& r){
  l.u = l.u - r.u;
  l.n = l.n - r.n;
  return l;
}

val operator*(val l, const val& r){
  l.n = l.n * r.n;
  l.u = l.u * r.u;
  return l;
}

val operator/(val l, const val& r){
  l.n = l.n / r.n;
  l.u = l.u / r.u;
  return l;
}

val operator%(val l, const val& r){
  l.n -= (int)(l.n/r.n)*r.n;
  l.u = l.u%r.u;
  return l;
}

val operator^(val l, const val& r){
  if(r.u != D) fatal("Non-Dimensionless Exponent");
  l.n = pow(l.n, r.n);
  l.u = l.u ^ r.n;
  return l;
}

Derived Units as Combined Base Units

For a given string representing a unit or other physical quantity, we can extract number-unit pair using a look-up table. Values are constructed by multiplication of base units and stored in a map referenced by a symbol:

map <string, val> ud = {

  //Base Unit Scalings
  {"min", val(60, s)},
  {"km",  val(1E+3, m)},
  //...

  //Derived Units (Examples)
  {"J",   val(1, kg*(m^2)/(s^2))},    //Joule   (Energy)
  //...

  //Physical Constants
  {"R",   val(8.31446261815324, kg*(m^2)/(s^2)/K/mol)},
  //...

  //Mathematical Constants
  {"pi",  val(3.14159265359, D)},
  //...

};

//Extract Value
val getval(string s){
  auto search = ud.find(s);
  if(search != ud.end()){
    val m = ud[s];
    return m;
  }

  cout<<"Could not identify unit \""<<s<<"\""<<endl;
  exit(0);
}

Defining some quantities as being dimensionless, we can also include mathematical constants in the lookup table.

Note: Combined units are typically represented by some “key” or string, which can be ambiguous depending on who you ask. The lookup table is easily modifiable though!

Note: The “^” operator in the lookup table requires bracketing because of its low precedence order.

Expression Parsing

For this calculator I define five components of an expression: Numbers, Units, Operators, Brackets and Special.

Every character in a valid expression can be placed into one of these categories. The first step is therefore to determine which class each character belongs and to store it in a representation that includes this information.

Note: “Special” characters represent unary operators which transform a value. The following code examples are written in C++ and use the standard template library.

We define the “parse class” using a simple enumerator and define a “parse tuple” as a pairing between a character and its parse class. The string is parsed into a “parse vector”, which contains the ordered parse tuples.

enum pc {                         //Parse Class
  NUM, UNT, OPR, BRC, SPC
};

using pt = std::pair<pc,char>;    //Parse Tuple

using pv = std::vector<pt>;       //Parse Vector

We construct our parse vector by simply comparing each character to a set of characters contained in each class.

// Error Handling

void unrecognized(int i, char c){

  cout<<"Unrecognized character \""<<c<<"\" at position "<<i<<endl;

  exit(0);

}

// Construct a parse vector from a string!

pv parse(string e){

  pv parsevec;

  // Iterate over the string

  for(string::size_type i = 0; i < e.size(); i++){

    const char c = e[i]; // Get the next character

    // Permissible characters for each class

    string brackets = "[]";
    string operators = "+-*/^%";    //Binary Operators
    string special = "!~E";         //Unary Operators
    string numbers = "0123456789.";

    // Identify the class and add a parse tuple to the vector

    if(numbers.find(c) != string::npos)
      parsevec.push_back(pt(NUM, c));

    else if(isalpha(c))
      parsevec.push_back(pt(UNT, c));

    else if(operators.find(c) != string::npos)
      parsevec.push_back(pt(OPR, c));

    else if(brackets.find(c) != string::npos)
      parsevec.push_back(pt(BRC, c));

    else if(special.find(c) != string::npos)
      parsevec.push_back(pt(SPC, c));

    else unrecognized(i, c);

  }

  return parsevec;

}

The entire structure of our main program is to compress the expression, construct a parse vector and pass it to some evaluator which returns the final evaluated expression:

// MAIN FILE

using namespace std;

// ...

// Compress the command line input
string compress(int ac, char* as[]){
  string t;
  for(int i = 1; i < ac; i++)
    t += as[i]; // append to string
  return t;
}   // Note that spaces are automatically sliced out

// Compress, Parse, Evaluate
int main( int argc, char* args[] ) {

  string expression = compress(argc, args);
  pv parsevec = parse(expression);

  val n = eval(parsevec, 0);
  cout<<n<<endl;

  return 0;

}

For the example expression, this would look like this:

The easy part is now completed. The parse vector is constructed from the command line input and we can operate between numbers associated with values.

How do we evaluate the parse vector to yield a single value?

Expression Evaluation

Evaluating the parse vector represents the remaining challenge, and requires information about the structure of semantic mathematical expressions.

There are few key observations that we can make:

1. Numbers and units which are associated are always written contiguously in an expression
2. Unary operators can be applied directly to their associated number-unit pairs
3. Binary operators act between to number-unit pairs, yielding a new, single number-unit pair
4. Binary operators have a certain evaluation order
5. Brackets contain expressions which can themselves be evaluated to yield a number-unit pair
6. A balanced expression without unary operators or brackets always consists of N values and N-1 operators

After constructing number-unit pairs and applying unary operators, the parse-vector is therefore converted into a balanced sequence of values and operators.

Simultaneously, brackets are evaluated internally in a recursive fashion to collapse them to a single value.

This generally means that a parse vector can be evaluated using a recursive function which returns a number-unit pair.

Recursive Parse-Vector Evaluation Function

The recursive function eval is described by the process:

1. Iterate over the parse vector
   1. When we encounter a bracket, call eval on the internal expression to yield a value
   2. Extract number-unit pairs while applying unary operators and store in a vector
   3. Extract binary operators and store in a vector
2. Apply binary operators in the correct order using our balanced value and operator vectors

Ordered Value-Operator Sequence Construction

We start by defining the eval function, which takes an additional parameter n representing the starting point:

val eval(pv pvec, int n){

  if(pvec.empty()) return val(1.0, D);
  if(pvec[0].first == OPR) invalid(n);

  vector<val> vvec;   //Value Sequence Vector
  vector<char> ovec;  //Binary Operator Sequence Vector

  // ...

Note: An empty parse-vector returns a dimensionless unity value, and a parse-vector can not begin with an operator.

We iterate over the parse string tracking a start- and end-point for the current sequence being observed. When we encounter a bracket, we find the end-point of the bracket and call the evaluate function on the internal expression:

  // ...

  size_t i = 0, j = 0;  //Parse section start and end
  while(j < pvec.size()){

    //Bracketing
    if(pvec[j].second == '['){

      i = ++j;  //Start after bracket
      for(int nbrackets = 0; j < pvec.size(); j++){
        if(pvec[j].second == '[') //Open Bracket
          nbrackets++;
        else if(pvec[j].second == ']'){
          if(nbrackets == 0) //Successful close
            break;
          nbrackets--; //Decrement open brackets
        }
      }

      //Open Bracket at End
      if(j == pvec.size())
        invalid(n+i-1);

      //Recursive sub-vector evaluate
      pv newvec(pvec.begin()+i, pvec.begin()+j);
      vvec.push_back(eval(newvec, n+j));
    }

    // ...

This will lead to recursion until a parse-vector expression is found which does not contain any brackets and therefore consists of a balanced sequence of values and operators.

Operators can be added directly, while values are given by combination of numbers, units and unary operators. We can construct a value by finding the sequence of consecutive parse tuples representing it and constructing appropriately:

    // ...

    //Add Operator
    if(pvec[j].first == OPR)
      ovec.push_back(pvec[j].second);

    //Add Value
    if(pvec[j].first == NUM ||
       pvec[j].first == UNT ||
       pvec[j].first == SPC ){

      i = j; //Start at position j
      while(pvec[j].first != OPR &&
            pvec[j].first != BRC &&
            j < pvec.size()) j++; //increment

      //Construct the value and decrease j one time
      pv newvec(pvec.begin()+i, pvec.begin()+j);
      vvec.push_back(construct(newvec, n+j));
      j--;
    }

    j++; //Increment j

    //Out-of-Place closing bracket
    if(pvec[j].second == ']')
      invalid(n+j);

  }

  // Check if sequence is balanced
  if(ovec.size() + 1 != vvec.size())
    fatal("Operator count mismatch");

  // ...

We construct values from their sequence of parse tuples by identifying the numerical components, the units and the unary operators.

Number-Unit Pair Construction and Unary Operators

Since this calculator supports floating point representations, the value can consist of both a pre-exponential factor and a power. Additionally, both of these quantities can have a sign.

The sign is extracted as the first character, followed by a sequence of numbers. The value is extracted using stof:

val construct(pv pvec, int n){

  unit u  = D;       //Unit Initially Dimensionless
  double f = 1.0;    //Pre-Exponential Value
  double p = 1.0;    //Power
  double fsgn = 1.0; //Signs
  double psgn = 0.0;

  size_t i = 0;      //Current Index
  string s;
  bool fp = false;   //Floating Point Number?

  //First Character Negation
  if(pvec[i].second == '~'){
    fsgn = -1.0;
    i++;
  }

  //Get Numerical Elements
  while(i < pvec.size() && pvec[i].first == NUM){
    s.push_back(pvec[i].second);
    i++;
  }

  if(!s.empty()) f = stof(s);   //Extract Value
  s.clear();                    //Clear String

  //...

Note: The unary operator which represents a sign switch, e.g. -1, is represented here by a tilde ~ because it becomes easier to differentiate from the binary subtraction operator.

Next, we check for a floating point representation and repeat this to get the sign and magnitude of the power:

  //...

  //Test for Floating Point
  if(pvec[i].second == 'E'){
    i++;
    psgn = 1.0;

    if(pvec[i].second == '~'){
      psgn = -1.0;
      i++;
    }

    while(i < pvec.size() && pvec[i].first == NUM){ //Get Number
      s.push_back(pvec[i].second);
      i++;
    }
    if(!s.empty()) p = stof(s);
    else fatal("Missing exponent in floating point representation.");
    s.clear();
  }

  //Double floating point attempt
  if(pvec[i].second == 'E')
    invalid(n+i);

  //...

Finally, we extract the trailing unit as a string and get the associated value. We apply the final trailing unary operators and return the final form of our value:

  //...

  //Get Unit String
  while(i < pvec.size() && pvec[i].first == UNT){
    s.push_back(pvec[i].second);
    i++;
  }

  if(!s.empty()){
    val m = getval(s);
    f *= m.n; //Scale f by m.n
    u = m.u;  //Set the unit
  }

  if(pvec[i].second == '!'){
    f = fac(f);
    i++;
  }

  if(i != pvec.size())  //Trailing characters
    invalid(n+i);

  return val(fsgn*f*pow(10,psgn*p), u);
}

This process will collapse all combinations of unary operators numbers and units to value structs which can be operated on using binary operators:

Note: The position is passed to the construction function so the absolute position in the expression is known for error handling.

Ordered Value-Operator Sequence Compression

Finally, we have a balanced sequence of values and binary operators which we can compress using the correct order of operations. Two values associated with an interstitial operator can be compressed using a simple function:

val eval(val a, val b, char op){
  if(op == '+') a = a + b;
  else if(op == '-') a = a - b;
  else if(op == '*') a = a * b;
  else if(op == '/') a = a / b;
  else if(op == '^') a = a ^ b;
  else if(op == '%') a = a % b;
  else{
    std::cout<<"Operator "<<op<<" not recognized"<<std::endl;
    exit(0);
  }
  return a;
}

To compress the entire balanced sequence, we iterate over the parse vector once for every operator type in the correct order and perform the binary evaluations. Note that multiplication and division can occur simultaneously, as can addition and subtraction.

  //...

  function<void(string)> operate = [&](string op){
    for(size_t i = 0; i < ovec.size();){
      if(op.find(ovec[i]) != string::npos){
        vvec[i] = eval(vvec[i], vvec[i+1], ovec[i]);
        ovec.erase(ovec.begin()+i);
        vvec.erase(vvec.begin()+i+1, vvec.begin()+i+2);
      }
      else i++;
    }
  };

  operate("%");
  operate("^");
  operate("*/");
  operate("+-");

  return vvec[0];
}

Yielding the final result at the 0’th index, which we return.

Note: This recursive structure reflects the tree-like nature of the semantics of the mathematical expression.

Results and Conclusion

The structure described previously was wrapped in a simple command line tool I have called “dima” for “dimensional analysis”. The full source code can be found here.

This simple command line calculator will correctly evaluate the expressions you throw at it with units!

Units are correctly combined and expanded:

> dima J
1 kg m^2 s^-2
> dima J / N
1 m
> dima J/N + 2cm
1.02 m

while providing a convenient quick-reference for constants:

> dima R
8.31446 kg m^2 K^-1 mol^-1 s^-2

Depending on your application, the lookup table of unit expressions can be customized.

The recursive structure of the evaluation algorithm reflects the tree-like nature of the semantics of mathematical expressions.

A possible extension to this system would be to add a method for defining functions / transformations with names.

Another possibility would be to add some kind of evaluation buffer, which stores variables in a new dictionary using the assignment operator which can be accessed during other evaluations later on. Storing state like this would require writing to file or launching a process though.

This semantic math parser could be entirely re-imagined to yield alternative useful math programs!

For instance, it could try to reform expressions with variables algebraically to find a more elegant representation based on some scoring method (length, symmetry, repeating expressions, etc.)

Another possible variation would be a differentiation helper, which would exploit the algorithmic nature of derivatives.