Optimize shunting-yard algorithm

Question

Following your suggestions, I updated my expression evaluator with a Shunting-Yard algorithm.

I've created two classes, a Shunting-yard class and a RPNsolver class.

The first I mentioned converts from infix to postfix notation and the other solves the postfix expression.

I'm open to suggestions of any type.

Shunting_yard.h

#pragma once

#include <string>
#include <stack>
#include <map>
#include <iostream>
#include <sstream>



class Shunting_yard
{
private:
    std::string infix;
    std::map<char, std::pair<int, bool>> op //Operators features(precedence, right associative)
    {
        { '+', std::make_pair(2,  0) },
        { '-', std::make_pair(2,  0) },
        { '*', std::make_pair(3,  0) },
        { '/', std::make_pair(3,  0) },
        { '^', std::make_pair(4,  1) }
    };

    bool isoperator(char);
public:
    Shunting_yard(std::string );
    void convert();

    std::string postfix;
};

Shunting_yard.cpp

#include "Shunting_yard.h"

Shunting_yard::Shunting_yard(std::string str)
{
    this->infix = str;
}

bool Shunting_yard::isoperator(char c)
{
    return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
}

void Shunting_yard::convert()
{
    std::stack<char> operators;
    std::istringstream iss(infix);
    char tmp;
    double num;

    while ((int)iss.tellg() != EOF)
    {
        char token = iss.peek();
        if (isdigit(token))
        {
            iss >> num;
            std::stringstream ss;
            ss << num; 
            postfix += ss.str();
            postfix += " ";
        }
        else if (isoperator(token))
        {
            char o1 = token;
            bool offset = 0;
            if (!op[o1].second)
                offset = 1;
            if (!operators.empty())
            {
                char top = operators.top();
                while (isoperator(top))
                {
                    if (op[o1].first < op[top].first+offset)
                    {
                        postfix += top;
                        postfix += " ";
                        operators.pop();
                    }
                    else break;
                    if (operators.empty())
                        break;
                    else top = operators.top();
                }
            }
            operators.push(o1);
            iss >> tmp;
        }
        else if (token == '(')
        {
            operators.push(token);
            iss >> tmp;
        }
        else if (token == ')')
        {
            while (operators.top() != '(')
            {
                postfix += operators.top();
                postfix += " ";
                operators.pop();
            }
            operators.pop();
            iss >> tmp;
        }
        else iss.get(tmp);
    }
    if (!operators.empty())
    {
        int size = operators.size();
        for (int i = 0; i < size; i++)
        {
            postfix += operators.top();
            postfix += " ";
            operators.pop();
        }
    }
}

RPNSolver.h

#include "Shunting_yard.h"
#include <string>
#include <stack>
#include <map>
#include <iostream>
#include <sstream>

class RPNSolver
{
private:
    std::string postfix;

    bool isOperator(char);
public:
    double result;

    RPNSolver(std::string str);
    void solve();
};

RPNSolver.cpp

#include "Solver.h"

RPNSolver::RPNSolver(std::string str)
{
    Shunting_yard exp(str);
    exp.convert();
    this->postfix = exp.postfix;
}

bool RPNSolver::isOperator(char c)
{
    return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
}


void RPNSolver::solve()
{
    std::istringstream iss(postfix);
    std::stack<double> nums;
    double num;
    char tmp;
    double res;

    while ((int)iss.tellg() != EOF)
    {
        char token = iss.peek();
        if (isdigit(token))
        {
            iss >> num;
            nums.push(num);
        }
        else if (isOperator(token))
        {
            double num2 = nums.top();
            nums.pop();
            double num1 = 0;
            if (!nums.empty())
            {
                num1 = nums.top();
                nums.pop();
            }
            if (token == '+' || token == '-')
            {
                if (token == '-')
                    num2 *= -1;
                res = num1 + num2;
            }
            else if (token == '*' || token == '/')
            {
                if (token == '/')
                    num2 = 1/num2;
                res = num1 * num2;
            }
            else if (token == '^')
            {
                res = pow(num1, num2);
            }
            nums.push(res);
            iss >> tmp;
        }
        else iss.get(tmp);
    }
    result = nums.top();
}

