Four-function expression evaluator

Question

I've been making an interpreter for my own programming language that I've been working on as a hobby. I made an expression evaluator that can evaluate simple mathematical expressions.

It understands +, -, /, *, brackets and the order of operations. I haven't put a modulus operator in the evaluator because I'm going to make a function for modulus instead.

I works in all of the tests I've tried. But I'd appreciate of anyone knows of any complicated expressions that it fails to evaluate.

It also understands that a positive number of minuses is that same as a plus.

It evaluates expressions like this:

(10 + (20 * - (5 + 9)))

and produce the correct output of, -270.

I'd just like to know whether there are any ways I can improve my expression evaluator and whether there are any complicated expressions that don't evaluate correctly.

Also, is there a better way than using the time command on OSX to find out how fast it evaluates because the time command only does to 3 decimal places so it's not accurate enough?

My expression evaluator evaluates the above expression like this:

(10 + (20 * - (14)))

1. It first does the deepest brackets.

   (10 + (20 * -14))
   

2. Then, since there's a minus it multiplies the result of the brackets by -1.

   (10 + (-280))
   

3. Then it does the multiply in the brackets.

   (-270)
   

4. Then it does the addition with the 10 and the -280.

#include <iostream>
#include <string>
#include <fstream>
#include <sstream>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <functional>

using namespace std;

vector<string> rdo_num_stack;
int opp_count = 0;

bool rdo_ws(char c) {
    if (c != ' ')
        return 0;
    else
        return 1;
}

char rdo_expr_item_type(char c) {

    switch(c) {
        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9':
        case '.':
            c = 'n';
            break;
        case '+':
        case '-':
        case '*':
        case '/':
            c = 'o';
            break;
        case '(':
        case ')':
            c = 'b';
            break;
    }

    return c;

}

string rdo_opp_to_string(char opp) {

    string o = "";

    switch(opp) {
        case '+':
            o = "+";
            break;
        case '-':
            o = "-";
            break;
        case '/':
            o = "/";
            break;
        case '*':
            o = "*";
            break;
        case '(':
            o = "(";
            break;
        case ')':
            o = ")";
            break;
    }

    return o;

}

bool rdo_is_num(string is_num) {
    if (is_num == "+" or
        is_num == "-" or
        is_num == "/" or
        is_num == "*" or
        is_num == "(" or
        is_num == ")") {
        return 0;
    }
    return 1;
}

void rdo_count_opp(bool to_count_or_not) {
    if (to_count_or_not == 1)
        opp_count++;
}

