Failing to parse different math operators

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.

As you said

I'd like to craft something of my own, this is not production-code. Just hobby.

so probably you want to learn a thing or two. That's why I won't write any code here and steal all the fun from you.

Looks like you should start from the basics. I could've recommend you the Dragon Book but you probably want to get your hands dirty right away instead of reading the classics for a week. So you can start with PEGs - it's really simple. I've started to love parsing after I've read this article.

In your case the grammar will be quite simple:

Expr    ← Sum
Sum     ← Product (('+' / '-') Product)*
Product ← Value (('*' / '/') Value)*
Value   ← [0-9]+

With functions you can rewrite it like this

value   = repeat_at_least_once(character("0"),...,character("9"))
product = sequence(value  , repeat(one_of(character("*"),character("/")), value  ) 
expr    = sequence(product, repeat(one_of(character("+"),character("-")), product)

All you have to do now - write these functions :) It will be not much longer than the code you've written, if not shorter.

^{If you fill confident, you can even implement packrat parsing with left recursion support, in this case you grammar will be even simpler.}

IMHO, your current approach (doing multiplications and divisions first, then continuing with addition and subtraction, and all in one function) will be painful at best. Your calculate function is very hard to reason about already, because it mixes multiple cases already, e.g.

• first pass or second pass (depending on the content of string action, which is the current status of the expression, which you modify from call to call)
• first_nr empty/filled
• second_nr empty/filled

Now imagine that more operators are added, like ^ and ( and ). I do understand that this is a hobby project. But even if you get this to work one day, you will not be able to understand it a week later.

Since you want to reuse your current code, how about this:

Think about how you yourself (as a human being) would go about this? There are multiple approaches. Independent of the specific algorithm they consist of two parts:

• Tokenization (identifying numbers and operators)
• Evaluation (combine those numbers and operators)

You are mixing both parts in your code. It would be much simpler for you and anybody you are asking for help if you separated them.

Tokenization is simple (you are doing it already, although I would recommend to treat the expression string as read-only).

Evaluation is more tricky, because you have to think about operator precedence. But again, it helps to think about how you would do it as a human. You might read from left to right. How do you handle that as a person? You might evaluate sub expressions with higher precedence first (as you intend to do now). How do you store the tokens? Think of different data structures. Lists, stacks, or queues for examples.

There are many ways. Once you found one, looking at some literature should be fun.

Enjoy!

While I clearly stated I did not want a postfix solution, I actually realized it's the most sane solution. I made a postfix solution myself with the help of tutorials (and still learnt a lot!). Thanks everyone for the help and suggestions.

#include <iostream>
#include <string>
#include <stack>

/*
 * Function to check if a given character is an operator (+, -, *, /) or not
 * :param c: Character to check
 * :return bool: Returns true if parameter c is an operator
 */ 
bool isOperator(char c) {
    char operators[4] = {'+', '-', '*', '/'};
    if (std::find(std::begin(operators), std::end(operators), c) != std::end(operators)) {
        return true;
    }

    return false;
}

/*
 * Function to get the precedence matching the character
 *
 * :param a: Character containing the operator to get precedence from
 * :return int: Integer representing precedence. Operators with high precedence (e.g * and /) return a higher value than e.g + and -.
 *
 * Example:
 * precedence('*') > precedence('+') == true
 *
 */
int precedence(char a) {
    switch (a) {
        case '+': return 1;
                  break;
        case '-': return 1;
                  break;
        case '*': return 2;
                  break;
        case '/': return 2;
                  break;
    }

    return -1;
}

/*
 * Function to convert an infix string to postfix notation
 * :param infix: Infix string
 * :return string: returns postfix string
 *
 * Example:
 * std::string s = "5+5";
 * toPostfix(s) == "5 5 +"
 *
 */
std::string toPostfix(std::string& infix) {
    std::string postfix = "";

    //Stack to hold operators and nr is a helper string to
    //group digits in numbers
    std::stack<char> stack;
    std::string nr = "";

    //If first character is a minus-operator (AKA a negative number)
    //add "0"
    if (infix[0] == '-') {
        infix = "0" + infix;
    }

    //Looping over infix string
    for (int i = 0; i < infix.size(); i++) {
        //If current evaluated character ain't an operator, it's a digit
        if (!isOperator(infix[i])) {
            //If digit is in a group of digits (AKA a number) put the whole number in nr
            while (!isOperator(infix[i]) && i < infix.size()) {
                nr += infix[i];
                i++;
            }

            i--;

            //Append the number to the postfix string
            postfix += nr + " ";
            nr = "";
        } else {
            //This block is executed when evaluated character is an operator

            //If stack is empty, or the evaluated operator is higher than the one in the stack
            //push it to the stack (Needs to be appended to the postfix string later)
            if (stack.size() == 0 || precedence(infix[i]) > precedence(stack.top())) {
                stack.push(infix[i]);
            } else {
                //While the stack contacts a higher or equally high precedence as currently
                //evaluated operator
                while (precedence(stack.top()) >= precedence(infix[i])) {
                    //We append the top of the stack to the postfix string
                    postfix += stack.top();
                    postfix += ' ';

                    stack.pop();
                    if (stack.size() == 0) {
                        break;
                    }
                }

                //Push evaluated operator to stack
                stack.push(infix[i]);
            }
        }
    }

    //Append all remaining operators to the postfix string
    while (stack.size() != 0) {
        postfix += stack.top();
        stack.pop();
    }

    return postfix;
}

/*
 * Evaluate two numbers regaring the used operator
 * :param x: First number to do evaluation with
 * :param y: Second number to do evaluation with
 * :param _operator: Operator to do calculation with
 * :return double: Result of the evaluation
 *
 * Example:
 *  x: 5
 *  y: 60
 *  _operator: +
 *  = 65
 */
double evaluate(double x, double y, char _operator) {
    switch(_operator) {
        case '+':
            return x + y;
            break;
        case '-':
            return x - y;
            break;
        case '*':
            return x * y;
            break;
        case '/':
            return x / y;
            break;
    }

    return 0;
}

/*
 * Calculate the result of an infix string
 * :param s: String containing the infix notation
 * :return double: Result of the calculation
 *
 * Example:
 * std::string s = "5+5";
 * calculate(s) == 10
 */
double calculate(std::string& s) {

    //Convert infix to postfix
    s = toPostfix(s);

    //Stack holding operators and nr (string) for separating numbers
    std::stack<double> stack;
    std::string nr = "";

    //Looping over postfix string
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == ' ') {
            continue;
        }

        //If evaluated character is a digit,
        //put it in nr
        if (isdigit(s[i])) {
            //If digit is first of a group of digits, put that group of digits
            //AKA a number in nr
            while (isdigit(s[i])) {
                nr += s[i];
                i++;
            }
            i--;

            //Pushing nr in stack
            stack.push(std::stod(nr));
            nr = "";
        } else {
            //If current evaluated character is not a digit
            //but an operator, do a calculation

            //Retrieve first number for calculation
            int x = stack.top();
            stack.pop();

            //Retrieve second number for calculation
            int y = stack.top();
            stack.pop();

            //Put evaluation result in integer and push into stack
            int result = evaluate(y, x, s[i]);
            stack.push(result);
        }
    }

    //Final number is in stack
    return stack.top();
}



