3
\$\begingroup\$

I'm learning C++ by implementing a previous project I did in Python. This is a simple stack machine which evaluates mathematical expressions, e.g. pow(9, 12). The code to run this on the stack machine would be an ordered list of constants and instructions: 12 9 POW.

In Python, preparing such a list is quite straightforward due to the heterogeneous nature of Python containers. I just make a list of numeric types for the constants and string types for the instructions, e.g. [12, 9, "op_pow"]. Constants get pushed to a data stack, and strings are looked up in a dispatch map for their corresponding functions.

I'm a bit stuck on how to do the same thing in C++, due to containers only having a single type. The very inefficient way I'm currently doing it is by passing a program as a vector of strings, and then converting the string constants to doubles with the fast_float library.

Is there a more efficient way to do this?

Below is what I have so far:

#include <vector>
#include <cmath>
#include <string_view>
#include <string>
#include <iostream>

#include "fast_float/fast_float.h"



class Machine {


    public:
        
        std::vector<double> stack ;
        
        
        void add () {
            if (stack.size() > 1) { 
                double a {stack[stack.size() - 1]} ; 
                double b {stack[stack.size() - 2]} ; 
                stack.pop_back() ;
                stack.pop_back() ;
                
                stack.emplace_back(a+b) ; }
        }
        
        
        void sub () {
            if (stack.size() > 1) { 
                double a {stack[stack.size() - 1]} ; 
                double b {stack[stack.size() - 2]} ; 
                stack.pop_back() ;
                stack.pop_back() ;
                
                stack.emplace_back(a-b) ; }
        }
        
        
        void mul () {
            if (stack.size() > 1) { 
                double a {stack[stack.size() - 1]} ; 
                double b {stack[stack.size() - 2]} ; 
                stack.pop_back() ;
                stack.pop_back() ;
                
                stack.emplace_back(a*b) ; }
        }
        
        
        void div () {
            if (stack.size() > 1 
                && !(stack[stack.size() - 1] == 0) 
                && !(stack[stack.size() - 2] == 0)) { 
                double a {stack[stack.size() - 1]} ; 
                double b {stack[stack.size() - 2]} ; 
                stack.pop_back() ;
                stack.pop_back() ;
                
                stack.emplace_back(a/b) ; }
        }
        
        
        void mod () {
            if (stack.size() > 1 
                && !(stack[stack.size() - 1] == 0) 
                && !(stack[stack.size() - 2] == 0)) { 
                double a {stack[stack.size() - 1]} ; 
                double b {stack[stack.size() - 2]} ; 
                stack.pop_back() ;
                stack.pop_back() ;
                
                stack.emplace_back(std::fmod(a,b)) ; }
        }
        
        
        void flr () {
            if (stack.size() > 0) { 
                double a {stack[stack.size() - 1]} ; 
                stack.pop_back() ;
                
                stack.emplace_back(std::floor(a)) ; }
        }
        
        
        void cei () {
            if (stack.size() > 0) { 
                double a {stack[stack.size() - 1]} ; 
                stack.pop_back() ;
                
                stack.emplace_back(std::ceil(a)) ; }
        }
        
        
        
        void abs () {
            if (stack.size() > 0) { 
                double a {stack[stack.size() - 1]} ; 
                stack.pop_back() ;
                
                stack.emplace_back(std::fabs(a)) ; }
        }
        
    
    
        void sqrt () {
            if (stack.size() > 0 
                && stack[stack.size() - 1] > 0) { 
                double a {stack[stack.size() - 1]} ;
                stack.pop_back() ;
                
                stack.emplace_back(std::sqrt(a)) ; }
        }
        
        
        void pow () {
            if (stack.size() > 1 
                && stack[stack.size() - 1] > 0) { 
                double a {stack[stack.size() - 1]} ;
                double b {stack[stack.size() - 2]} ;
                stack.pop_back() ;
                stack.pop_back() ;
                
                stack.emplace_back(std::pow(a, b)) ; }
        }
        
        
        void log () {
            if (stack.size() > 0 
                && stack[stack.size() - 1] > 0) { 
                double a {stack[stack.size() - 1]} ;
                stack.pop_back() ;
                
                stack.emplace_back(std::log(a)) ; }
        }
        
        
        void exp () {
            if (stack.size() > 0) { 
                double a {stack[stack.size() - 1]} ;
                stack.pop_back() ;
                
                stack.emplace_back(std::exp(a)) ; }
        }
        
        
        
        void sin () {
            if (stack.size() > 0) { 
                double a {stack[stack.size() - 1]} ;
                stack.pop_back() ;
                
                stack.emplace_back(std::sin(a)) ; }
        }
        
        
        void cos () {
            if (stack.size() > 0) { 
                double a {stack[stack.size() - 1]} ;
                stack.pop_back() ;
                
                stack.emplace_back(std::cos(a)) ; }
        }
        
        
        void tan () {
            if (stack.size() > 0) { 
                double a {stack[stack.size() - 1]} ;
                stack.pop_back() ;
                
                stack.emplace_back(std::tan(a)) ; }
        }
        
        
        
