Infix calculator programming challenge Kattis.com

Question

I'm working on this C++ coding problem:

Input is a sequence of up to commands, one per line, ending at end of file. Each command is a definition, a calculation, or a clear. All tokens within a command are separated by single spaces.

A definition has the format def x y where x is a variable name and y is a an integer in the range . No two variables are ever defined to have the same numeric value at the same time. If x had been defined previously, defining it again erases its old definition. Variable names are up to lowercase characters, each character from the range a to z.

A calculation command starts with the word calc, and is followed by one to more variable names separated by addition or subtraction operators. The end of a calc command is an equals sign. For example:

calc foo + bar - car =

The clear command instructs your program to forget all of its definitions.

Your program should produce no output for definitions, but for calculations it should produce the value of the calculation. If there is not a word for the result, or some word in the calculation has not been defined, then the result of the calculation should be unknown. The word unknown is never used as a variable in the input.

Here is my solution, which works, but is way too slow. There is surely many ways to optimise it, but for me it's not obvious right away. Starting to feel like there's probably a way more straight forward way to solve this, but I just can't see it. Any advice?

#include <deque>
#include <fstream>
#include <iostream>
#include <map>
#include <sstream>
#include <string>
#include <vector>

std::map<std::string, std::string> definitions;

int doCalculation(int a, int b, char op){
    switch(op){
        case '+': return a + b;
        case '-': return a - b;
    }
    return 0;
}

void evaluateTranslatedCalcString(std::string &calc_string, std::string &translated_calc_string){

     std::string calc_result;

     if(translated_calc_string == "unknown"){
         calc_result = "unknown";
     }

     else{
         std::deque<int> vals;
         std::deque<char> ops;

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

             if(translated_calc_string[i] == ' '){
                 continue;
             }

             else if (std::isdigit(translated_calc_string[i])){
                 int val = 0;
                 // There may be more than one digit in the number.
                 while(i < translated_calc_string.length() && isdigit(translated_calc_string[i]))
                 {
                     val = (val*10) + (translated_calc_string[i]-'0');
                     i++;
                 }
                 vals.push_back(val);
                 // Correct offset made by the while loop.
                 i--;
             }

             else if(translated_calc_string[i] == '+' || translated_calc_string[i] == '-'){
                 ops.push_back(translated_calc_string[i]);
             }
         }

         while(!ops.empty()){
             int val1 = vals.front();
             vals.pop_front();

             int val2 = vals.front();
             vals.pop_front();

             char op = ops.front();
             ops.pop_front();

             vals.push_front(doCalculation(val1, val2, op));
         }

         for(auto it = definitions.begin(); it != definitions.end(); it++){
             if(std::to_string(vals.front()) == it->second){
                 calc_result = it->first;
             }
         }
         if(calc_result.empty()){
             calc_result = "unknown";
         }
     }

    //Logging
    std::cout << calc_string << calc_result << std::endl;
    std::cout << std::endl;
}

void translateCalcString(std::string &calc_string){

    std::string translated_calc_string;

    std::stringstream ss (calc_string);
    std::string calc_item;
    std::deque<std::string> calc_items;
    char delim = ' ';

    while (getline (ss, calc_item, delim)){
        calc_items.push_back(calc_item);
    }

    for(int i = 0; i < calc_items.size(); i++){
        if(calc_items[i] == "="){
            continue;
        }
        else if(definitions.find(calc_items[i]) != definitions.end()){
            translated_calc_string += definitions[calc_items[i]] + " ";
        }
        else if(calc_items[i] == "+" || calc_items[i] == "-"){
            translated_calc_string += calc_items[i] + " ";
        }
        else{
            translated_calc_string = "unknown";
        }
    }

    evaluateTranslatedCalcString(calc_string, translated_calc_string);
}

void addDefinition(std::deque<std::string> &command_items){
    definitions[command_items[0]] = command_items[1];
}

void makeCalcString(std::deque<std::string> &command_items){
    std::string calc_string;

    for(int i = 0; i < command_items.size(); i++){
        calc_string += command_items[i] + " ";
    }

    translateCalcString(calc_string);
}

void getCommandType(std::string &command){
    std::stringstream ss (command);
    std::string command_item;
    std::deque<std::string> command_items;
    char delim = ' ';

    while (getline (ss, command_item, delim)){
        command_items.push_back(command_item);
    }

    if(command_items.front() == "def"){
        command_items.pop_front();
        addDefinition(command_items);
    }

    else if(command_items[0] == "calc"){
        command_items.pop_front();
        makeCalcString(command_items);
    }

    else{
        definitions.clear();
    }
}

int main() {
    std::vector<std::string> commands;
    std::ifstream infile;
    infile.open("commands.txt", std::ifstream::in);
    std::string command;
    while (!infile.eof())
    {
        getline(infile, command);
        if (!command.empty())
        {
            commands.push_back(command);
        }
    }
    infile.close();
    for(int i = 0; i < commands.size(); i++){
        getCommandType(commands[i]);
        
    }

    return 0;
}

Answer 1

My first suggestion is to stop doing 2 passes through the file. Just call get_command_type() on every non-empty command from getline(). That avoids the need for creating and growing the vector, which should help save time too.

make_calc_string is rebuilding the original string you split in get_command_type and then passing it to translate_calc_string which is splitting it again? Why? There's no need to parse every string into a collection. You are allowed to use raw strings in C++. I'm guessing a profiler would show a lot of time in constructors.

You can combine a lot of these layers: translate_calc_string could be as simple as:

int op = 1;
int sum = 0;
while ( getline(ss, token, delim) ) {
    auto it = definitions.find(token);
    if (it != definitions.end) {
        int value = *it;
        sum += op *value;
    }
    else if (token == '+') { op = 1; }
    else if (token == '-') { op = -1; }
    else if (token == '=') { 
       cout << lookup_name_for(sum) << endl;
    }
}       

This assumes well formed input, and that you are doing an atoi on the definitions when you put them into the dictionary, but you should get the idea.