string rdo_eval(string expr) {

    string result;
    string num_holder = "";
    string temp_result = "";
    string num1 = "";
    string num2 = "";
    int n2 = 0;
    int i;
    int iter;
    int bcount = 0;
    int depth = 0;
    int current_depth = 0;
    int diff = 0;
    int diff2 = 0;
    int current_b = 0;
    int minus_count = 0;
    int minus_start = 0;
    int plus_count = 0;
    int plus_start = 0;
    bool found_end = 0;
    bool got_diff = 0;
    bool to_inverse = 0;
    bool do_calc = 0;

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

        if (!rdo_ws(expr[i])) {
            if (rdo_expr_item_type(expr[i]) == 'n' or rdo_expr_item_type(expr[i]) == 'o' or rdo_expr_item_type(expr[i]) == 'b') {

                if (rdo_expr_item_type(expr[i]) == 'n') {

                    num_holder += expr[i];

                } else if (rdo_expr_item_type(expr[i]) == 'o') {

                    if (num_holder != "") {

                        rdo_num_stack.push_back(num_holder);
                        num_holder = "";

                    }

                    rdo_num_stack.push_back(rdo_opp_to_string(expr[i]));

                } else {

                    if (num_holder != "") {

                        rdo_num_stack.push_back(num_holder);
                        num_holder = "";

                    }

                    rdo_num_stack.push_back(rdo_opp_to_string(expr[i]));
                    bcount++;

                }
            
            } else {
                cout << "Invalid character in expression" << endl;
                exit(0);
            }

            if (i == expr.length()-1 and num_holder != "") {

                rdo_num_stack.push_back(num_holder);
                num_holder = "";

            }

        }

    }

    if (bcount % 2 != 0) {
        cout << "Extra / Missing parens." << endl;
        exit(0);
    } else {
        bcount /= 2;
    }

    for (i = 0; i < rdo_num_stack.size();i++) {
        if (rdo_num_stack[i] == "(") {
            current_b++;
            
        }
        if (current_b == bcount and !found_end) {
            if (i == 1)
                depth = 0;
            else
                depth = i;
            found_end = 1;
        }
        if (rdo_num_stack[i] == ")" and found_end and !got_diff) {
            diff = i - depth;
            got_diff = 1;
        }
    }


    for (i = depth; i < depth+diff; i++) {

        if (rdo_num_stack[i] == "+" or rdo_num_stack[i] == "-" or rdo_num_stack[i] == "*" or rdo_num_stack[i] == "/") {
            if (rdo_num_stack[i-1] == "(" and rdo_num_stack[i] == "-") {
                rdo_count_opp(0);
            } else if (rdo_num_stack[i-1] == "(" and rdo_num_stack[i] == "+") {
                rdo_count_opp(0);
            } else {
                rdo_count_opp(1);
            }
        }
    
    }


    for (i = depth; i <= depth+diff;i++) {

        if (rdo_num_stack[i] == "+" and rdo_num_stack[i+1] == "-") {

            rdo_num_stack.erase(rdo_num_stack.begin()+i);
            diff -= 1;
        }
        if (rdo_num_stack[i] == "-" and rdo_num_stack[i+1] == "+") {

            rdo_num_stack.erase(rdo_num_stack.begin()+i+1);
            diff -= 1;
        }
    }
        
    for (i = depth; i <= depth+diff;i++) {
        if (rdo_num_stack[i] == "-") {

            minus_count++;

            if (minus_start == 0) {
                minus_start = i;
            }
            
        }
        if (rdo_num_stack[i] != "-") {

            if (minus_count != 0 and minus_count % 2 == 0) {
                
                for (iter = minus_start;iter < minus_start+minus_count;iter++) {
                    rdo_num_stack[iter] = "";
                }
                if (rdo_num_stack[minus_start+minus_count] != "" and rdo_num_stack[minus_start+minus_count][0] != '+') {
                rdo_num_stack[minus_start+minus_count] = "+" + rdo_num_stack[minus_start+minus_count];
                }
                minus_start = 0;
                minus_count = 0;

            } else if (minus_count != 0 and minus_count % 2 != 0) {
                
                for (iter = minus_start;iter < minus_start+minus_count;iter++) {
                    rdo_num_stack[iter] = "";
                }
                rdo_num_stack[minus_start+minus_count] = "-" + rdo_num_stack[minus_start+minus_count];
                minus_start = 0;
                minus_count = 0;

            }
        }
    }

    for (i = depth; i <= depth+diff;i++) {
        if (rdo_num_stack[i] == "+") {

            plus_count++;

            if (plus_start == 0) {
                plus_start = i;
            }
            
        }
        if (rdo_num_stack[i] != "+") {
            for (iter = plus_start;iter < plus_start+plus_count;iter++) {
                    rdo_num_stack[iter] = "";
                }
                if (rdo_num_stack[plus_start+plus_count] != "" and rdo_num_stack[plus_start+plus_count][0] != '(') {
                rdo_num_stack[plus_start+plus_count] = "+" + rdo_num_stack[plus_start+plus_count];
                }

                plus_start = 0;
                plus_count = 0;
        }
    }

    for (i = depth+diff;i >= depth;i--) {
        if (i - 1 >= depth) {
            if (rdo_num_stack[i-1] == "(" and rdo_num_stack[i] != "(" and rdo_num_stack[i][0] != '+' and rdo_num_stack[i][0] != '-'  and rdo_num_stack[i] != "") {
                rdo_num_stack[i] = "+" + rdo_num_stack[i];
            }
            if (rdo_num_stack[i] == "/" and rdo_num_stack[i-1][0] != '+' and rdo_num_stack[i-1][0] != '-') {
                rdo_num_stack[i-1] = "+" + rdo_num_stack[i-1];
            }
            if (rdo_num_stack[i] == "/" and rdo_num_stack[i+1][0] != '+' and rdo_num_stack[i+1][0] != '-') {
                rdo_num_stack[i+1] = "+" + rdo_num_stack[i+1];
            }
            if (rdo_num_stack[i] == "*" and rdo_num_stack[i-1][0] != '+' and rdo_num_stack[i-1][0] != '-') {
                rdo_num_stack[i-1] = "+" + rdo_num_stack[i-1];
            }
            if (rdo_num_stack[i] == "*" and rdo_num_stack[i+1][0] != '+' and rdo_num_stack[i+1][0] != '-') {
                rdo_num_stack[i+1] = "+" + rdo_num_stack[i+1];
            }
        }
        if (rdo_num_stack[i] == "") {
            rdo_num_stack.erase(rdo_num_stack.begin()+i);
            diff-=1;
        }
    }

    div_loop:for (i = depth+diff;i >= depth;i--) {
            
            if (rdo_num_stack[i] == "/") {
                result = to_string(stof(rdo_num_stack[i-1]) / stof(rdo_num_stack[i+1]));
                if (result[0] != '+' and result[0] != '-') {
                    result = "+" + result;
                }
                rdo_num_stack[i-1] = result;
                rdo_num_stack.erase(rdo_num_stack.begin()+i);
                rdo_num_stack.erase(rdo_num_stack.begin()+i);
                diff -= 2;

                goto div_loop;
            }
    }

    mul_loop:for (i = depth+diff;i >= depth;i--) {
            
            if (rdo_num_stack[i] == "*") {
                result = to_string(stof(rdo_num_stack[i-1]) * stof(rdo_num_stack[i+1]));
                if (result[0] != '+' and result[0] != '-') {
                    result = "+" + result;
                }
                rdo_num_stack[i-1] = result;
                rdo_num_stack.erase(rdo_num_stack.begin()+i);
                rdo_num_stack.erase(rdo_num_stack.begin()+i);
                diff -= 2;

                goto mul_loop;
            }

            
    }
  

    minus_loop:for (i = depth; i <= depth+diff;i++) {
        
        if (rdo_num_stack[i][0] == '-' and rdo_num_stack[i-1] != "(") {
            
            result = to_string(stof(rdo_num_stack[i]) + stof(rdo_num_stack[i-1]));
            if (result[0] != '+' and result[0] != '-') {
                result = "+" + result;
            }
            rdo_num_stack[i-1] = result;
            rdo_num_stack.erase(rdo_num_stack.begin()+i);
            diff-=1;
            
            goto minus_loop;

        }

    } 

    plus_loop:for (i = depth; i <= depth+diff;i++) {
        
        if (rdo_num_stack[i][0] == '+' and rdo_num_stack[i-1] != "(") {
            
            result = to_string(stof(rdo_num_stack[i]) + stof(rdo_num_stack[i-1]));
            if (result[0] != '+' and result[0] != '-') {
                result = "+" + result;
            }
            rdo_num_stack[i-1] = result;

            rdo_num_stack.erase(rdo_num_stack.begin()+i);
            diff-=2;
            goto plus_loop;

        }

    }
 
    opp_count = 0;

    for (i = 0; i < rdo_num_stack.size();i++) {
        
        if (rdo_num_stack[i] == "+" or rdo_num_stack[i] == "-" or rdo_num_stack[i] == "*" or rdo_num_stack[i] == "/") {

            opp_count++;

        }

    }

    if (opp_count > 0) {

        for (i = depth; i < depth+diff;i++) {
            if (rdo_num_stack[i] == "(" and rdo_num_stack[i+2] == ")") {
                rdo_num_stack.erase(rdo_num_stack.begin()+i);
                rdo_num_stack.erase(rdo_num_stack.begin()+i+1);

            }
        }

    }

    expr = "";

    for (i = 0; i < rdo_num_stack.size();i++) {
        expr += rdo_num_stack[i];
    }

    expr = "";
    bcount = 0;
    depth = 0;
    for (i = 0; i < rdo_num_stack.size();i++) {
        expr += rdo_num_stack[i];
        if (rdo_num_stack[i] == "(") {
            bcount++;
            depth = i;
        }
    }
    
    result = rdo_num_stack[depth+1];

    rdo_num_stack.clear();
    if (opp_count > 0)
        return rdo_eval(expr);
    else
        expr = to_string(stoi(result));
        return expr;
}