        double run (const std::vector<std::string> &program) {
            
            double num ;
            
            for (std::string_view instruction : program) {
                
                if (instruction == "op_add") { add() ; }
                else if (instruction == "op_sub") { sub() ; }
                else if (instruction == "op_mul") { mul() ; }
                else if (instruction == "op_div") { div() ; }
                else if (instruction == "op_mod") { mod() ; }
                else if (instruction == "op_flr") { flr() ; }
                else if (instruction == "op_cei") { cei() ; }
                else if (instruction == "op_abs") { abs() ; }
                else if (instruction == "op_sqrt") { sqrt() ; }
                else if (instruction == "op_pow") { pow() ; }
                else if (instruction == "op_log") { log() ; }
                else if (instruction == "op_exp") { exp() ; }
                else if (instruction == "op_sin") { sin() ; }
                else if (instruction == "op_cos") { cos() ; }
                else if (instruction == "op_tan") { tan() ; }
                else {
                    
                fast_float::from_chars(
                    instruction.data(), 
                    instruction.data() + 
                    instruction.size(), 
                    num);
                
                stack.emplace_back(num) ; }
                    
            
            }
        
        
            if (stack.size()) {
                
                return stack[stack.size() -1] ;
                
                } 
            
            else {
                
                return 0 ;
                
                } 
        
            
        }
    
    
};





int main(int argc, char *argv[]) {
    
    std::vector<std::string> program (argv + 1, argv + argc);
    
    double solution ;
    
    Machine machine ;
    
    machine.stack.reserve(50) ;

    solution = machine.run(program) ;
    
    machine.stack.clear() ;

    std::cout << solution << '\n' ;    
    
    return 0 ;
    
}

\$\endgroup\$
2
  • \$\begingroup\$ Is your main() supposed to be double-spaced like that, or is it a problem of how you copied the code into your question? \$\endgroup\$ Nov 11, 2021 at 17:36
  • 1
    \$\begingroup\$ @upkajdt I’m not OP but IIRC from_chars was not implemented until recently for gcc (msvc had it since Stephan, the STL, wrote the first one). \$\endgroup\$ Nov 11, 2021 at 19:21

4 Answers 4

2
\$\begingroup\$

Here is what I would recommend doing:

  1. Create an enum class called Operation (or something of that sort) with its values being all of the different operator names (POW, ABS, etc.) Info on enum class here.
  2. Globally overload the operator>> operator for Operations This overload should read into a static temporary string of some sort and convert that string into an Operation. This enables you to use switch statements instead of a chain if-else statements.
  3. Since every instruction must have at least one double before an op, read a double, peek at the next character, if the character is a letter then read an Operation; else repeat.
  4. Instead of storing the operations and the numbers in a vector of strings, simply have a std::stack<double> for storing the args and calculate values "on the fly", meaning that operations take place immediately and update the stack accordingly.

For any questions on how to do any of these things, look them up here.

\$\endgroup\$
1
\$\begingroup\$

In Python, preparing such a list is quite straightforward due to the heterogeneous nature of Python containers. I just make a list of numeric types for the constants and string types for the instructions, e.g. [12, 9, "op_pow"]. Constants get pushed to a data stack, and strings are looked up in a dispatch map for their corresponding functions.

Use std::variant<double,std::string>. Then use std::visit to perform a different action depending on the type of the element.

struct instruction_visitor {

    void operator() (double x) const 
        { stack.push_back(x); }

    void operator() (const std::string& cmd) const
        {
            // interpret the command string
        }
};

On the other hand, it makes sense that if you are treating the commands as strings to be parsed as part of the interpretation, why not treat constants the same way, as strings? That is not an issue with your existing code as presented; that is the way it ought to work if you want to load a text file and run it.

If you will have numbers as actual numbers already of the right type, then why wouldn't you do the same thing with the commands? You don't need a mapping from command name string to the function! Rather, just put a function pointer directly in the instruction list.

using command_t = void(*)();
using instruction = std::variant<double,command_t>;


struct instruction_visitor {

    void operator() (double x) const 
        { stack.push_back(x); }

    void operator() (command_t cmd) const
        { cmd(); }
};

But as you show it, you (rightfully) have an instruction list of strings, and you decide whether it's a literal or command (and later, a variable perhaps) as part of the interpretation. There is no need for a variant type anywhere, and your approach is sound. (Though I would suggest a data structure rather than a gang of if/else statements)


In your implementation:

                double a {stack[stack.size() - 1]} ; 
                double b {stack[stack.size() - 2]} ; 
                stack.pop_back() ;
                stack.pop_back() ;

You should write a helper function pop, something like:

double pop()
{
     double retval= stack.back();
     stack.pop_back();
     return retval;
}

Then you can write simply

     const double a = pop();
     const double b = pop();
     stack.push_back (a+b);

If you want to get fancier, you could implement a helper that does the argument count check and pops all of them:

     const auto [a,b] = take<2>();
