Prefix expression evaluator [C++] [closed]

Question

Here's my code for this' weeks homework I had. The code should take an expression , preferably in prefix notation ( otherwise throws exception ), that evaluate prefix expression. I've given three example in the main function. The expression gets saved in the object at the mText variable type of string and then the function 'evaluate' evaluates the expression.

The code works fine as said by my professor, but he highly criticized my poor style of writing.

I'm interested in your opinion and what exactly should I be working on in the future ? I'm pretty sure my biggest mistake is writing bunch of code in one line instead of separating it in a several lines.

The code:

#include <iostream>
#include <string>
#include <stdexcept>
#include <cctype>
#include <sstream>
#include <limits>
#include <cmath>

using namespace std;

class Expression{
public:
    using Value=int;
    enum TokenType {operand,unaryOp,binaryOp};

    struct Token{
        TokenType tokentype;
        char sym;
        Value val;
        bool start;
        TokenType type() const { return tokentype; }
        char symbol() const { return sym; }
        Value value() const { return val; }
    };

    Expression(){}
    Expression(string text);
    Value evaluate();
    string getText() { return mText; }
private:
    static string valid,whites;
    string mText;
    size_t processed_size=0;
    Token mnextToken;
    Token getToken();
};


Expression::Expression(string text) : mText{text} {}
string Expression::valid="+*/-^~0123456789";
string Expression::whites=" \t\v\n";

Expression::Value solve(Expression::Value a, Expression::Value b,char symbol){
    long long num1=a,num2=b;
    switch (symbol){
        case '+': return !(abs(num1+num2) > numeric_limits<int>::max()) ? a+b : throw runtime_error("Wrong expression [Two big(or low) numbers generated for the type int].");
        case '-': return !(abs(num1-num2) > numeric_limits<int>::max()) ? a-b : throw runtime_error("Wrong expression [Two big(or low) numbers generated for the type int].");
        case '*': return !(abs(num1*num2) > numeric_limits<int>::max()) ? a*b : throw runtime_error("Wrong expression [Two big(or low) numbers generated for the type int].");
        case '/': return !b ? a/b : throw runtime_error("Wrong expression [dividing with 0].");
        case '^': { auto b_th_power_of = [num2] (long long x) mutable { if (!num2) return static_cast<long long>(1);
                                                                        if (num2<0) return static_cast<long long>(0); long long temp=1;
                                                                        while (num2-->0) temp*=x;
                                                                        return temp; };
                    num2=b_th_power_of(num1);
                    return !(abs(num2) > numeric_limits<int>::max()) ? num2 : throw runtime_error("Wrong expression [Two big(or low) numbers generated for the type int]."); }
        default: throw runtime_error("Undefined error occured."); //Za svaki slucaj
    }
}

Expression::Value Expression::evaluate(){
    Token t=getToken();
    if (t.type()==unaryOp){
        Value a=evaluate();
        if (t.start && mText.find_first_not_of(Expression::whites,processed_size)!=string::npos) throw runtime_error("Wrong expression [Too many characters on the right side]");
        return a-(2*a);
    }
    else if(t.type() == binaryOp){
        Value a=evaluate();
        Value b=evaluate();
        if (t.start && mText.find_first_not_of(Expression::whites,processed_size)!=string::npos) throw runtime_error("Wrong expression [Too many characters on the right side].");
        return solve(a,b,t.symbol());
    }
    else{
        return t.value();
    }


}

Expression::Token Expression::getToken(){
    processed_size ? mnextToken.start=false : mnextToken.start=true;
    if (static_cast<int>(processed_size) > static_cast<int>(mText.length())-1 ) throw runtime_error("Wrong expression [Too many operators on the left side or empty expression]."); // Fali mi u dz
    while (Expression::whites.find( mText.at(processed_size) ) != string::npos){
        ++processed_size;
        if (processed_size > mText.length()-1) throw runtime_error("Wrong expression [Too many operators on the left side].");
    }

    size_t found=Expression::valid.find(mText[processed_size]);

    if (found < 5){
        mnextToken.sym=mText[processed_size++];
        mnextToken.tokentype=binaryOp;
    }
    else if (found == 5){
        ++processed_size;
        mnextToken.tokentype=unaryOp;
    }
    else if (found < 16 && found > 5){
        if (mnextToken.start) throw runtime_error("Wrong expression [Expression shouldn't start with a number].");
        Expression::Value number;
        stringstream buffer;
        while (isdigit( mText[processed_size] )){ buffer << mText[processed_size]; processed_size++; }
        if ( !(buffer >> number) ) throw runtime_error("Wrong expression [Too large number(s) in the expression].");
        mnextToken.val=number;
        mnextToken.tokentype=operand;
    }
    else throw runtime_error("Wrong expression [Invalid symbol inside the expression].");

    return mnextToken;
}


int main()
{
    try{
        Expression a1("+ 2 3");
        cout << a1.getText() << " = " << a1.evaluate() << " [Correct result: 5]" << endl;

        Expression a2(" *  4 ^ 2++2 3 1 ");
        cout << a2.getText() << " = " << a2.evaluate() << " [Correct result: 256]" << endl;

        Expression a3("-+*2 3 *5 4 9");
        cout << a3.getText() << " = " << a3.evaluate() << " [Correct result: 17]" << endl;

    } catch (const exception& ex){ cout << "Exception: " << ex.what() << endl; }
    return 0;
}

Just to mention that I was supposed to work with runtime_error exception as that was the part of the homework.

Answer 1

The Good