int main() {
    int i;


    cout << rdo_eval("(10 + (20 * - (5 + 9)))") << endl << endl;

    return 0;
}

Answer 1

Common beginner mistakes

Stop doing this:

using namespace std;

See Why is “using namespace std;” considered bad practice?

Namespaces

All your functions seem to have the prefix rdo_

bool rdo_ws(char c)
char rdo_expr_item_type(char c)
string rdo_opp_to_string(char opp)
bool rdo_is_num(string is_num)
void rdo_count_opp(bool to_count_or_not)
string rdo_eval(string expr)

This is old school C classic from before the time of namespaces. Easier to not use the prefix and put all your functions into a namespace called rdo.

Maintainability

You have a seriously long function rdo_eval() (344 lines). Functions that long are considered bad style as they are really hard to read and maintain. A good rule of thumb is that a function should be no longer than your screen (ie you want to be able to read the whole function in a single glance without scrolling), so 40-80 lines.

Also by splitting your function into logic units (smaller functions). If you give each one a meaningful name (and you should) it helps in documenting the code. At the call point you don't have to go and read the code (as the name of the function tells you what is logically happening). Thus it makes the code self documenting.

Variables

Declare variables where you are going to use them, not at the top of the function. It makes it easy to see usage if you can look close to where you are using the variable to see its definition. This becomes a lot more important when you start using objects with constructors (as the constructors can call arbitrator code).

