Shunting_yard algorithm

shunting_yard.cpp

/* while there are tokens to be read:
    read a token.
    if the token is a number, then push it to the output queue.
    if the token is an operator, then:
        while ((there is an operator at the top of the operator stack with
            greater precedence) or (the operator at the top of the operator stack has
                        equal precedence and
                        the operator is left associative)) and
                      (the operator at the top of the stack is not a left bracket):
                pop operators from the operator stack, onto the output queue.
        push the read operator onto the operator stack.
    if the token is a left bracket (i.e. "("), then:
        push it onto the operator stack.
    if the token is a right bracket (i.e. ")"), then:
        while the operator at the top of the operator stack is not a left bracket:
            pop operators from the operator stack onto the output queue.
        pop the left bracket from the stack.
         if the stack runs out without finding a left bracket, then there are
        mismatched parentheses.
if there are no more tokens to read:
    while there are still operator tokens on the stack:
         if the operator token on the top of the stack is a bracket, then
        there are mismatched parentheses. 
        pop the operator onto the output queue.
exit.*/

#include <algorithm>
#include <cctype>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

namespace Calculator {
 
/* This Function returns the precedence of a given operator.
 * Positive values are left-associative and negative are right-associative */
inline const short precedence(const string& op) noexcept
{
    static unordered_map<string,const short> table {{"+", 1}, 
                                                    {"-", 1},
                                                    {"*", 2},
                                                    {"/", 2},
                                                    {"%", 2},
                                                    {"^",-4}};
                                              
    return table[op];
}

/* This function compares the precedence of 2 operators */
inline bool has_precedence(const string& op1, const string& op2) noexcept
{
    return abs(precedence(op1)) > abs(precedence(op2));
}

/* This function checks if an operator is right-associative */
inline bool is_right_associative(const string& op) noexcept
{
    return precedence(op) < 0;
}

/* This funciton checks if a given string is a number.
 * It compares only the first digits. But afterwards the conversion
 * with std::stod can throw, so that is not a problem */
inline bool is_number(const string& s) noexcept
{
    size_t sz = s.size();
    
    if (sz == 1 && isdigit(s[0])) return true;
    else if (sz > 1 && isdigit(s[1])) return true;
    else if (sz > 2 && isdigit(s[2])) return true;
    
    return false;
}

/* This function performs the appropriate calculation */
double do_arithmetic(double num1, double num2, const string& op)
{
    // unfortunately we cannot switch a string, so use if...else
    if (op == "+") {return num1 + num2;}
    else if (op == "-") {return num1 - num2;}
    else if (op == "*") {return num1 * num2;}
    else if (op == "/") {return num1 / num2;}
    else if (op == "%") {return static_cast<long>(num1) % static_cast<long>(num2);}
    else if (op == "^") {return pow(num1, num2);}
    else {throw invalid_argument("Invalid operator");}
}

/* This function takes the appropriate values and opperators from stack and
 * calls do_arithmetic and push the result back*/
void perform_operation(stack<double>& val, stack<string>& op)
{
    double num1, num2, tmpRes;
    
    if (val.size() > 1) {
        num2 = val.top();
        val.pop();
        num1 = val.top();
        val.pop();
    } else throw invalid_argument("Ill-formed expression");
    
    if (!op.empty()) {
        tmpRes = do_arithmetic(num1, num2, op.top());
        op.pop();
    } else throw invalid_argument("Ill-formed expression");
    
    
    val.push(tmpRes);
}

/* This function splits the string into tokens, while performing checks for
 * balanced parenthesis and unary operators + and - */
vector<string> lexer_tokenize(string s)
{
    // remove white space
    s.erase(remove_if(begin(s), 
                      end(s), 
                      [](unsigned char c){return isspace(c);}), 
            end(s));
    
    if (s.size() == 0) throw invalid_argument("Empty string");
    
    vector<string> res; // hold results
    res.reserve(s.size());
    
    int l_count = 0, r_count = 0; // for parenthesis balance count
    
    auto pos = s.find_first_not_of("0123456789,.");
    
    while (pos != string::npos) {
        if (pos >= 1) { // its a number
            res.push_back(s.substr(0, pos));
            s.erase(0, pos);
        }
        else { // its an operator
            // handle unary '+' and '-'
            if ((s[0] == '+' || s[0] == '-') &&
                (res.size() == 0  || precedence(res.back()) != 0)) {
                    auto pos2 = s.find_first_not_of("0123456789,.", pos+1);
                    res.push_back(s.substr(0, pos2));
                    s.erase(0, pos2);
            }
            else { // else count brackets and push_back the operator
                if (s[0] == '(') l_count++;
                if (s[0] == ')') r_count++;
                
                res.push_back(s.substr(0, 1));
                s.erase(0, 1);   
            }
                     
        }
        
        pos = s.find_first_not_of("0123456789,.");
    }
    
    if (s.size() > 0) {res.push_back(s);}
    res.shrink_to_fit();
    
    if (r_count != l_count) throw invalid_argument("Unbalanced parenthesis");
    
    return res;
}

/* This function evaluates the expression using Shunting-Yard algorithm */
double evaluate_expression(const string& expression)
{
    // get tokens and check 
    auto tokens = lexer_tokenize(expression);
    
    for (auto& t: tokens) cout << t << endl; // Debug tokens
    
    stack<double> val;
    stack<string> op;
    
    static auto is_suitable = [&op](const string& t){
        return !op.empty() &&
               (has_precedence(op.top(), t) || 
               (precedence(op.top()) == precedence(t) && !is_right_associative(op.top())));
    };
    
    for (auto& t: tokens) {
        if (is_number(t)) {
            val.push(stod(t));
        }
        else {
            if (t == "(") {
                op.push(t);
            }
            else if (t == ")") {
                while (!op.empty() && op.top() != "(") {
                    perform_operation(val, op);
                }
                op.pop(); // remove remaining parenthesis
            }
            else {
                if (precedence(t) == 0) throw invalid_argument("Invalid operator");
                
                while (is_suitable(t)) {
                    perform_operation(val, op);
                }
                op.push(t);
            }
        }
    }
    
    while(!op.empty()){
        perform_operation(val,op);
    }
    
    return val.top();
}

} // end of namespace calculator


/* Mainloop */
int main()
{
    string input {};
    
    while (true) {
        cout << "Enter expression: ";
        getline(cin, input);
        if (input == "exit") {break;}
        if (!cin.good()) {break;}
        
        try {
            double result = Calculator::evaluate_expression(input);
            cout << "Result: " << setprecision(15) << result << endl;
        }
        catch (invalid_argument& e) {
            cout << "Invalid expression: " << e.what() << endl;
        }
    }
    
    return 0;
}