5
\$\begingroup\$

I was in the mood for some C++ and decided to write a command line calculator, which understands addition, subtraction, multiplication and parentheses. See what I have:

main.cpp

#include <algorithm>
#include <cctype>
#include <iostream>
#include <iterator>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <utility>
#include <vector>

using std::cin;
using std::copy;
using std::cout;
using std::endl;
using std::isspace;
using std::ostream_iterator;
using std::pair;
using std::runtime_error;
using std::stack;
using std::string;
using std::stringstream;
using std::vector;

enum class TokenType {
    OPERAND,
    OPERATOR
};

enum class Operator {
    PLUS,
    MINUS,
    MULTIPLY,
    LEFT_PARENTHESIS,
    RIGHT_PARENTHESIS
};


static int get_operator_precedence(Operator _operator)
{
    switch (_operator) {
        case Operator::PLUS:
        case Operator::MINUS:
            return 1;

        case Operator::MULTIPLY:
            return 0;

        default:

            if (_operator == Operator::LEFT_PARENTHESIS)
            {
                throw runtime_error(
                    "Left parenthesis has no precedence assigned to it.");
            }

            if (_operator == Operator::RIGHT_PARENTHESIS)
            {
                throw runtime_error(
                    "Right parenthesis has no precedence assigned to it.");
            }

            throw std::runtime_error(
                    "Unknown operator. This should not happen.");
    }
}

class Token
{
    TokenType m_token_type;
    Operator  m_operator;
    int       m_operand;

public:
    Token(int operand) : m_operand{operand},
                         m_token_type{TokenType::OPERAND} {}

    Token(Operator _operator) : m_operand{0},
                                m_token_type(TokenType::OPERATOR),
                                m_operator{_operator} {}

    TokenType get_token_type() const
    {
        return m_token_type;
    }

    Operator get_operator() const
    {
        return m_operator;
    }

    int get_operand() const
    {
        return m_operand;
    }

    friend std::ostream& operator<<(std::ostream&, const Token&);
};

std::ostream& operator<<(std::ostream& out, const Token& token)
{
    if (token.m_token_type == TokenType::OPERAND)
    {
        out << token.m_operand;
    }
    else
    {
        switch (token.m_operator)
        {
            case Operator::PLUS:
                out << "+";
                break;

            case Operator::MINUS:
                out << "-";
                break;

            case Operator::MULTIPLY:
                out << "*";
                break;

            case Operator::LEFT_PARENTHESIS:
                out << "(";
                break;

            case Operator::RIGHT_PARENTHESIS:
                out << ")";
                break;
        }
    }

    return out;
}

vector<Token> tokenize(const string& expression)
{
    vector<Token> token_vector;
    stringstream number_string_stream;
    bool number_string_stream_empty = true;
    size_t char_index = 0;
    size_t expression_length = expression.length();

    while (char_index < expression_length)
    {
        const char current_char = expression[char_index];

        switch (current_char)
        {
            case '(':

                if (!number_string_stream_empty)
                {
                    int number;
                    number_string_stream >> number;
                    number_string_stream.clear();
                    token_vector.push_back(Token(number));
                    number_string_stream_empty = true;
                }

                token_vector.push_back(Token(Operator::LEFT_PARENTHESIS));
                break;

            case ')':

                if (!number_string_stream_empty)
                {
                    int number;
                    number_string_stream >> number;
                    number_string_stream.clear();
                    token_vector.push_back(Token(number));
                    number_string_stream_empty = true;
                }

                token_vector.push_back(Token(Operator::RIGHT_PARENTHESIS));
                break;

            case '+':

                if (!number_string_stream_empty)
                {
                    int number;
                    number_string_stream >> number;
                    number_string_stream.clear();
                    token_vector.push_back(Token(number));
                    number_string_stream_empty = true;
                }

                token_vector.push_back(Token(Operator::PLUS));
                break;

            case '-':

                if (!number_string_stream_empty)
                {
                    int number;
                    number_string_stream >> number;
                    number_string_stream.clear();
                    token_vector.push_back(Token(number));
                    number_string_stream_empty = true;
                }

                token_vector.push_back(Token(Operator::MINUS));
                break;

            case '*':

                if (!number_string_stream_empty)
                {
                    int number;
                    number_string_stream >> number;
                    number_string_stream.clear();
                    token_vector.push_back(Token(number));
                    number_string_stream_empty = true;
                }

                token_vector.push_back(Token(Operator::MULTIPLY));
                break;

            case '0':
            case '1':
            case '2':
            case '3':
            case '4':
            case '5':
            case '6':
            case '7':
            case '8':
            case '9':

                number_string_stream_empty = false;
                number_string_stream << current_char;
                break;

            default:
                if (!isspace(current_char))
                {
                    stringstream err_msg;

                    err_msg << "Bad character: '"
                            << current_char
                            << "' at index "
                            << char_index
                            << "!";

                    throw runtime_error(err_msg.str());
                }
        }

        ++char_index;
    }

    if (!number_string_stream_empty)
    {
        int operand;
        number_string_stream >> operand;
        token_vector.push_back(Token(operand));
    }

    return token_vector;
}