Boolean expressions.

Don't use 0 and 1 when you can use true and false (the latter is much more readable).

Don't use an if condition to set a boolean variable (use the boolean condifiton of the if stement as the result).

bool rdo_ws(char c) {
    if (c != ' ')
        return 0;
    else
        return 1;
}

// or
bool rdo_ws(char c)
{
    return c == ' ';  // return true if it was a space
}

// or better yet use a built-in test for space.
bool rdo_ws(char c)
{
    return std::is_space(c);  // return true if it was a white space
}

Use a default in your switch

If your expression does not match any of the case statments and there is no default then it is undefined behavior. The input may not be legal in your expression but you should detect and report that not go into undefined territory.

char rdo_expr_item_type(char c) {

    switch(c) {
        case '0':
       .....
        case '9':
        case '.':
            c = 'n';
            break;
        case '+':
       ......
        case '/':
            c = 'o';
            break;
        case '(':
        case ')':
            c = 'b';
            break;

        // Whoops no default.
        // potentially very bad.
    }

    return c;
}

OK so we see you are trying for speed here.
So why not just build the result from an array":

char rdo_expr_item_type(char c)
{
     static char const result[] = {
     'e', 'e', ' e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e',
     'e', 'e', ' e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e',
      //  . is 46
      //  * (42) + (43) - (45) / (47)
      //  ( (40) ) (41)
     'e', 'e', ' e', 'e', 'e', 'e', 'e', 'e', 'b', 'b', 'o', 'o', 'e', 'o', 'n', 'o',
      // 0 is 48
     'n', 'n', ' n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'e', 'e', 'e', 'e', 'e', 'e',
     'e', 'e', ' e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e',
     'e', 'e', ' e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e',
     'e', 'e', ' e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e',
     'e', 'e', ' e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e',
     'e', 'e', ' e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e',
     'e', 'e', ' e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e',
     'e', 'e', ' e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e',
     'e', 'e', ' e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e',
     'e', 'e', ' e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e',
     'e', 'e', ' e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e',
     'e', 'e', ' e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e',
     'e', 'e', ' e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e',
                                  };
     return result[static_cast<unisgned char>(c)];
}

Answer 2

Loki Astari already covered a number of good points, which I will not repeat.

Algorithms and data structures

The standard library contains a number of ready-made algorithms and data structures that can make your code easier to read and understand.

For example, you have these lines:

opp_count = 0; // line 393, new lines removed for brevity
for (i = 0; i < rdo_num_stack.size();i++) {        
    if (rdo_num_stack[i] == "+" or rdo_num_stack[i] == "-" or rdo_num_stack[i] == "*" or rdo_num_stack[i] == "/") {
        opp_count++;
    }
}

Instead, you could define a set containing your operator symbols and a function, and then use count_if() included from the <algorithm> header:

// At top level
static const std::set<std::string> operators = {"+", "-", "/", "*"};
bool is_operator(const std::string& s) {
    return operators.find(s) != operators.end();
}

// In function body
opp_count = std::count_if(rdo_num_stack.begin(), rdo_num_stack.end(), is_operator);

Likewise, counting the parentheses in your stack could also be implemented using count_if(), rather than incrementing bcount in your iteration:

bcount = std::count_if(rdo_num_stack.begin(), rdo_num_stack.end(), []
                             (const std::string& value)
                             {
                                 return (value == "(" || value == ")");
                             });

Don't write code that does nothing

You also have written (verbatim):

expr = ""; // line 417 in original

for (i = 0; i < rdo_num_stack.size();i++) {
    expr += rdo_num_stack[i];
}

expr = "";

This assigns the contents of rdo_num_stack to expr, and then immediately overwrites expr. Everything but the last assignment can be removed.

Deep nesting

Deeply nested code is hard to read, and possibly to reason about. Several times you have a construct with a for-loop and nested if conditions:

for (/* loop conditions */) { // summarized from line 134 in original
    if (!condition1) { 
        if (condition2) {
            // Loop body
        } else {
            // report error and quit
        }
    }
}

You can reduce the level of nesting by inverting the conditional logic and breaking early:

for (/* loop conditions */) {
    if (condition1) {continue;}
    if (!condition2) { /* report error and quit*/}
    // Loop body
}