Equation Evaluator

Question

I am currently applying to many Software Engineer positions, and have been asked to complete several coding challenges. The most recent was an equation evaluator, written in C++, that was supposed to evaluate equations.

The criteria given were as follows:

• Each equation is specified on a separate line
• LHS is the left hand side of the equation and is always a variable name
• A variable name is composed of letters from the alphabet for which isalpha(c) is always true
• RHS is the right hand side of the equation and can be composed of variables, unsigned integers, and the + operator

The program needed to take a filename as input. That file contained a set of equations, such as:

• left = 5
• right = 6
• total = left + right

It needed to evaluate the set of equations and print the value of each variable, sorted in ascending order by variable name. If a variable didn't have a well-defined and unique solution, the program should output the exact contents of the file (no error or debug output).

After completing the challenge, I submitted my code and ended up being told I didn't make it to the next stage and that my code was... less than stellar. I'm only now getting out of college, and I'm not entirely sure where I can improve, so I'm hoping that's where you can help me. The code below is what I submitted, and I would appreciate any suggestions or advice on things I could have done better or other ways of tackling some of the problems. Only constructive criticism, please! I know the code is not the best, but it was my best at the time. I want to improve.

#include <fstream>
#include <iostream>
#include <string>
#include <unordered_map>
#include <sstream>
#include <vector>
#include <algorithm>

using namespace std;

bool isNum(char test)
{
   return (test == '0' || test == '1' || test == '2' || test == '3' || test == '4' || test == '5' || test == '6' || test == '7' || test == '8' || test == '9');
}

int main()
{
   string fileName;
   char fileChar;
   unordered_map<string, int> myVariables;
   unordered_map<std::string, int>::const_iterator result;
   string tempNumStr = "", tempVar = "", leftSide = "", line = "";
   int tempNum;
   bool leftSideComplete = false, additionTime = false, justHadEquals = false, errorExists = false;
   vector<string> mapKeys;

   cout << "For what file would you like to evaluate equations? Verify that this file is located in the directory from which you are running this program." << "\n";
   cin >> fileName;
   ifstream inFile;
   inFile.open(fileName);
   if (!inFile) {
      cerr << "Unable to open the file " << fileName << "\n";
      system("pause");
      return 0;
   }
   while (getline(inFile, line)) {
      if (errorExists)
          break;
      leftSide = "";
      tempVar = "";
      tempNumStr = "";
      tempNum = 0;
      leftSideComplete = false;
      additionTime = false;
      justHadEquals = false;
      for (int i = 0; i < line.length(); i++) {
          if (isNum(line[i])) {
              tempNumStr += line[i];
          }
          else if (isalpha(line[i])) {
              tempVar += line[i];
          }
          else if (line[i] == ' ') {
              if (leftSideComplete && (additionTime || justHadEquals)) {
                  if (tempVar.length() > 0) {
                      result = myVariables.find(tempVar);
                      if (result == myVariables.end()) {
                          errorExists = true;
                          tempVar = "";
                      }
                      else {
                          tempNum = myVariables.at(tempVar);
                          myVariables.at(leftSide) += tempNum;
                          tempNum = 0;
                          additionTime = false;
                          justHadEquals = false;
                      }
                  }
                  else if (tempNumStr.length() > 0) {
                      stringstream convert(tempNumStr);
                      convert >> tempNum;
                      myVariables.at(leftSide) += tempNum;
                      tempNum = 0;
                      tempNumStr = "";
                      additionTime = false;
                      justHadEquals = false;
                  }
              }
          }
          else if (line[i] == '=') {
              if (justHadEquals || leftSideComplete)
                  errorExists = true;
              result = myVariables.find(tempVar);
              if (result == myVariables.end()) {
                  myVariables.insert(make_pair(tempVar, 0));
              }
              leftSide = tempVar;
              tempVar = "";
              leftSideComplete = true;
              justHadEquals = true;
          }
          else if (line[i] == '+') {
              if ((additionTime && (tempVar.length() == 0 && tempNumStr.length() == 0)) || !leftSideComplete)
                  errorExists = true;
              additionTime = true;
              tempVar = "";
              tempNumStr = "";
              tempNum = 0;
          }
          if(i == line.length() - 1){
              if (leftSideComplete && (additionTime || justHadEquals)) {
                  if (tempVar.length() > 0) {
                      result = myVariables.find(tempVar);
                      if (result == myVariables.end()) {
                          errorExists = true;
                          tempVar = "";
                      }
                      else {
                          tempNum = myVariables.at(tempVar);
                          myVariables.at(leftSide) += tempNum;
                          tempNum = 0;
                          additionTime = false;
                          justHadEquals = false;
                          leftSideComplete = false;
                      }
                  }
                  else if (tempNumStr.length() > 0) {
                      stringstream convert(tempNumStr);
                      convert >> tempNum;
                      myVariables.at(leftSide) += tempNum;
                      tempNum = 0;
                      tempNumStr = "";
                      additionTime = false;
                      justHadEquals = false;
                      leftSideComplete = false;
                  }
              }
              break;
          }
      }
  }
  inFile.close();

  if (errorExists) {
      inFile.open(fileName);
      while (getline(inFile, line)) {
          cout << line << endl;
      }
  }
  else {
      for (auto& x : myVariables) {
          mapKeys.push_back(x.first);
          sort(mapKeys.begin(), mapKeys.end());
      }
      for (int i = 0; i < mapKeys.size(); i++) {
          std::cout << mapKeys[i] << " = " << myVariables.at(mapKeys[i]) << std::endl;
      }
  }
  system("pause");
  return 0;
  }

