Failing to parse different math operators Code Answer

Hello Developer, Hope you guys are doing great. Today at Tutorial Guruji Official website, we are sharing the answer of Failing to parse different math operators without wasting too much if your time.

The question is published on by Tutorial Guruji team.

This question is a follow-up from this one. Basically I’m trying to make a parser which calculates the total result of a string. 5+5+3*2/1 should give 16. This already works for strings only containing plusses and mins, so -55-44+1-2+123-54442+327737+1-2 successfully gives 273317.

It however does not work when plusses/mins get mixed with times/divides. So 1*2-2*3 returns 6 instead of -4. I think this is because I try to respect the order in which math needs to be executed (first plusses and mins, than times and division), but the operator somehow doesn’t get updated.

#include <iostream>
#include <string>
#include <algorithm>

//Enumeration of all the possible
//math operators
enum Operator {
    PLUS,
    MIN,
    TIMES,
    DIVIDE,
    UNDEFINED
};




/************************IGNORE********************/
    char operatorToChar(Operator o) {
        switch(o) {
            case Operator::PLUS:
                return '+';
                break;
            case Operator::MIN:
                return '-';
                break;
            case Operator::TIMES:
                return '*';
                break;
            case Operator::DIVIDE:
                return '/';
                break;
            default:
                return '0';
                break;
        }
    }
/***************************************************/

/*
 * Function to check if there are still times- or divide-operators in the action string.
 * This to respect the order of math (first times and divides, than plusses and mins)
 *
 * :param action: The action string
 * :return bool: Returns true if a '*' or '/' is found
 */
bool timesAndDividesGone(std::string& action) {
    for (char& c : action) {
        if (c == '*' || c == '/') {
            return false;
        }
    }

    return true;
}


/*
 * Function to convert char to Operator
 * :param c: One of the following '+', '-', '*', '/'
 * :return Operator: Operating matching the character
 */
Operator charToOperator(char c) {
    switch(c) {
        case '+':
            return Operator::PLUS;
            break;
        case '-':
            return Operator::MIN;
            break;
        case '*':
            return Operator::TIMES;
            break;
        case '/':
            return Operator::DIVIDE;
            break;
        default:
            return Operator::UNDEFINED;
            break;
    }
}

/*
 * Function to do maths on two numbers, the math to do is decided by the operator
 * :param x: First number
 * :param y: Second number
 * :param o: Operator (Plus, Min, Times or Divide) 
 * :return double: Result of the calculation
 *
 * Example:
 * math(5, 5, Operator::Plus) == 10
 *
 */
double math(double x, double y, Operator o) {
    double z = 0;

    switch (o) {
        case Operator::PLUS:
            z = x + y;
            break;
        case Operator::MIN:
            z = x - y;
            break;
        case Operator::TIMES:
            z = x * y;
            break;
        case Operator::DIVIDE:
            z = x / y;
            break;
    }

    return z;
}

/*
 * Recursive function performing all the calculations from an action string.
 * For example, if the string actions has value "5+7" in the first recursive run
 * result should contain 12 after the last recursion.
 *
 * :param result: Double containing the calculated result after the last recursion
 * :param actions: Action string (what you type in your calculator; e.g: 5+5). We analyze the first character of this string each time and add it to first_nr, second_nr, or make it the operator. First character gets deleted after each recursion
 * :param first_nr: Empty at first recursion, number of left side of the operator. So in 55+77 this paramater will be "55". Gets resetted at the next operator
 * :param second_nr: Idem as first_nr but for the right side of the operator.
 * :param oper: Operation to calculate the first_nr and second_nr
 */
double calculate(double& result, std::string& actions, std::string& first_nr, std::string& second_nr, Operator& oper) {


    //DEBUG OUTPUT:
    std::cout << actions << " Gives ";
    std::cout << std::to_string(result) << std::endl;


    //Base-condition:
    //If action string is empty return 
    if (actions == "") {

        //Scenario for when first action is an operator
        //e.g: 1+1-
        if (second_nr == "")
            second_nr = "0";

        //Update result
        result = math(std::stod(first_nr), std::stod(second_nr), oper);

        return result;
    }



    //Get first character from action string
    char c = actions[0];

    //Making sure order of math is respected (first times and divdes)
    //and than plus and min
    char operatorInChar[4] = {'*', '/'};
    if (timesAndDividesGone(actions)) {
        operatorInChar[2] = '+';
        operatorInChar[3] = '-';
    }

    //If first character is an operator
    if (std::find(std::begin(operatorInChar), std::end(operatorInChar), c) != std::end(operatorInChar)) {

        //Scenario for when first action is an operator
        //e.g: -1+1
        if (first_nr == "") {
            if (actions[1] == '*')
                first_nr = "1";
            else
                first_nr = "0";
        }

        //If operator is not yet set in a previous recursion
        if (oper == Operator::UNDEFINED) {
            oper = charToOperator(c);

            //If second_nr is not empty, we need to calculate the two numbers together
            if (second_nr != "") {
                //Update result
                result = math(std::stod(first_nr), std::stod(second_nr), oper);
            } 
        } else {
            //Update result
            result = math(std::stod(first_nr), std::stod(second_nr), oper);

            first_nr = std::to_string(result);
            second_nr = "";

            //Remove first character from action string because it's analysed in this recursion
            actions = actions.erase(0, 1);
            oper = charToOperator(c);
            return calculate(result, actions, first_nr, second_nr, oper);

        }

    } else {
        //If the character is not a operator but a number we append it to the correct nr
        //we add to first_nr if the operator is not yet set, if we already encountered an operator
        //we add to second_nr.
        //e.g: actions = "123+789"

        if (oper == Operator::UNDEFINED) {
            first_nr += c;
        } else {
            second_nr += c;
        }

    }

    //Remove first character from action string because it's analysed in this recursion
    actions = actions.erase(0, 1);

    //DEBUG OUTPUT:
    //std::cout << first_nr << operatorToChar(oper) << second_nr << std::endl;
    //std::cout << std::endl << actions << " Gives ";
    //std::cout << std::to_string(result) << std::endl;

    //Make recursive call
    return calculate(result, actions, first_nr, second_nr, oper);
}

