C++ arithmetic calculator built without resorting to tree structure as conventionally done, but by parsing input string and then std::stoi

Question

Lately I came across a book exercise that asked to implement a calculator by resorting only to std::string manipulation.

I avoided C++ streams as well, as they are yet to be treated in the book, and came up with the algorithm below.

The program can handle parentheses (). Operations are resolved by order of precedence, so first anything inside parentheses, then multiplication, division and modulo, then addition / subtraction.

The input is read directly from the command prompt, as an additional argv argument typed between quotes "", when invoking the program.

Had to resort to the boost::string Algorithms library, especially to read the input string and elsewhere the boost::algorithm::is_any_of() classification predicate.

Right now, the program handles integers. The algorithm is elegant (so I find it), partly because implementing compiler polymorphism would consist just in a matter of adapting the doArithmetic() function into accepting a std::variant<int, double>.

However, I found actual implementation to be tricky, because of negative numbers that can result from intermediate operations, for instance -1 - 1 - 2 which - parsing subtraction from-end-to-start like I decided to - has to be transformed into -1 + (-1 - 2) in order to be computed correctly. This choice stems from the desire to treat together the last number standing, with its unary +- sign operator (in the example above, -4 would be the last term) as the returned output.

Also, if I were to parse + or - operations left-to-right and the leftmost number were to be negative, I'd have to find a way to code into the program the difference between a unary -, and the subtract operator a - b between two numbers.

After a certain amount of testing, the above consideration led to bloating the code with a number of parsing lines handling edge cases.

#include <cstdio>
#include <exception>
#include <string>
#include <boost/algorithm/string/predicate.hpp>
#include <boost/algorithm/string/classification.hpp>
#include <boost/algorithm/string/case_conv.hpp>

std::string argvParser(const int argc, char** argv) {
  std::string output;

  // parse input word by word ...
  for (auto word_index=1; word_index!=argc; ++word_index)
    // ... if current word is with no punctuation, add it to the string_view at once
    if (boost::algorithm::all(*(argv+word_index), boost::algorithm::is_alnum() || boost::algorithm::is_any_of("+-*/%()")))
      output.append(*(argv+word_index));
    // ... if punctuation present, add alphanum chars one by one
    else {
      const char* word{*(argv+word_index)};
      for (auto letter_index=0; letter_index!=strlen(word); ++letter_index)
        if (boost::algorithm::is_alnum()(*(word+letter_index)) || boost::algorithm::is_any_of("+-*/%()")(*(word+letter_index)))
          output.push_back(*(word+letter_index));
    }

  boost::algorithm::to_upper(output);

  return output;
}


int doArithmetic(const std::string& input, const int previous_symbol, const int this_symbol, const int next_symbol){
  const char operation{input[this_symbol]};  // *, /, %, +, or - symbol

  std::string factor1_str{};
  if (previous_symbol==0 && input[previous_symbol]=='-')  // accounts for the - if 1st factor is negative number
    factor1_str.assign(std::string{input.substr(previous_symbol, this_symbol-previous_symbol)});
  else
    factor1_str.assign(std::string{input.substr(previous_symbol+1, this_symbol-previous_symbol-1)});
  std::string factor2_str{input.substr(this_symbol+1, next_symbol-this_symbol-1)};

  int factor1 = std::stoi(factor1_str);
  int factor2 = std::stoi(factor2_str);
  int result{};

  switch (operation) {
  case ('*'):
    result = factor1 * factor2;
    break;
  case ('/'):
    result = factor1 / factor2;
    break;
  case ('%'):
    result = factor1 % factor2;
    break;
  case ('+'):
    result = factor1 + factor2;
    break;
  case ('-'):
    result = factor1 - factor2;
    break;
  default:
    throw std::logic_error("Failed to read arithmetic symbol (*, /, +, - or %)\n");
    break;
  }

  return result;
}


void parseMultDivMod(std::string& input) {
  int idx_product_symbol = input.find_first_of("*/%");  // symbol for current operation

  // perform all */% operations present within the input
  while (idx_product_symbol != std::string::npos) {
    // locate the two factors left and right the */% operation symbol
    int previous_symbol = input.find_last_of("+-*/%", idx_product_symbol-1); // find symbol before current
    if (input[previous_symbol]=='-' && boost::algorithm::is_any_of("+-*/%")(input[previous_symbol-1])) // include - if 1st factor is negative
      previous_symbol--;
    if (previous_symbol == std::string::npos) // if present operation first one in string -> tag no previous symbol
      previous_symbol = -1;

    int next_symbol = input.find_first_of("+-*/%", idx_product_symbol+1); // find symbol after current
    if (input[idx_product_symbol+1]=='-')
      next_symbol = input.find_first_of("+-*/%", idx_product_symbol+2);
    if (next_symbol == std::string::npos)
      next_symbol = input.size();

    // perform actual */% operation
    int res{doArithmetic(input, previous_symbol, idx_product_symbol, next_symbol)};

    // recast */% operation result from number to std::string
    std::string prod_str = std::to_string(res);
    std::string plug_result{};
    // edge cases
    if (previous_symbol > 0)
      plug_result = std::move(std::string{input.begin(), input.begin()+previous_symbol+1});
      
    plug_result.append(prod_str);
    plug_result = plug_result + input.substr(next_symbol, input.size()-next_symbol);
    input.assign(plug_result);  // using auxiliary std::string above + assign() method, helps preserve iterators
    
    idx_product_symbol = input.find_first_of("*/%"); // update next iteration with next symbol in string
  } 
}


