Polish notation interpreter/calculator

Question

Just for the heck of it, I wrote a simple little interpreter that takes in inputs in the form of Polish Notation.

The user will input something like

+ 5 6

And it will then output

11

Here's another sample input:

+ 5 * 2 3

And the output:

11

Users can even define their own variables, like this:

def myVar 10

and like this:

def anotherVar + 5 6

And then of course reuse those variables. So let's say you type

myVar

it will ouput

10

or

anotherVar

which outputs

11

Furthermore, you type in

+ myVar anotherVar

you would then get

21

---

I'm a total newbie to well-formatted and readable code. What would be a good way to refactor this?

#include <iostream>
#include <vector>
#include <string>
#include <sstream>

using namespace std;

class Variable
{
public:
    Variable(const string& name, double val)
    {
        this->name = name;
        this->val = val;
    }

    inline const string& get_name() const { return name; }
    inline double get_val() const { return val; }
private:
    string name;
    double val;
};

//----------------------------------

double operate(const string& op, istringstream& iss, vector<Variable>& v);
double perform_addition(istringstream& iss, vector<Variable>& v);
double perform_subtraction(istringstream& iss, vector<Variable>& v);
double perform_division(istringstream& iss, vector<Variable>& v);
double perform_multiplication(istringstream& iss, vector<Variable>& v);
void define_new_var(vector<Variable>& v, istringstream& iss);

bool is_number(const string& op)
{
    int char_to_int = op[0];
    if (char_to_int >= 48 && char_to_int <= 57)
        return true;

    return false;
}

void print_var_list(vector<Variable>& v)
{
    int size = v.size();
    for (int i = 0; i < size; i++)
    {
        cout << v[i].get_name() << ", " << v[i].get_val() << endl;
    }
    cout << endl;
}

int main()
{
    cout << endl << "LeRPN Programming Language" << endl;

    vector<Variable> v;

    string temp;
    while (cin)
    {
        cout << endl << "> ";

        getline(cin, temp);

        istringstream iss(temp);
        string op;
        iss >> op;

        if (op == "quit")
            break;
        else if (op == "def")
            define_new_var(v, iss);
        else if (op == "show_vars")
            print_var_list(v);
        else
            cout << endl << operate(op, iss, v) << endl;
    }
}

double perform_addition(istringstream& iss, vector<Variable>& v)
{
    string left;
    iss >> left;

    string right;
    iss >> right;

    return operate(left, iss, v) + operate(right, iss, v);
}

double perform_subtraction(istringstream& iss, vector<Variable>& v)
{
    string left;
    iss >> left;

    string right;
    iss >> right;

    return operate(left, iss, v) - operate(right, iss, v);
}

double perform_division(istringstream& iss, vector<Variable>& v)
{
    string left;
    iss >> left;

    string right;
    iss >> right;

    return operate(left, iss, v) / operate(right, iss, v);
}

double perform_multiplication(istringstream& iss, vector<Variable>& v)
{
    string left;
    iss >> left;

    string right;
    iss >> right;

    return operate(left, iss, v) * operate(right, iss, v);
}

double get_variable(const string& op, vector<Variable>& v)
{
    int size = v.size();
    for (int i = 0; i < size; i++)
    {   
        if (op == v[i].get_name())
            return v[i].get_val();
    }
}

double operate(const string& op, istringstream& iss, vector<Variable>& v)
{   
    double value;
    if (op == "+")
        value = perform_addition(iss, v);
    else if (op == "-")
        value = perform_subtraction(iss, v);
    else if (op == "/")
        value = perform_division(iss, v);
    else if(op == "*")
        value = perform_multiplication(iss, v);
    else if (is_number(op))
        value = atof(op.c_str());
    else
        value = get_variable(op, v);

    return value;
}

void define_new_var(vector<Variable>& v, istringstream& iss)
{
    string name;
    iss >> name;

    string temp;
    iss >> temp;

    double value = operate(temp, iss, v);

    v.push_back(Variable(name, value));
}

Answer 1

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <cstdlib> // mmocny: I needed to add this to use atof
#include <functional>

using namespace std;

//----------------------------------

class Variable
{
public:
    Variable(const string& name, double val)
        : name_(name), val_(val) // mmocny: Use initializer lists
    {
    }

    // mmocny: get_* syntax is less common in C++ than in java etc.
    const string& name() const { return name_; } // mmocny: Don't mark as inline (they already are, and its premature optimization)
    double val() const { return val_; } // mmocny: Again, don't mark as inline
private:
    string name_; // mmocny: suggest renaming name_ or _name: Easier to spot member variables in method code, and no naming conflicts with methods
    double val_;
};