vector<Token> shunting_yard_algorithm(const vector<Token>& token_vector)
{
    vector<Token> postfix_token_vector;
    stack<Token> operator_stack;

    for (const Token& token : token_vector)
    {
        if (token.get_token_type() == TokenType::OPERAND)
        {
            postfix_token_vector.push_back(token);
        }
        else if (token.get_operator() == Operator::LEFT_PARENTHESIS)
        {
            operator_stack.push(token);
        }
        else if (token.get_operator() == Operator::RIGHT_PARENTHESIS)
        {
            while (!operator_stack.empty()
                   && operator_stack.top().get_operator()
                   != Operator::LEFT_PARENTHESIS)
            {
                postfix_token_vector.push_back(operator_stack.top());
                operator_stack.pop();
            }

            if (operator_stack.empty()
                || operator_stack.top().get_operator()
                        != Operator::LEFT_PARENTHESIS)
            {
                throw runtime_error("The parentheses are invalid.");
            }
            else
            {
                operator_stack.pop();
            }
        }
        else
        {
            while (!operator_stack.empty()
                   && operator_stack.top().get_operator()
                        != Operator::LEFT_PARENTHESIS
                   && get_operator_precedence(
                        operator_stack.top().get_operator()) <
                        get_operator_precedence(token.get_operator()))
            {
                postfix_token_vector.push_back(operator_stack.top());
                operator_stack.pop();
            }

            operator_stack.push(token);
        }

    }

    while (!operator_stack.empty())
    {
        postfix_token_vector.push_back(operator_stack.top());
        operator_stack.pop();
    }

    return postfix_token_vector;
}

pair<int, vector<Token>> coderodde_evaluate(const string& expression)
{
    vector<Token> infix_token_vector = tokenize(expression);
    vector<Token> postfix_token_vector =
        shunting_yard_algorithm(infix_token_vector);

    stack<Token> _stack;

    for (const Token& token : postfix_token_vector)
    {
        if (token.get_token_type() == TokenType::OPERATOR
            && token.get_operator() == Operator::LEFT_PARENTHESIS)
        {
            throw runtime_error(
                "The parentheses are invalid.");
        }

        if (token.get_token_type() == TokenType::OPERAND)
        {
            _stack.push(token.get_operand());
        }
        else
        {
            if (_stack.size() < 2)
            {
                throw runtime_error("The parentheses are invalid.");
            }

            int operand2 = _stack.top().get_operand(); _stack.pop();
            int operand1 = _stack.top().get_operand(); _stack.pop();

            switch (token.get_operator())
            {
                case Operator::PLUS:
                    _stack.push(Token(operand1 + operand2));
                    break;

                case Operator::MINUS:
                    _stack.push(Token(operand1 - operand2));
                    break;

                case Operator::MULTIPLY:
                    _stack.push(Token(operand1 * operand2));
                    break;
            }
        }
    }

    if (_stack.size() != 1)
    {
        throw runtime_error("The parentheses are invalid.");
    }

    return make_pair(_stack.top().get_operand(), postfix_token_vector);
}