void parseAddSubtract(std::string& input) {
 // same logic as parseMultiDivMod above, but for +- operations
  int idx_add_subtract_symbol = input.find_last_of("+-"); // start searching from last symbol

  while (idx_add_subtract_symbol != std::string::npos) {
    int previous_symbol = input.find_last_of("+-", idx_add_subtract_symbol-1);
    // edge cases
    if (input[previous_symbol]=='-' && previous_symbol!=0) { // in case 1st factor negative
      std::string aux{input.begin(), input.begin()+previous_symbol};
      aux.push_back('+');
      aux.append(input.begin()+previous_symbol, input.end());
      input.assign(aux);
      idx_add_subtract_symbol++;
    }
    int next_symbol = input.find_first_of("+-", idx_add_subtract_symbol+1);

    // if no previous/next symbol found
    if (previous_symbol == std::string::npos)
      previous_symbol = -1;   
    if (next_symbol == std::string::npos)
      next_symbol = input.size();

    // if just one symbol & number left, cancel symbol if ;+', and exit
    if (idx_add_subtract_symbol==0) {
      if (input[0] == '+' || input[1] == '0')
        input.assign(input.begin()+1, input.end());
      break;
    }

    // same as previous function
    int res{doArithmetic(input, previous_symbol, idx_add_subtract_symbol, next_symbol)};

    std::string add_subtract_str = std::to_string(res);
    std::string plug_result{};
    // edge cases
    if (previous_symbol > 0)
      plug_result.assign(input.begin(), input.begin()+previous_symbol+1);
    if (add_subtract_str[0] == '-') {
      if (!plug_result.empty())
        plug_result.pop_back();
      if (input[previous_symbol] == '-' && previous_symbol!=0) {
        add_subtract_str.assign(add_subtract_str.begin()+1, add_subtract_str.end());
        plug_result.push_back('+');
      }
    }
    plug_result.append(add_subtract_str);
    plug_result = plug_result + input.substr(next_symbol, input.size()-next_symbol);
    input.assign(plug_result);
    idx_add_subtract_symbol = input.find_last_of("+-");
  }
}


void parseParentheses(std::string& input) {
  size_t idx_close_bracket = input.find_first_of(")");

  // starting from the innermost bracketed operation, progressively resolve all bracketed operations
  while (idx_close_bracket != std::string::npos) {
    // locate the matching opening parenthesis
    size_t idx_open_bracket = input.find_last_of("(", idx_close_bracket);
    if (idx_open_bracket == std::string::npos)
      throw std::logic_error("Parentheses don't match\n");

    std::string inside_parentheses{input.substr(idx_open_bracket+1, idx_close_bracket-idx_open_bracket-1)};

    // perform operations inside parentheses ( )
    parseMultDivMod(inside_parentheses);
    parseAddSubtract(inside_parentheses);

    // collate result of bracketed operation to std::string input
    std::string plug_result{input.begin(), input.begin()+idx_open_bracket};
    // edge cases
    if (inside_parentheses[0] == '-') {
      if (!plug_result.empty())
        plug_result.pop_back();
      if (input[idx_open_bracket-1] == '-') {
        inside_parentheses.assign(inside_parentheses.begin()+1, inside_parentheses.end());
      }
    }
    plug_result.append(inside_parentheses);
    plug_result = plug_result + input.substr(idx_close_bracket+1, input.size()-idx_close_bracket);
    input.assign(plug_result);  // using auxiliary std::string above + assign() method, helps preserve iterators
    idx_close_bracket = input.find_first_of(")");
  } 
}


void parseOperation(std::string& input) {
  parseParentheses(input);
  parseMultDivMod(input);
  parseAddSubtract(input);

  printf("= %s\n", input.c_str());
}