//----------------------------------

// mmocny: Replace print_* methods with operator<< so that other (non cout) streams can be used.
// mmocny: Alternatively, define to_string()/str() methods which can also be piped out to different streams
std::ostream & operator<<(std::ostream & out, Variable const & v)
{
    return out << v.name() << ", " << v.val() << endl;
}

std::ostream & operator<<(std::ostream & out, vector<Variable> const & v)
{
    for (vector<Variable>::const_iterator it = v.begin(), end = v.end(); it != end; ++it ) // mmocny: Use iterators rather than index access
    {
        out << *it << endl;
    }
    return out;
}

//----------------------------------

double get_variable(const string& op, vector<Variable>& v)
{
    // mmocny: instead of using a vector<Variable> you should be using a map/unordered_map<string,double> and doing a key lookup here
    int size = v.size();
    for (int i = 0; i < size; i++)
    {   
        if (op == v[i].name())
            return v[i].val();
    }
    // mmocny: what do you do if you don't find the variable?
    throw std::exception(); // mmocny: You should do something better than throw a generic exception()
}

//----------------------------------

bool is_number(const string& op)
{
    // mmocny: someone else already mentioned: what if op is empty?
    int char_to_int = op[0];
    // mmocny: couple notes here:
    // 1) chars are actually numbers you can reference directly, and not need "magic" constants
    // 2) functions in the form "if (...) return true; else return false;" should just be reduced to "return (...);"
    // 3) is_number functionality already exists in libc as isdigit()
    // 4) long term, you are probably going to want to improve this function.. what about negative numbers? numbers in the form .02? etc..
    //return (char_to_int >= '0' && char_to_int <= '9');
    return isdigit(char_to_int);
}

//----------------------------------

// mmocny: replace istringstream with istream
// mmocny: you only need to predeclare this one function
double operate(const string& op, istream& in, vector<Variable>& v);

//----------------------------------
/*
 * mmocny: All of your perform_* functions have identical code other than the operator being used.
 * You can turn all of these functions into a single function template where you pass the operator to be used.
 * Luckily, <functional> already has plus minus multiplies divides function objects (functors)
 */

template< class Operator >
double perform_action(istream& in, vector<Variable>& v, Operator op)
{
    string left;
    in >> left;

    double result = operate(left, in, v); // mmocny: This is a big one: for correctness, you must calculate result of left BEFORE you read right

    string right;
    in >> right;

    return op(result, operate(right, in, v));
}

//----------------------------------

double operate(const string& op, istream& in, vector<Variable>& v)
{   
    double value;
    if (op == "+")
        value = perform_action(in, v, plus<double>());
    else if (op == "-")
        value = perform_action(in, v, minus<double>());
    else if(op == "*")
        value = perform_action(in, v, multiplies<double>());
    else if (op == "/")
        value = perform_action(in, v, divides<double>());
    else if (is_number(op))
        value = atof(op.c_str()); // mmocny: consider using boost::lexical_cast<>, or strtod (maybe)
    else
        value = get_variable(op, v);

    return value;
}

//----------------------------------

void define_new_var(vector<Variable>& v, istream& in)
{
    string name;
    in >> name;

    string temp;
    in >> temp;

    double value = operate(temp, in, v);

    v.push_back(Variable(name, value));
}

//----------------------------------

int main()
{
    cout << endl << "LeRPN Programming Language" << endl;

    vector<Variable> v;

    string temp;
    while (cin)
    {
        cout << endl << "> ";

        getline(cin, temp);

        if (temp.empty()) // mmocny: This also handles the case of CTRL+D
            continue;

        istringstream iss(temp);
        string op;
        iss >> op;

        if (op == "quit")
            break;
        else if (op == "def")
            define_new_var(v, iss);
        else if (op == "show_vars")
            std::cout << v << std::endl;
        else
            cout << endl << operate(op, iss, v) << endl;
    }
}

Those are my changes, with comments inline. I would make more changes, but thats enough for now :)

Notice one BIG change: you have a serious correctness bug in your perform_* functions. Not that I've tested my modified code above for all edge cases, but the original code was flat out always wrong for any nested calculations.

Answer 2

As a minor aside, I've renamed it to PN instead of RPN. The form you've give (with operators preceding the operands) is Polish Notation as Jan Łukasiewicz invented it. RPN is when you reverse that, and have the operands first, followed by the applicable operator.