int main() {
    //String we want to calculate
    std::string str = "1*2-2*3";
    std::string str_copy_for_output = str;

    //Variables
    double result = 0;
    std::string first_nr = "";
    std::string second_nr = "";
    Operator oper = Operator::UNDEFINED;

    //Call function
    int calculation = calculate(result, str, first_nr, second_nr, oper);

    //Output
    std::cout << std::endl << str_copy_for_output << " = " << calculation << std::endl;

    return 0;
}


tl;dr This code works perfectly for strings only containing plusses and mins or only times and divides. Combining times and divides messes it up. Probably the operator parameter fails to update. How to fix this?

Answer

I’m sorry if I did not not analyze your code in detail because it is way too much complicated for what you are trying to do. Therefore I will not tell you where is exactly the problem, instead I will propose you something more simple.

One way or another you need to manage a stack because an algebraic expression must be handled as a tree structure and the evaluation process has to follow that structure. It can’t be handled as a flat structure and you can’t escape the management of operator precedence. In addition to that an expression is normally evaluated from left to right (left associativity).

That said if you really don’t want to use a parsing tool (which IMHO would be more simple and clean), it is always possible to parse “manually”. In that case you may avoid to manage an explicit stack by using the call stack itself as demonstrated in the following code:

#include <iostream>

int precedenceOf(char op) {
    switch (op) {
    case '+':
    case '-':
        return 4;
    case '*':
    case '/':
        return 3;
    }
    return 0;   // never happen
}
const int MAX_PRECEDENCE = 4;

double computeOp(double left, double right, char c) {
    switch (c) {
    case '+': return left + right;
    case '-': return left - right;
    case '*': return left * right;
    case '/': return left / right;
    }
    return 0;   // never happen
}

char readOperator(const char*& expr)
{
    // read the operator
    while (*expr != 0) {
        switch (*expr) {
        case '+':
        case '-':
        case '*':
        case '/':
        {
            char res = *expr;
            expr++;
            return res;
        }
        case ' ':
            break;
        }
        expr++;
    }
    return 0;
}

double readOperand(const char*& expr)
{
    double result = 0;
    while (*expr != 0 && *expr == ' ') expr++;
    while (*expr != 0) {
        if (*expr >= '0' && *expr <= '9')
            result = result * 10 + *expr - '0';
        else
            return result;
        expr++;
    }
    return result;
}

double eval(const char*& expr, int breakPrecedence = MAX_PRECEDENCE + 1);

// evalRight function reads the right part of an expression and evaluates it 
// (up to the point where an operator with precedence 'breakPrecedence' is reached)
// returns the computation of the expression with the left operand passed as parameter.
double evalRight(const char*& expr, int breakPrecedence, double leftOperand)
{
    do
    {
        auto posBeforeOp = expr;
        auto op = readOperator(expr);
        if (op == 0)
            return leftOperand;  // end of expression reached, meaning there is no right part

        auto prec = precedenceOf(op);
        if (prec >= breakPrecedence)
        {
            expr = posBeforeOp;  // we backtrack before the operator (which will be handled by one of our caller)
            return leftOperand;
        }

        // reads and evaluates the expression on the right hand side
        auto rightOperand = eval(expr, prec);
        // computes the current operation, the result becoming the new left operand of the next operation
        leftOperand = computeOp(leftOperand, rightOperand, op);
    } while (true);
}

// eval function reads an expression and evaluates it (evaluates it up to the point where an operator with precedence 'breakPrecedence' is reached)
// returns the evaluation of the expression
double eval(const char*& expr, int breakPrecedence)
{
    auto leftOperand = readOperand(expr);
    return evalRight(expr, breakPrecedence, leftOperand);
}

int main()
{
    auto expression = "1 + 1 * 2 - 2 * 3 + 1";
    std::cout << "result = " << eval(expression);   // prints: result = -2
    return 0;
}

To keep the code as simple as possible the provided expression is assumed to be syntactically correct. It’s up to you to add some checks if you want.

Hope this helps.

We are here to answer your question about Failing to parse different math operators - If you find the proper solution, please don't forgot to share this with your team members.

Related Posts

Tutorial Guruji