Answer 1

In real life, I would use knowledge of existing libraries to pull out an almost-finished solution. In particular, I think it is an example for Boost.Spirit, which is what I would use for a real problem of this nature.

I applaud you for checking here as well as whatever else you are doing to learn from your experience and improve your skills.

Library Knowledge

A meta-knowledge answer is something I have at the top of my hot-list for co-workers to read: Know your libraries. In a company with a large body of code, things get written multiple times and we need to make efforts to publish common or simple reusable code for all to find. In your case, per your comment, I suggest that as part of your basic knowledge in C++ programming you learn about

• the C++ Standard Library
• familiarity with Boost

Just reading through and knowing generally what’s there is enough; keep bookmarks in your browser to these references and then look up things you kind-of remember existing when you need details on how to use something.

Your Code Sample

For your specific code, I’m looking it over now …

---

Don’t use namespace std;

You can, however, in a CPP file (not H file) or inside a function put individual using std::string; etc.

---

bool isNum(char test)

Well,

• there is a standard library function that already does this;
• you should not put extra parens around the value in a return statement (always a point of style; but with new features it matters);
• The chars are guaranteed to be contiguous in the character set so even if there is funny encodings going on, you could just use return test>='0' && test<='9';.

---

Don’t declare variables en masse at the top of the block.

Declare variables when you are ready to initialize them, or use them for the first time. This is such a good idea that it was pulled back into C for C-99.

So I would go through

   string fileName;
   char fileChar;
   unordered_map<string, int> myVariables;
   unordered_map<std::string, int>::const_iterator result;
   string tempNumStr = "", tempVar = "", leftSide = "", line = "";
   int tempNum;
   bool leftSideComplete = false, additionTime = false, justHadEquals = false, errorExists = false;
   vector<string> mapKeys;

and float each one down to where it is first used.

Use constructors! Instead of

ifstream inFile;
inFile.open(fileName);

use

ifstream inFile {fileName};

and in this case, inFile is only used in this one place. You need to break up main into smaller functions, each doing one thing or being highly cohesive.

inFile open_users_file()
{
std::cout << "For what file would you like to evaluate equations? Verify that this file is located in the directory from which you are running this program\n";
string fileName;
cin >> fileName;
ifstream f { fileName };
return f;
}

 ⋮
auto inFile= open_users_file();

Note also the use-if-OK idea is directly supported by syntax, so actually it could be:

if (auto inFile= open_users_file())
{ // do the work 
}

but since this is essential and literally the first thing it does, I’d write it as a precondition. That is, short (one-line) tests at the very beginning of the function that return or throw. Then, no more deeply nested braces to do the main job: the body of code beyond that has passed the gauntlet and can be written as if it was the real beginning of the function.