As to why they decided to call that RPN: because English speakers had a hard enough time figuring out that his last name was pronounced roughly like "Wookashayvitch", not to mention trying to figure out how to say that backwards.

In any case, I think I'd write the code more like this:

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <map>
#include <iterator>

using namespace std; // really would *not* normally do this, but...

void define_var(map<string, int> &v, istringstream& iss) {
    std::string name;
    int value;
    iss >> name >> value;
    v[name] = value;
}                       

int do_op(char op, int val1, int val2) { 
    switch (op) { 
        case '+': return val1 + val2;
        case '-': return val1 - val2;
        case '*': return val1 * val2;
        case '/': return val1 / val2;
        default: 
            string error("Unknown operator: ");
            error += op;
            throw runtime_error(error);
    }
}

bool isoperator(char ch) { 
    return ch == '+' || ch == '-' || ch == '*' || ch == '/';
}

char getop(istream &is) {
    char ch;
    while (isspace(ch = is.peek()))
        is.get(ch);
    ch = is.peek();
    return ch;
}

int eval(istream &is, map<string, int> const &v) { 
    // evaluate an expression. It consists of:
    // an operator followed by operands, or
    // a number, or
    // a variable.
    // 

    char ch = getop(is);

    if (isoperator(ch)) {
        is.get(ch);
        int val1 = eval(is, v);
        int val2 = eval(is, v);
        return do_op(ch, val1, val2);
    }
    if (isdigit(ch)) {
        int val;
        is >> val;
        return val;
    }

    string var_name;
    is >> var_name;
    map<string, int>::const_iterator p = v.find(var_name);
    if (p==v.end()) {
        string problem("Unknown variable: ");
        problem +=var_name;
        throw runtime_error(problem.c_str());
    }
    return p->second;
}

// used only for dumping out the variables.
namespace std { 
    ostream &operator<<(ostream &os, pair<string, int> const &v) {
        return os << v.first << ": " << v.second;
    }
}

int main() {
    cout << endl << "LePN Programming Language" << endl;

    map<string, int> v;

    string temp;
    cout << endl << "> ";
    while (getline(cin, temp)) {
        istringstream iss(temp);

        string op;
        iss >> op;

        if (op == "quit")
            break;
        else if (op == "def") 
            define_var(v, iss);
        else if (op == "show_vars")
            std::copy(v.begin(), v.end(), ostream_iterator<pair<string, int> >(cout, "\n"));
        else {
            // Technically, this isn't right -- it only ungets one 
            // character, not the whole string.
            // For example, this would interpret "this+ 2 3" as "+ 2 3"
            // and give 5 instead of an error message. Shouldn't affect 
            // correct input though.
            // 
            iss.unget();
            cout << endl << eval(iss, v) << endl;
        }
        cout << endl << "> ";
    }
}

Answer 3

1. double get_variable(const string& op, vector<Variable>& v) - must return default value (0.0), for example if op is empty. Alternatively, you can show an error message.

2. double operate(const string& op, istringstream& iss, vector<Variable>& v) - Always initialize variables, like this:

   double value(0.0); OR
   double value = 0.0;
   

   and you must check this op in vector, if it doesn't exist - show error.

3. void define_new_var(vector<Variable>& v, istringstream& iss) - if variable already exists, set new value or show error.

4. bool is_number(const string& op)

   int char_to_int = op[0];
   

   if op is empty.

5. For this functions:

   double perform_addition(istringstream& iss, vector<Variable>& v);
   double perform_subtraction(istringstream& iss, vector<Variable>& v);
   double perform_division(istringstream& iss, vector<Variable>& v);
   double perform_multiplication(istringstream& iss, vector<Variable>& v);
   

   Define common function who get left and right.

   I think you can define some enums and functions, like this:

   double perform_operator(istringstream& iss, vector<Variable>& v, OperatorType type)
   {
       std::string lhs, rhs;
       GetValues(iss, lhs, rhs); // fill them
       switch(type)
       {
           case Minus
           {
               return operate(left, iss, v) - operate(right, iss, v);
           }
           break;
       }
   }
   

Answer 4

If you look at the similarity of your various perform_xxx functions, it suggests there is duplication that could be removed. One way to do this would be to extract Operator classes, one for each operation, where the common behavior of extracting left and right values from the stream was expressed in the superclass and the individual operations of multiplication, addition, etc. was left to the subclasses.