1

Alright, so I'm trying to make an expression-as-a-string solver, so that the user can input a string, such as 2+4*5/10, and it will print out the answer, 4. I have some code written, but it doesn't apply the order of operations; it simply solves the equation in order of the operators - e.g. 2+4*5/10 would produce 3, which is incorrect. How do I make it so that multiplication and division are performed first, then addition and subtraction? Here's the code I have right now: 

class Expressions
{
String E;
void SetE(String e)
{
    E = e;
}

int EvalE()
{
    int res = 0;
    int temp = 0;
    char op = '+';

    for(int i=0;i<E.length();i++)
    {
        if(E.charAt(i)=='*'||E.charAt(i)=='/'||E.charAt(i)=='+'||E.charAt(i)=='-')
        {
            if(op=='*')res*=temp;
            else if(op=='/')res/=temp;
            else if(op=='+')res+=temp;
            else res-=temp;

            temp=0;
            op=E.charAt(i);
        }
        else
        {
            temp = temp*10+E.charAt(i)-'0';
        }
    }

    if(op=='*')res*=temp;
    else if(op=='/')res/=temp;
    else if(op=='+')res+=temp;
    else res-=temp;

    return res;
}
}
user2967415
  • 11
  • 1
  • 2

3 Answers3

2

Split the expression into two simpler expressions, then use recursion.

You have to do the following steps in precisely this order, or you will mess up the order of operations.

  1. Look for the rightmost + sign. If there is such a +, then use recursion to evaluate the sub-expression to the left of it, then the sub-expression to the right of it, then add them and return the result.
  2. If there's no + sign, then look for the rightmost - sign that's preceded by a number (that is, it's subtraction, not negation). If there is such a -, then use recursion to evaluate the sub-expression to the left of it, then the sub-expression to the right of it, then subtract them and return the result.
  3. If there's no + or - sign, then look for the rightmost * sign. If there is such a *, then use recursion to evaluate the sub-expression to the left of it, then the sub-expression to the right of it, then multiply them and return the result.
  4. If there's no +, - or * sign, then look for the rightmost * sign. If there is such a *, then use recursion to evaluate the sub-expression to the left of it, then the sub-expression to the right of it, then divide them and return the result. If you're using integers, you'll have to think about whether you want integer division or floating point. You might also want to do some kind of check around dividing by zero.
  5. If there's no +, -, * or /, then all you've got is numbers and whitespace. Maybe a negative sign. Strip out the whitespace, parse it and return it.

Example: "6 - 5 - 4 + 3 * -2"

  • First, split at the +, and use recursion to evaluate "6 - 5 - 4 " and " 3 * -2".
  • For "6 - 5 - 4 ", split at the second - , and use recursion to evaluate "6 - 5 " and " 4 ".
  • For "6 - 5 ", split at the -, and use recursion to evaluate "6 " and " 5 ".
  • For " 3 * -2", split at the *, because the - is not preceded by a number. Use recursion to evaluate " 3 " and " -2 ".
  • For each of "6 ", " 5 ", " 4 ", " 3 " and " -2 ", there are no operators, so we just strip out the white space and parse.
  • The result of our calculation will be "((6-5)-4)+(3*-2)", so the order of operations worked out correctly.
Dawood ibn Kareem
  • 77,785
  • 15
  • 98
  • 110
1

Use two for loops.

In your first loop, search for * and / operators. Evaluate that part and replace that part of the string with the result of the evaluation.

In your second loop, do all the + and - as you're already doing.

So for the example you use, 2+4*5/10, your first loop would look for * or /. Upon finding the *, it evaluates 4*5. That's 20, so the string is modified into 2+20/10. Check again, and it finds the /, and modifies the string into 2+2.

Now you go through your second loop, and get 4.

nhgrif
  • 61,578
  • 25
  • 134
  • 173
  • That's what I thought I had to do, but I'm not really sure how to replace 4*5 with 20. – user2967415 Nov 08 '13 at 03:32
  • Start by finding the index of the substring `4*5`, perform the multiplication on that substring, turn the result into a string, then use the `replace` method. – nhgrif Nov 08 '13 at 03:38
  • Ok, I suppose my real problem is that I don't know how to make `4*5` a substring. I know it needs to be like `E.substring(E.indexOf('4'),E.indexOf('5')+1)` in this case, but I have no idea how to specify which which character should be the beginning index and which should be the ending index, when `E` can be any string. Thanks for the help so far though! – user2967415 Nov 08 '13 at 03:50
  • `E.subString( (E.indexOf("*") - 1), (E.indexOf("*") + 1) )`? I'm not perfectly familiar with Java's `String` methods. – nhgrif Nov 08 '13 at 03:51
  • That would work, but the numbers can be any size. So if `4` were actually `278`, then that wouldn't work. – user2967415 Nov 08 '13 at 03:53
  • Collect the indexes of all the operators. OR, split the string into two arrays. In one array you have the numbers, in the other array you have the operator. The operator at index 0 of the operator array goes between the numbers at index 0 and 1 of the numbers array, etc. – nhgrif Nov 08 '13 at 03:55
  • I haven't learned how to use arrays yet; I've just been programming for a few months. Even if I collected all the indexes of the operators, how would I store them without an array, assuming that there can be more than one of each type? – user2967415 Nov 08 '13 at 03:59
1

You need to do two steps instead of one. In first step you parse equation into the reverse polish notation, then in second step you run through that and calculate results. Nice bonus is you get brackets support for (almost) free :-)

PiotrK
  • 4,210
  • 6
  • 45
  • 65