\$\endgroup\$
1
  • 1
    \$\begingroup\$ You are correct as always ;-) for a simple sequential list of instructions like we currently have, there is no benefit to first parse it to vector of variants. \$\endgroup\$
    – jdt
    Nov 12, 2021 at 13:55
1
\$\begingroup\$

If the program is read from command line arguments or from another external source, then you will have to convert strings to doubles at some point. If you only ever run the program once, then what you are doing is fine. However, if you intend to call run() multiple times, then it would indeed be better to convert the input in something that is more efficient to handle. I think upkajdt's answer of using a std::variant that can hold a double or a std::function is a very reasonable way to do it.

You could go further than this; I explored this myself a bit in this question about creating a poor man's JIT using lambdas, some of the answers there might be helpful as well. The most extreme way of optimizing it would be to compile the program to machine code. This is certainly possible but has several drawbacks; apart from the fact that compiling the code takes a lot longer than interpreting it, meaning that it only pays of if you call the program a lot, there's also the dependency on a compiler or a library like libclang.

\$\endgroup\$
1
\$\begingroup\$

I think that the closest that you might get to this in C++ is to:

  1. Use std::variant for the instructions
  2. Create lookup list for the function with std::map
  3. Implement your own pop function as suggested by @JDługosz

Since you are not supposed to take an address of a library function, and using old school function pointer is frowned upon, I have updated it to the following:

#include <charconv>
#include <cmath>
#include <functional>
#include <iostream>
#include <map>
#include <sstream>
#include <string>
#include <variant>
#include <vector>

typedef std::tuple<std::size_t, std::function<double(double, double)>> funcspec; 
typedef std::variant<double, funcspec> instruction;

std::vector<instruction> parse(const std::vector<std::string>& args)
{
    static std::map<std::string, funcspec> functions{
          { "op_abs",  { 1, [](double a, double) { return std::fabs(a); } } },
          { "op_cos",  { 1, [](double a, double) { return std::cos(a); } } },
          { "op_exp",  { 1, [](double a, double) { return std::exp(a); } } },
          { "op_log",  { 1, [](double a, double) { return std::log(a); } } },
          { "op_sin",  { 1, [](double a, double) { return std::sin(a); } } },
          { "op_tan",  { 1, [](double a, double) { return std::tan(a); } } },
          { "op_flr",  { 1, [](double a, double) { return std::floor(a); } } },
          { "op_sqrt", { 2, [](double a, double) { return std::sqrt(a); } } },
          { "op_add",  { 2, [](double a, double b) { return a + b; } } },
          { "op_div",  { 2, [](double a, double b) { return a / b; } } },
          { "op_mul",  { 2, [](double a, double b) { return a * b; } } },
          { "op_sub",  { 2, [](double a, double b) { return a - b; } } },
          { "op_pow",  { 2, [](double a, double b) { return std::pow(a, b); } } },
          { "op_mod",  { 2, [](double a, double b) { return std::fmod(a, b); } } }
    };

    std::vector<instruction> instructions;
    for (auto arg : args)
    {
        // numbers
        double number;
        auto ret = std::from_chars(arg.data(), arg.data() + arg.size(), number);
        if (ret.ec == std::errc() && ret.ptr == arg.data() + arg.size())
        {
            instructions.emplace_back(number);
            continue;
        }

        // functions
        auto funcion = functions.find(arg);
        if (funcion != functions.end())
        {
            instructions.emplace_back(funcion->second);
            continue;
        }

        std::ostringstream oss;
        oss << "Error: invalid instruction: " << arg;
        throw std::runtime_error(oss.str());
    }
    return instructions;
}

double pop(std::vector<double>& stack)
{
    if (stack.empty())
        throw std::runtime_error("Error: failed to pop value from an empty stack");
    double retval = stack.back();
    stack.pop_back();
    return retval;
}

double run(const std::vector<instruction>& instructions)
{
    std::vector<double> stack;
    double a = 0;
    double b = 0;
    stack.reserve(50);
    for (const auto& inst : instructions)
    {
        if (inst.index() == 0)
        {
            stack.emplace_back(std::get<double>(inst));
        }
        else
        {
            auto funcion = std::get<funcspec>(inst);
            if (std::get<0>(funcion) == 1)
                stack.emplace_back(std::get<1>(funcion)(pop(stack), 0));
            else
                stack.emplace_back(std::get<1>(funcion)(pop(stack), pop(stack)));
        }
    }
    return stack.empty() ? 0 : stack.back();
}

int main(int argc, char* argv[])
{
    try
    {
        auto arguments = std::vector<std::string>(argv + 1, argv + argc);
        auto instructions = parse(arguments);
        std::cout << run(instructions);
    }
    catch (std::exception err)
    {
        std::cerr << err.what();
        return 1;
    }
}
\$\endgroup\$
1
  • \$\begingroup\$ The OP is looking for efficiency, not simplicity. \$\endgroup\$ Nov 11, 2021 at 21:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.