String expressions with four operators

Question

CS Student here. I want to be able to take a string such as '2+2*3/2-2' and evaluate it (= 3). But I'm not sure how to structure the code to follow the proper order of operations. Here's code for multiplication and division:

int r = 1;
    int n = 0;
    char op = '*';

    for (int i = 0; i < E.length(); i++)
        if (E.charAt(i)=='*'||E.charAt(i)=='/')
        {
            if (op == '*')
                r *= n;
            else
                r /= n;
            n = 0;
            op = E.charAt(i);
        }
        else
            n = n*10 + (E.charAt(i)-'0');

    if (op == '*')
        r *= n;
    else
        r /= n;

    return r;

Thanks for reading!

You may find some interesting information at http://stackoverflow.com/questions/3422673/evaluating-a-math-expression-given-in-string-form — Dawood ibn Kareem, Nov 07 '13 at 22:54

score 2 · Answer 1 · answered Nov 07 '13 at 22:39

2

Use a binary tree where each node is an arithmetic operator and the leaves are the values.

answered Nov 07 '13 at 22:39

MadConan

3,749
1
16
27

1

+1 Calculation is then done bottom-up from the leaves until reaching the root node. – Fabian Barney Nov 07 '13 at 22:42
I'm not sure what that is. I'm just beginning programming. Haven't even been doing it for more than a couple months. – CSpadawan Nov 07 '13 at 22:52

score 0 · Answer 2 · answered Nov 07 '13 at 22:40

This is exactly what the Interpreter pattern is meant to do. Your mathematical operations are basically a grammar - all you need to do is represent that grammar. Use the Interpreter pattern to parse your mathematical statement, and then use what it spits out to perform the necessary operations.

score 0 · Answer 3 · answered Nov 07 '13 at 23:12

Use Reverse Polish Notation to represent your formula in a "computation friendly" form. You can read about RPN here: http://en.wikipedia.org/wiki/Reverse_Polish_notation

RPN version of your 2+2*3/2-2 would be 2 2 3 * 2 / 2 - +

Then the algorithm is like that: Assume each sign from RPN version is an element from the array of symbols. You take element from the array and if this is a number put it on a stack if this is an operator take two elements from the stack and perform operation. The result should land on the stack again. Repeat until you reach the last element of the array. At the end there will be only one element on your stack which is your answer.

Let's visualize: iteration# symbol stack content 1# 2 -> 2 2# 2 -> 2,2 3# 3 -> 3,2,2 4# * -> 6,2 5# 2 -> 2,6,2 6# / -> 3,2 7# 2 -> 2,3,2 8# - -> 1,2 9# + -> 3

score 0 · Answer 4 · answered Nov 07 '13 at 23:58

You need to parse the expression. A simple recursive descent parser can do that:

double expression(const char **p) {
    double rv = term(p);
    while (**p) {
        if (**p = '+') {
            ++*p;
            rv += term(p)
        } else if (**p = '-') {
            ++*p;
            rv -= term(p);
        } else
            break; }
    return rv; }

double term(const char **p) {
    double rv = factor(p);
    while (**p) {
        if (**p = '*') {
            ++*p;
            rv *= factor(p)
        } else if (**p = '/') {
            ++*p;
            rv /= factor(p);
        } else
            break; }
    return rv; }

double factor(const char **p) {
    return strtod(p, (char **)&p);
}

Of course, the above won't deal with spaces in the strings, or parenthesis, or other things you might care about, but they can be added relatively easily.

String expressions with four operators

4 Answers4