int main()
{
    string expr;

    while (true)
    {
        cout << "> ";
        getline(cin, expr);

        if (expr == "quit")
        {
            break;
        }

        try {
            pair<int, vector<Token>> data = coderodde_evaluate(expr);
            cout << "Value: " << data.first << ", postfix notation: ";

            copy(data.second.cbegin(),
                 data.second.cend(),
                 ostream_iterator<Token>(cout, " "));

            cout << endl;
        }
        catch (runtime_error& err)
        {
            cout << "ERROR: " << err.what() << endl;
        }
    }
}

Critique request

Am I doing good C++ here? Please tell me anything that comes to mind.

\$\endgroup\$
3
  • \$\begingroup\$ Cases 1, 2, ..., 9 may be simplified \$\endgroup\$ Commented Jul 23, 2016 at 12:42
  • \$\begingroup\$ Title should possibly include whether it is a prefix, infix or postfix calculator. \$\endgroup\$ Commented Jul 23, 2016 at 13:51
  • 1
    \$\begingroup\$ @pacmaninbw Thank you for your input. I made the title more explicit. \$\endgroup\$ Commented Jul 23, 2016 at 13:52

3 Answers 3

Reset to default
4
\$\begingroup\$

Quite nice. A couple of small things:

  • you can use emplace_back instead of push_back when adding Tokens. Likewise for the stack with emplace instead of push
  • for the sake of symetry, do out << 'c' instead of out << "c"
  • check your IO: your mainloop should be while (getline(cin, expr)) { ... } to detect EOF
  • don't use _variable for names.
\$\endgroup\$
1
  • \$\begingroup\$ So emplace_back will move the object instead of copy-constructing it? \$\endgroup\$ Commented Jul 24, 2016 at 14:10
2
\$\begingroup\$

This suggestion probably won't make the code look more like C++.

Parsing, tokenizing input is very cumbersome job. It has a lot of edge cases. When possible, very high quality library should be deployed. It might be overkill, but one of them is boost.spirit family of libraries. It is based on expression templates.

You're using too much. The only case you should write using is switch statement, which is done to let the compiler choose appropriate function overload. Just write std:: where it should be written.

Don't use m_ prefixes. They are artifacts of the past. Good reason to enrich vocabulary (but don't write too sophisticated words so other people could understand ).

\$\endgroup\$
2
\$\begingroup\$

Descriptive function names

It's kind of weird to name your parsing after yourself coderodde_evaluate. It suggests it's evaluating you (unless coderodde has some meaning I don't know about). I'd prefer a name that describes what the function actually does. If you want to package your stuff, think about using namespaces instead.

The parentheses are invalid.

You throw runtime errors with the string same string 'The parentheses are invalid.' 4 times in your code. This suggests that maybe it should be defined as a constant. It's also, somewhat confusing to the user:

> 1*
ERROR: The parentheses are invalid.
> *
ERROR: The parentheses are invalid.
>
ERROR: The parentheses are invalid.

I haven't used any parentheses...

Overflow checking

You don't limit the size of the input stream, so it's possible to overflow the input:

> 11111111111111111111
Value: -858993460, postfix notation: -858993460

Spaces

This is probably subjective, but I find it odd that you allow spaces between numbers:

> 2*(2 1 3 4 5 6 7)
Value: 4269134, postfix notation: 2 2134567 *

Enum Values

Again, somewhat subjective, but I'd be tempted to assign values to your operator enum like:

enum class Operator {
    PLUS='+',
    MINUS='-',
    MULTIPLY='*',
    LEFT_PARENTHESIS='(',
    RIGHT_PARENTHESIS=')'
};

That way the value of the enum is actually linked to the character it represents. This makes it possible for your operator<< to become:

std::ostream& operator<<(std::ostream& out, const Token& token)
{
    if (token.m_token_type == TokenType::OPERAND)
    {
        out << token.m_operand;
    }
    else
    {
        out << static_cast<char>(token.m_operator);
    }
    return out;
}
\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.