---

Also among your big block of variables:

string tempNumStr = "", tempVar = "", leftSide = "", line = "";
bool leftSideComplete = false, additionTime = false, justHadEquals = false, errorExists = false;

It is bad practice in C++ to declare a bunch of stuff in one statement like that. Also, string has a default constructor, so initializing to an empty string is superfluous and is just extra code that has no effect.

And if you did really need to do that, an empty lex string literal is the wrong way to do it.

string s = "";  // bad
string s{};     // the proper way to indicate an empty string
string s;       // but not needed at all here

---

Everything inside

  for (int i = 0; i < line.length(); i++) {

is just a huge blob of nested blocks. I can’t even see the end of the loop, let alone the end of the function, in the editor window!

Write small functions, and break apart the logic into smaller pieces that do “one thing” or have highly cohesive use of variables.

Learn Top Down Design.

You should read, via the function names, what the code does on a high level, and thus understand the overall algorithm.

Since all your little blocks seem to use the same variables, you would make the parser an object, and have those be instance variables. Then breaking it up into smaller functions will work with private member functions which can all see the common state.

That also automatically pushes the initialization into the constructor or in-line default initialization of the data members; lifting them out of the main function as well.

---

I see multiple tests of the same form⋯ collapsing the bodies so I can read it:

  for (int i = 0; i < line.length(); i++) {
      if (isNum(line[i])) { ⋯ }
      else if (isalpha(line[i])) { ⋯ }
      else if (line[i] == ' ') { ⋯ }
      else if (line[i] == '=') { ⋯ }
      else if (line[i] == '+') { ⋯ }
  }

So, this should be the size of the function — each (possibly complex branch) can go in its own helper function to handle that case.

The repeated line[i] should be factored out. E.g.

const current_char = line[i];

but that is just a reflection of the use of an old-fashond for loop for the indexes. You don’t want the index i — you want the value at each index in the input, right?

for (auto current_char : line) {

---

tempVar = "";

To clear out a string efficiently, write tempVar.clear()

---

myVariables.insert(make_pair(tempVar, 0));

Good show on knowing about the std map types.

This specific line you might notice is a bit clunky… it is correct, but outdated. Now you can write it much more easily as

myVariables.insert({tempVar, 0});

But widening the view a little:

          result = myVariables.find(tempVar);
          if (result == myVariables.end()) {
              myVariables.insert(make_pair(tempVar, 0));
          }

First, notice that result is only used in these two places? So why is it defined sixty lines earlier and in scope for the about 120 lines?

But, you should know the behavior of insert. It does nothing if the item is already present. So, you don’t need to check first!

myVariables.insert({tempVar, 0});

is all you need. If the value is already present, it is not replaced with 0.

But, I wonder why you are making sure the var exists when it is first seen on the left. If you just wrote:

myVariables[leftSide] = result;

it would overwrite any old value and create a spot if necessary.

---

at the end:

  for (auto& x : myVariables) {

You should use const here.

  for (int i = 0; i < mapKeys.size(); i++) {

Why are you not using the range-for style here as well?

---

Again, showing you are not following Top Down Design and your functions are overgrown; after you close the file you go on to do something else entirely. Those steps should be different functions!!

Assuming you use the object idea I noted earlier, main would look something like this:

int main() 
{
    calc_t calc;
    process_inputs(calc);
    dump_variables(calc);
}

and

void process_inputs (calc_t& calc) {
    auto inFile= open_users_file();  // make it report and exit() if it can't.
    while (auto line = get_one_line(inFile)) {
        bool OK = calc.eval(line);
        if (!OK) {
            // report the error; it does not mess up the state
            // so you can keep going on the next line.
            return;  // if that's what you really wanted
        }
    }
}

At first I did not break process_inputs into a separate function, but then I did so because it gives a natural scope to the inFile. Note that I never explicitly close it — embrace RAII. It has no business outside of this block (e.g. while dumping the defined vars) so it should not exist there.

---

Recap

First, learn (or practice) Top Down Design and also don’t make meandering functions. That might be what gave the testers a bad impression.

Become familiar with standard and common library features.

Get a textbook written after 2011 and otherwise find good examples of “modern” (up to date) style and use of language features to learn from. Real code such as open source projects are full of legacy code and mixtures of old and new stuff, and is not so clear.

And keep it up! I applaud your effort to learn to improve your coding, and that’s the trump card. I’ve worked with someone who was stuck in 1987…

Answer 2

You are looking for advice on how to make this code better. What struck me when I looked at this code, and what surprised me that no one had mentioned, was

1. the lack of comments, and
2. the lack of testing infrastructure.

This is a non-trivial piece of code. Writing code is just the beginning. Code must then be maintained, maybe years after it was written, maybe by someone other than the author. Comments go a long way in informing the maintainer what the author was thinking.

The general structure of a program is input, processing, output. Obviously, for input in this program, you will need a recursive descent parser. The parser should be documented with the grammar you are using:

File := Lines
Lines := Line OR Line Lines
Line := Variable '=' Sum
Sum := Variable OR Number OR Variable '+' Sum OR Number '+' Sum

yada, yada, yada. This should all be in a comment before your parser.

Another comment before the parser should mention how the parser should treat corner cases: what if the file is empty, is it accepted or rejected? Does the last line need a newline to be accepted?

You should document the method for solving for your variables. This will probably be an iterative process where unknown values are computed from known values. According to the specification given, it seems like simultaneous equations would be possible (x=y+2, y=x+x+1). You should document in your variable solver that it will not handle simultaneous equations.

Finally, when developing any non-trivial program, one should develop the habit of writing tests. This will help a lot in verifying the program works as you expect. It will also give future maintainers confidence that their changes did not break the program. You don't have to use any fancy testing framework, but you can just write a test function which incorporates many tests, e.g.,

void TestFunction(){
    assert(ParseLine("x=y+5")!=null_ptr);
    assert(ParseLine("0=y")==null_ptr);
}

Answer 3

I looked at some of the detailed code.

              if (tempVar.length() > 0) {
                  result = myVariables.find(tempVar);
                  if (result == myVariables.end()) {
                      errorExists = true;
                      tempVar = "";
                  }
                  else {
                      tempNum = myVariables.at(tempVar);
                      myVariables.at(leftSide) += tempNum;
                      tempNum = 0;
                      additionTime = false;
                      justHadEquals = false;
                  }

The way to test to see if a string is empty is with empty(), not finding the length and then testing that.

The result of map::find is an iterator. You do more with them then see whether it was End! If you found it, you have it in your hand! There is no need to forget that and call at to look it up from scratch.

auto result= myVariables.find(tempVar);
if (result == myVariables.end()) {
    errorExists = true;
    tempVar.clear();
}
else {
    tempNum = *result;  // <<<< look here
    myVariables[leftSide] += tempNum;
         // note that [] auto-creates if it did not exist
    tempNum = 0;
    additionTime = false;
    justHadEquals = false;
}

---

The code is very hard to understand because the actions are not located where the even that caused them happen. You set flags like justHadEquals so the proper thing can be performed later, after reading a space for example. The blocks doing the actions are guarded by complex conditions of these flags.

If I had to write something like this, with the exercise being to write it “from scratch” rather than using library code, I would structure it as a standard recursive descent parser. The form would be known and thus basically understandable to others who read it later, and each action would be clearly associated with a small bit of grammar.

try {
   left = read the variable;
   read an equals
   right = read an summation expression
   vars[left] = right;
}
catch ⋯
    something was wrong with this line.

I don’t need error checking at every step; if something fails, throw an exception.

later…

I did write a working version. The above pseudocode ended up as:

try {
    skip_ws (input);
    auto LHS= read_identifier(input);
    if (!LHS)  raise_error(input, 4);
    read_required ('=', input);
    auto terms_result= read_terms(input);
    if (!terms_result)  raise_error (input, 5);
    if (!input.empty())  raise_error (input, 3);
    set_value (*LHS, terms_result);
    return *LHS;
}

The explicit error checking after each step is still dominating the code, detracting from the readability of the real work.