Answer 1

This already looks really nice, however it seems there are some minor typos etc.

1. Sort includes alphabetically. That way it is much easier to see whether one is missing.

2. You should make postfix private and add a getter for it

3. You might want to contify and pass per reference the input string.

4. It would not really affect performance but you can simplify your isoperator by utilizing op.find(c) != op.end()

5. Your isdigit function is missing, but you can take the standard one from cctype

6. Your digit is from a single char, why are you putting it into a double? int would be mor approriate. Also you can utilize std::to_string

7. Never mingle single line if/else with other ones. That completely demolishes the readability of your code.

8. The for loop at the end is unnecessary. Just make a while as long as operators is nonempty.

This gets me to the following

Shunting_yard.h

#pragma once

#include <cctype>
#include <iostream>
#include <map>
#include <sstream>
#include <stack>
#include <string>

class Shunting_yard
{
private:
    const std::string infix;
    std::string postfix;

    std::map<char, std::pair<int, bool>> op //Operators features(precedence, right associative)
    {
        { '+', std::make_pair(2,  0) },
        { '-', std::make_pair(2,  0) },
        { '*', std::make_pair(3,  0) },
        { '/', std::make_pair(3,  0) },
        { '^', std::make_pair(4,  1) }
    };

    bool isoperator(char) const;
public:
    Shunting_yard(const std::string& input);

    const std::string& getPostfix() const;

    void convert();    
};

Shunting_yard.cpp

#include "Shunting_yard.h"

Shunting_yard::Shunting_yard(const std::string& input)
    : infix(input) {}

bool Shunting_yard::isoperator(char c) const
{
    return op.find(c) != op.end();
}

void Shunting_yard::convert()
{
    std::stack<char> operators;
    std::istringstream iss(infix);
    char tmp;
    int num;

    while ((int)iss.tellg() != EOF)
    {
        char token = iss.peek();
        if (std::isdigit(token))
        {
            iss >> num;
            postfix += std::to_string(num);
            postfix += " ";
        }
        else if (isoperator(token))
        {
            char o1 = token;
            bool offset = 0;
            if (!op[o1].second)
                offset = 1;
            if (!operators.empty())
            {
                char top = operators.top();
                while (isoperator(top))
                {
                    if (op[o1].first < op[top].first+offset)
                    {
                        postfix += top;
                        postfix += " ";
                        operators.pop();
                    }
                    else 
                        break;
                    if (operators.empty())
                        break;
                    else 
                        top = operators.top();
                }
            }
            operators.push(o1);
            iss >> tmp;
        }
        else if (token == '(')
        {
            operators.push(token);
            iss >> tmp;
        }
        else if (token == ')')
        {
            while (operators.top() != '(')
            {
                postfix += operators.top();
                postfix += " ";
                operators.pop();
            }
            operators.pop();
            iss >> tmp;
        }
        else iss.get(tmp);
    }
    while (!operators.empty()) {
        postfix += operators.top();
        postfix += " ";
        operators.pop();
    }
}

So much for shunting yard, i might get back to RPN later

Answer 2

You could even write the pairs using universal initialization:

// old code
{ '+', std::make_pair(2,  0) },

// new code
{ '+', { 2, 0 } },

Some of the if-else chains can be improved in terms of efficiency and readability:

        // old code
        if (token == '+' || token == '-')
        {
            if (token == '-')
                num2 *= -1;
            res = num1 + num2;
        }
        else if (token == '*' || token == '/')
        {
            if (token == '/')
                num2 = 1/num2;
            res = num1 * num2;
        }
        else if (token == '^')
        {
            res = pow(num1, num2);
        }

The code gets clearer and faster by using a switch statement and handling each operator individually:

        // new code
        switch (token)
        {
        case '+': res = num1 + num2; break;
        case '-': res = num1 - num2; break;
        case '*': res = num1 * num2; break;
        case '/': res = num1 / num2; break;
        case '^': res = pow(num1, num2); break;
        }