int main(int argc, char** argv) {
  try {
    std::string my_input{std::move(argvParser(argc, argv)};
    parseOperation(my_input);
  } 
  catch(const std::exception& e) {
    printf("Thrown exception:\n%s\n", e.what());
  }
}

Answer 1

There are quite some issues with this code. Apart from the fact that string manipulation is best avoided as much as possible, the code looks quite unreadable; it's dense and there's lots of almost-but-not-quite code duplication. Let's go over the issues:

Only take a single argument

The whole argvParser() would not be necessary if you just take the input as a single argument. Sure, you have to quote the input string, so instead of writing ./calculate 1 + 2 or calculate.exe 1 + 2, you'd have to write ./calculate "1 + 2" or calculate.exe "1 + 2". But that's actually preferred, because depending on which shell you are on, without quotes, some symbols, especially the wildcard character *, will cause problems anyway if they are not quoted or escaped. So, just write:

int main(int argc, char** argv) {
    parseOperation(argv[1]);
}

This doesn't compile because parseOperation() takes the input by non-const references. The fix here is to take it the string by value:

void parseOperation(std::string input) {
    …
}

Use the C++ way of printing

When writing C++ code, avoid writing legacy C code. When printing, either write:

std::cout << "= " << input << "\n";

Or since C++23 you can write:

std::println("= {}", input);

C++'s functions are type-safe, and can also handle much more types of values.

Reduce the responsibilities of functions

Functions should have one task and do it well, and shouldn't do more than necessary. Conside parseOperation(): it not only parses the expression, it also prints the results. Instead, consider having it return the result, and let main() deal with printing it:

std::string parseOperation(std::string input) {
    parseParentheses(input);
    parseMultDivMod(input);
    parseAddSubtract(input);

    return input;
}

int main(int argc, char **argv) {
    std::println("= {}", parseOperation(argv[1]));
}

This might not seem like a big deal at first, but despite parseOperation() doing less, it's now much more flexible: if you want to save the result to disk instead of printing it to the screen, or use it as the input for another function, that's now easy to do.

Avoid code duplication

There is a lot of code duplication between parseMultDivMod() and parseAddSubtract. You even wrote so in a comment. Ideally, you move the duplicated code into its own function.

Have a look at those two functions, and find the differences. If it wasn't for the handling of negative numbers, the only difference would be which sets of operators are searched for. Those could be passed as a parameter. Then you could write something like:

std::string parseOperation(std::string input) {
    parseParentheses(input);
    parseOperators(input, "*/%");
    parseOperators(input, "+-");

    return input;
}

If you need to do some operators from right-to-left instead of from left-to-right, you could perhaps pass a bool parameter telling it to reverse direction.

Parse issues

Despite your attempts to make it parse negative numbers correctly, it doesn't always work right. Try for example to parse the following expression:

((-1))

Better ways to parse expressions

I know you wrote this particular implementation because it was an excercise in std::string manipulation. However, while it can be made to work, it's a bad example as there are much better ways to parse expressions. The string manipulation method has several disadvantages: it's very inefficient since y ou search strings repeatedly for operators, and convert from strings to ints and back. Most importantly though, it's quickly getting much more complicated when adding more operators.

For a much better way to parse expressions, I recommend trying to implement a Pratt parser.

Answer 2

Use the tools the library provides

You can greatly simplify your string manipulations by using std::string::replace, e.g.

std::string inside_parentheses{input.substr(idx_open_bracket+1, idx_close_bracket-idx_open_bracket-1)};

// perform operations inside parentheses ( )
parseMultDivMod(inside_parentheses);
parseAddSubtract(inside_parentheses);

input.replace(idx_open_bracket, idx_close_bracket-idx_open_bracket, inside_parentheses);

Similarly, you can simplify argvParser by using std::regex_replace to remove any whitespace.

std::string argvParser(const int argc, char** argv) {
  std::string output;
  std::regex whitespace { "\w" };

  // parse input word by word ...
  for (auto word_index=1; word_index<argc; ++word_index)
    output.append(std::regex_replace(argv[wordindex], whitespace, ""));
  }

  return output;
}

Also note that neither operators nor numbers have uppercase, so boost::algorithm::to_upper seems superfluous.

Parse from left to right

It is much simpler for code to match the way that a human would do things. You are trying to simulate the left-to-right rule for addition and subtraction, but are doing it right-to-left. To handle leading -, remember that all the operators that you care about evaluating follow a number, so you can start looking from the second character in the string.

idx_add_subtract_symbol = input.find_first_of("+-"sv, 1);

Use more substrings, and hold them in std::string_view when appropriate.

If, once you have identified the position of the operator you are evaluating, you split the input into before and after, it is much easier to find the numbers.

std::string_view left = input_view.substr(0, idx_add_subtract_symbol - 1);
std::string_view remaining = input_view.substr(idx_add_subtract_symbol + 1)
int next_symbol = remaining.find_first_not_of("0123456789");
std::string_view right = remaining.substr(0, next_symbol - 1);

doArithmetic should operate on std::string_views as input.