int main() {

    std::string s = "-5*5-2*2+3-10/5";
    std::cout << calculate(s) << std::endl;


}

you need divided calculation for several steps

1. copy expression to writable memory and check/normalize it:

.check that all chars valid (positive)

.remove spaces

.convert all to low (or upper) case (if case you use hex expressions)

.some operators take 2 symbols ( ==, !=, >=, <=, <<, >>, ||, && ) - replace it to single symbol, from not valid (negative) range

2. remove ( ) if exist - calculate expressions in ():

.find first ) symbol from begin

.find last ( before it.

.check that after ) and before ( was separator symbols (operator or begin/end of string) but not digit.

.format new string where you replace (..) with it digital result

3. remove (calculate) all unary operators (+, -, !, ~)

.unary operators - on right side must have digit and on left - another operator(or begin of string), but not digit

.format new string with result of unary operator

4. remove (calculate) all binary operators.

.we need calculate in reverse precedence - so first need calculate/remove operators with lowest precedence.

.so need do loop by operators (from low to high precedence) - search operator symbol in string.

.if found - A op B - calculate separate A and B and then apply op.

5. convert string to integer

.now, after all ( ) and operators removed - only digit must be in string

example of code:

namespace Eval 
{
    typedef INT_PTR (* fn_b_op)(INT_PTR a, INT_PTR b);
    typedef INT_PTR (* fn_u_op)(INT_PTR a);

    struct b_op_arr { fn_b_op pfn; char c; };
    struct u_op_arr { fn_u_op pfn; char c; };

    struct name_to_char { char b[3]; char c;};

    static INT_PTR fn1_bnt(INT_PTR a){ return !a; }
    static INT_PTR fn1_not(INT_PTR a){ return ~a; }
    static INT_PTR fn1_add(INT_PTR a){ return +a; }
    static INT_PTR fn1_sub(INT_PTR a){ return -a; }

    static INT_PTR fn2Land(INT_PTR a,INT_PTR b){ return a && b; }
    static INT_PTR fn2_Lor(INT_PTR a,INT_PTR b){ return a || b; }
    static INT_PTR fn2_equ(INT_PTR a,INT_PTR b){ return a == b; }
    static INT_PTR fn2_nqu(INT_PTR a,INT_PTR b){ return a != b; }
    static INT_PTR fn2_lqu(INT_PTR a,INT_PTR b){ return a < b;  }
    static INT_PTR fn2_gqu(INT_PTR a,INT_PTR b){ return a > b;  }
    static INT_PTR fn2_leu(INT_PTR a,INT_PTR b){ return a <= b; }
    static INT_PTR fn2_geu(INT_PTR a,INT_PTR b){ return a >= b; }
    static INT_PTR fn2_add(INT_PTR a,INT_PTR b){ return a + b;  }
    static INT_PTR fn2_sub(INT_PTR a,INT_PTR b){ return a - b;  }
    static INT_PTR fn2_mul(INT_PTR a,INT_PTR b){ return a * b;  }
    static INT_PTR fn2_div(INT_PTR a,INT_PTR b){ return a / b;  }
    static INT_PTR fn2_dv2(INT_PTR a,INT_PTR b){ return a % b;  }
    static INT_PTR fn2_lsh(INT_PTR a,INT_PTR b){ return (UINT_PTR)a << b; }
    static INT_PTR fn2_rsh(INT_PTR a,INT_PTR b){ return (UINT_PTR)a >> b; }
    static INT_PTR fn2_xor(INT_PTR a,INT_PTR b){ return a ^ b; }
    static INT_PTR fn2_and(INT_PTR a,INT_PTR b){ return a & b; }
    static INT_PTR fn2__or(INT_PTR a,INT_PTR b){ return a | b; }

    enum /*: char*/ { equ = -0x80, not_equ, less_equ, gre_equ, l_or, l_and, r_shift, l_shift };

    inline static b_op_arr b_arr[] = 
    {
        {fn2_mul, '*'}, {fn2_div, '/'}, {fn2_lsh, l_shift}, {fn2_rsh, r_shift},
        {fn2_xor, '^'}, {fn2_dv2, '%'}, {fn2_and, '&'}, {fn2__or, '|'},
        {fn2_equ, equ}, {fn2_nqu, not_equ}, {fn2_lqu, '<'}, {fn2_gqu, '>'},
        {fn2_leu, less_equ},{fn2_geu, gre_equ},{fn2_add, '+'}, {fn2_sub, '-'},
        {fn2Land, l_and}, {fn2_Lor, l_or}
    };

    inline static u_op_arr u_arr[] = 
    {
        {fn1_add, '+'}, {fn1_sub, '-'}, {fn1_bnt,'!'}, {fn1_not,'~'}
    };

    inline static name_to_char _2_to_1[] =
    {
        {"==", equ}, {"!=", not_equ}, {"<=", less_equ}, {">=", gre_equ }, 
        {">>", r_shift}, {"<<", l_shift}, {"||", l_or}, {"&&", l_and}, 
    };

    void initBits(LONG bits[], const char cc[], ULONG n)
    {
        do 
        {
            _bittestandset(bits, cc[--n]);
        } while (n);
    }

    static bool IsSeparatorSymbol(char c)
    {
        static LONG bits[8];
        static bool bInit;

        if (!bInit)
        {
            // acquire
            static const char cc[] = { 
                '*', '/', '+', '-', '^', '%', '&', '|', '<', '>', '!', '~', '(', ')',
                equ, not_equ, less_equ, gre_equ, l_or, l_and, r_shift, l_shift, 0
            };

            initBits(bits, cc, _countof(cc));

            // release
            bInit = true;
        }

        return _bittest(bits, c);
    }

    static bool IsUnaryOpSymbol(char c)
    {
        static LONG bits[8];
        static bool bInit;

        if (!bInit)
        {
            // acquire
            static char cc[] = { 
                '+', '-', '!', '~'
            };

            initBits(bits, cc, _countof(cc));

            // release
            bInit = true;
        }

        return _bittest(bits, c);
    }

    static bool IsDigit(char c)
    {
        static LONG bits[8];
        static bool bInit;

        if (!bInit)
        {
            // acquire
            static char cc[] = { 
                '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'
            };

            initBits(bits, cc, _countof(cc));

            // release
            bInit = true;
        }

        return _bittest(bits, c);
    }

    __int64 strtol64_16(char* sz, char** psz)
    {
        __int64 r = 0;

        while (char c = *sz)
        {
            ULONG d;

            if ((ULONG)(c - '0') <= '9' - '0')
            {
                d = (c - '0');
            }
            else if ((ULONG)(c - 'a') <= 'z' - 'a')
            {
                d = (c - 'a') + 10;
            }
            else
            {
                break;
            }

            r = (r << 4) + d;
            sz++;
        }

        *psz = sz;

        return r;
    }

    bool Normalize(const char* psz, char* buf, size_t s)
    {
        int len = 0;

        do 
        {
            --s;
            char c = *psz++, d;

            // is valid char
            if (c < 0) return false;

            // skip space
            if (c == ' ') continue;

            if ((ULONG)(c - 'A') < (ULONG)('Z' - 'A'))
            {
                c += 'a' - 'A';
            }

            // not last char
            if (s)
            {
                d = *psz;

                int k = _countof(_2_to_1);
                do 
                {
                    if (_2_to_1[--k].b[0] == c && _2_to_1[k].b[1] == d)
                    {
                        c = _2_to_1[k].c, psz++, --s;
                        break;
                    }
                } while (k);
            }

            *buf++ = c, len++;

        } while (s);

        return 0 < len;
    }

    char* format_new_str(const char* a, INT_PTR r, const char* b)
    {
        static const char format[] = "%s%I64x%s";

        int len = _scprintf(format, a, r, b);

        if (0 < len)
        {
            if (char* buf = new char [++len])
            {
                if (0 < sprintf_s(buf, len, format, a, r, b))
                {
                    DbgPrint("++%p\n\"%s\"\n", buf, buf);
                    return buf;
                }

                delete buf;
            }
        }

        return 0;
    }

    bool _calc (char* str, INT_PTR& result)
    {
        DbgPrint("\"%s\"\n", str);
        struct SB 
        {
            char* str;

            SB() : str(0) {}

            ~SB()
            {
                operator <<(0);
            }

            void operator <<(char* psz)
            {
                if (str) 
                {
                    DbgPrint("--%p\n", str);
                    delete [] str;
                }
                str = psz;
            }
        } sb;

        size_t len = strlen(str);

        if (!len)
        {
            return false;
        }

        char b, c;
        int l;
        INT_PTR r, q;

        //1. remove ( )
        char *psz = str, *pc = 0, *buf;

        for (;;)
        {
            switch (*psz++)
            {
            case '(':
                pc = psz;
                continue;

            case ')':

                if (!pc || !IsSeparatorSymbol(*psz) || (pc > str + 1 && !IsSeparatorSymbol(pc[-2]))) return false;

                psz[-1] = 0, pc[-1] = 0;

                if (_calc(pc, r) && (buf = format_new_str(str, r, psz)))
                {
                    sb << buf;
                    psz = str = buf, pc = 0;
                    continue;
                }

                return false;
            case 0:
                goto __2;
            }
        }

__2:
        //2. remove unary op

        psz = str;

        do 
        {
            if (IsDigit(c = *psz) && str < psz && IsUnaryOpSymbol(c = psz[-1]) && (psz == str + 1 || IsSeparatorSymbol(psz[-2])))
            {
                psz[-1] = 0;
                l = _countof(u_arr);
                do 
                {

                    if (u_arr[--l].c == c)
                    {
                        r = strtol64_16(psz, &psz);
                        if (IsSeparatorSymbol(*psz))
                        {
                            r = u_arr[l].pfn(r);

                            if (buf = format_new_str(str, r, psz))
                            {
                                sb << buf;
                                psz = str = buf;
                                goto __2;
                            }
                        }
                        break;
                    }
                } while (l);

                return false;
            }
        } while (psz++, c);

        //3. remove binary op

        l = _countof(b_arr);
        do 
        {
            c = b_arr[--l].c;

            psz = str;

            do 
            {
                if (c == (b = *psz++))
                {
                    psz[-1] = 0;
                    if (_calc(psz, q) && _calc(str, r))
                    {
                        result = b_arr[l].pfn(r, q);

                        return true;
                    }

                    return false;
                }
            } while (b);

        } while (l);

        result = strtol64_16(str, &str);

        return !*str;
    }

    bool calc(const char* psz, INT_PTR& result)
    {
        bool fOk = false;

        if (size_t s = strlen(psz))
        {
            if (char* buf = new char[++s])
            {
                if (Normalize(psz, buf, s))
                {
                    fOk = _calc(buf, result);
                }

                delete [] buf;
            }
        }

        return fOk;
    }
};

use

INT_PTR r;
Eval::calc(str, r);

While reading Learning Go I've implemented some of the suggested training programs. One of which has nearly the same requirements as yours, although I have to admit, that yours is a bit more evolved. So, I hope you can get something out of this code (I know it's not C++, but I'm sure you can read it):

package main

import (
  "fmt"
  "os"
  "bufio"
  "stack"
  "strconv"
)

func readInput() string {
  reader := bufio.NewReader(os.Stdin)
  switch in, ok := reader.ReadString('\n'); true {
  case ok != nil:
    fmt.Printf("Failed to read inputs: %v", ok)
    return "error"
  default:
    return in[:len(in)-1]
  }
}

func isdigit(in string) bool {
  _,ok := strconv.Atoi(in)
  return ok == nil
}

func isOperation(in string) bool {
  chars := []rune(in)
  return '+' == chars[0] || '-' == chars[0] || '*' == chars[0] || '/' == chars[0]
}

func calc(operation string, op2, op1 int) float32 {
  chars := []rune(operation)
  switch chars[0] {
  case '+':
    return float32(op1 + op2)
  case '-':
    return float32(op1 - op2)
  case '*':
    return float32(op1 * op2)
  case '/':
    return float32(op1) / float32(op2)
  }
  print("Failed to recognize operation: ")
  println(operation)
  fmt.Printf("%v\n", chars)
  return 0.0
}

func main() {
  var st stack.Stack

  fmt.Println("Calculator.")
  fmt.Println("Please input operations and then one of + - * / for calculation,")
  fmt.Println("or anything else for exit.")

LOOP:  for {
    in := readInput()
    switch {
    case isdigit(in):
      i,_ := strconv.Atoi(in)
      st.Push(i)
    case isOperation(in):
      op2 := st.Pop()
      op1 := st.Pop()
      res := calc(in, op2, op1)
      st.Push(int(res))
      fmt.Println(res)
    default:
      fmt.Println("Exit")
      break LOOP
    }
  }
}

... similar, isn't it?