In the class Expression you put the public interfaces first and then the private variables even though when C++ defaults the section immediately following class CLASSNAME { to private. This is very helpful for programmers that may have to maintain your code and can be considered a best practice.

You use an enum to indicate the token type.

Avoid using namespace std;

If you are coding professionally you probably should get out of the habit of using the using namespace std; statement. The code will more clearly define where cout and other identifiers are coming from (std::cin, std::cout, std::string). As you start using namespaces in your code it is better to identify where each function comes from because there may be function name collisions from different namespaces. The identifiercout you may override within your own classes, and you may override the operator << in your own classes as well. This stack overflow question discusses this in more detail.

Symbolic Constants

You have 2 static variables static string valid,whites; in the class Expression, it might be better to create these as const and initialize them in the class rather than initializing them almost as globals.

class Expression{
    ...
private:
    const std::string valid = "+*/-^~0123456789";
    const std::string whites = " \t\v\n";
    ...
};

There are Magic Numbers in the Expression::Token Expression::getToken() function (5), it might be better to create symbolic constants for them to make the code more readable and easier to maintain. These numbers may be used in many places and being able to change them by editing only one line makes maintainence easier.

Numeric constants in code are sometimes referred to as Magic Numbers, because there is no obvious meaning for them. There is a discussion of this on stackoverflow.

Horizontal and Vertical Spacing

It is common to put spaces between operands and operators in expressions. This makes the code more readable and easier to maintain by yourself or others.

                    while (num2-- > 0)

This includes the comma operator in function definitions and function calls.

Expression::Value solve(Expression::Value a, Expression::Value b, char symbol){

As @slepic noted, long lines may make the code less readable.

Here is a more readable version of the function solve():

Expression::Value solve(Expression::Value a, Expression::Value b, char symbol){
    long long num1=a,num2=b;
    switch (symbol){
        case '+':
            return !(abs(num1+num2) > std::numeric_limits<int>::max()) ?
                a + b :
                throw std::runtime_error("Wrong expression [Two big(or low) numbers generated for the type int].");

        case '-':
            return !(abs(num1-num2) > std::numeric_limits<int>::max()) ?
                a - b :
                throw std::runtime_error("Wrong expression [Two big(or low) numbers generated for the type int].");

        case '*':
            return !(abs(num1*num2) > std::numeric_limits<int>::max()) ?
                a * b :
                throw std::runtime_error("Wrong expression [Two big(or low) numbers generated for the type int].");

        case '/':
            return !b ?
                a / b :
                throw std::runtime_error("Wrong expression [dividing with 0].");

        case '^':
            {
                auto b_th_power_of = [num2] (long long x) mutable
                {
                    if (!num2) return static_cast<long long>(1);
                    if (num2 < 0) return static_cast<long long>(0); long long temp=1;
                    while (num2-- > 0)
                    {
                        temp *= x;
                    }
                    return temp;
                };
                num2 = b_th_power_of(num1);
                return !(abs(num2) > std::numeric_limits<int>::max()) ?
                num2 :
                    throw std::runtime_error("Wrong expression [Two big(or low) numbers generated for the type int].");
            }
        default: throw std::runtime_error("Undefined error occured."); //Za svaki slucaj
    }
}

*Note: It is common to put the opening brace { of a function on the next line so that it lines up with the closing brace }. This makes it easier to read and follow the logic. *

Testing the Code

A good practice in testing is to include failures to make sure the failure handling code executes as well as the other code. Has the exception handling been tested?

Separate Classes From Other Code

If this was a more complicated problem with multiple classes this would be more noticeable, but classes should be define in other files from main. Amoung other things this allows the classes to be reused. The class Expression should have a header file Expression.h and an implementation file Expression.cpp. Most modern editors will do this for you if you indicate you want to create a new class. This also decreases the amount of code in any single file, and allows classes to be mainted separately from other code. As long as the class header file is not touched, bugs can be fixed in the class implementation file. This also reduces the number of include files any single implementation file needs to include (improves build times).

Extend Ability

The function Expression::Value Expression::evaluate() is not as extendable as it could be, the if then else if logic could be replaced by a switch / case statement. This would allow the TokenType enum to be extended if necessary. An alternate implementation would be to use std::map and a function for each `TokenType. The map would be identified by the enum and then execute the function.

Expression::Value Expression::evaluate(){
    Token t=getToken();
    switch (t.type())
    {
        case unaryOp:
        {
            Value a=evaluate();
            if (t.start && mText.find_first_not_of(whites, processed_size) != std::string::npos)
            {
                throw std::runtime_error("Wrong expression [Too many characters on the right side]");
            }
            return a - (2 * a);
        }
        case binaryOp :
        {
            Value a=evaluate();
            Value b=evaluate();
            if (t.start && mText.find_first_not_of(whites, processed_size) != std::string::npos)
            {
                throw std::runtime_error("Wrong expression [Too many characters on the right side].");
            }
            return solve(a,b, t.symbol());
        }
        case operand :
            return t.value();
    }
}

Answer 2

Your professor is correct. This is really hard to read, and is structured somewhat oddly.

Here is an assortment of comments, left mostly in the order from top to bottom as I found them.

1. Don't using namespace std;. This has been discussed at length on this site and elsewhere, so I'm not going to leave any additional context here.
2. Expression::Value is a bit weird; if this is important you should make Expression<T>. The name ValueType is probably better too.
3. You should take strings by reference when they're parameters.
4. Your list of whitespace seems incomplete
5. I don't love declaring multiple variables per line
6. The general idea !(abs(expr) > numeric_limits<int>::max()) ? expr : throw runtime_error should be encapsulated in a helper function, and not done in a ternary expression
7. I don't see a good reason why exponentiation needs an anonymous function
8. All your magic numbers (I think they're string indices?) should be well named constants so it can be understood
9. A few of your while loops could probably be for loops
10. It might be nice to implement operator<<
11. Most of your member functions should be const
12. The getter methods on Token are pointless and should be removed
13. Token and TokenType don't seem like they should be public.