other ideas for calculating a string that contains e.g. "5 + 3 / 2"

Question

i have written a program, where you give a string as input. this string should be a normal term e.g. "5 + 3 / 2" and all numbers and operators have to be seperated via a whitespace. the term you can type in should be as long as you want it to be, e.g. "1 * 2 * 5 - 1 * 4 + 1 + 5 + 3 + 3 + 3" should be working too. +, -, * and / are the only operators that are allowed to be used.

i have already got a working code. but it ignores the fact of * and / before + and -. but it does everything else perfectly. the idea is it creates two arrays, one that saves the operators in a char array (called char operators[ ])and the other array saves the integers in a float array (called float values[ ]). then i have this calculation method:

    void calc(float values[], char operators[]) {
    float res_final;
    float res_array[10];
    int counter = (sizeof(values) / sizeof(*values));

    for (int i = 0; i < getBorder(values); i++) {
        if (i == 0) {
            res_array[i] = switchFunction(values[i], values[i + 1], operators[i]);
        }

        res_final = switchFunction(res_array[i], values[i + 2], operators[i + 1]);
        res_array[i+1] = res_final;
        if (i == getBorder(values)) {
            break;
        }
    }
    std::cout << "evaluation of expression is: " << res_final << std::endl;
    }

    float switchFunction(float val_1, float val_2, char op) {
    switch (op) {
    case '+': return val_1 + val_2;
        break;
    case '-': return val_1 - val_2;
        break;
    case '*': return val_1 * val_2;
        break;
    case '/': return val_1 / val_2;
        break;
    }
    return 0;
    }

well the code is not really pretty, but i couldnt come up with anything more useful. i have so many ideas but it all failed when it comes to the operators. i wanted to define the normal + in '+' and for the rest too, but this wont work.

so if you have any suggestions on how to include point before line or if you have a complete different approach to mine, i would be glad to hear about it :)

Answer 1

In the long run, you want to create an Object that represents the formula.

A good structure would be a tree. An inner node of such a tree is an operator, while a leaf is a number.

Then you write a parser that parses a string into a tree. I'd do this recursive like this:

FormulaNode parse(input){
    string left, right;
    if(split_string(input, * or /, left, right){
        return FormulaNode(* or /, parse(left), parse(right))
    if(split_string(input, + or -, left, right){
        ...
    }
    return FormulaNode(number, to_value(string))
}

with split_string being a method that tries to split a string by a certain symbol, returns a boolean if that was possible and splits it into the references left and right,

FormulaNode(symbol, left child, right child) being a constructor that creates an inner node,

FormulaNode(number, value) being a constructor that creates a leaf.

Of course, all of this is pseudo-code, didn't want to impose a style on you, just to illustrate the principle. The second constructor might probably only be of the signature FormulaNode(const double). As for symbol, I'd recommend to create something like enumerate OperatorType {addition,...}.

EDIT:

here is a bigger architecture with a somewhat different design:

class FormulaTree{

    private:

    class FormulaNode{

        private:

            bool is_number;

            //used members if is number
            double value;

            //used members if not is number / is operator
            OperatorType type;
            unique_ptr<FormulaNode> left_child, right_child;

        public:

            FormulaNode(string input);
            double evaluate() const;
    };

        unique_ptr<FormulaNode> root;

    public:

        Formula(string input);
        double evaluate() const;
}

with (in pseudo-code)

FormulaTree::FormulaNode::FormulaNode(string input){

    if(input contains * or /){

        char symbol = first occurence(input, * or /);
        vector<string> split_input= split at first occurence(input, symbol);
        type = OperatorType(symbol);

        is_number = false;
        left_child = make_unique(new FormulaNode(split_input[0]));
        right_child = make_unique(new FormulaNode(split_input[1]));
        return;
    }

    if(input contains + or -){

        ...
    }

    is_number = true;
    value = parse to int(input);
}

(in the long run, you might also want to add something that checks if the input is legal, like "the string is not empty on one side of an operator", "parse to int worked, that is contained no illegal characters" et cetera)

(also, if you continue to expand this, you need some parser that splits it by brackets first)

If you need me to explain anything about this structure, simply ask, I'll edit.

EDIT:

Slava commented that it would be better to derive FormulaNode for the different types. This is right, and I originally edited this to show such a design, but I removed it again because it might easily confuse a beginner.

Especially since such a pattern would require a somewhat different layout - we would want to let the tree itself do the parsing since the derived classes shouldn't know each other. In the long run, you want to learn such things. I'd recommend that you try out the pattern I presented, add your own style, add some more features (like a symbol for power or the option to use a minus to denote a negative number) and then put it on CodeReview. My reasoning is that this is what you want to do anyway and when you do, your code will be attacked at every part anyway, until it's "perfect".