2

I'm doing an advanced calculation process (something similar to scientific mode for calculator). I'm seeking for algorithm that can help me finish this task for my project. Here is the problem:

Let take an example 10+10*2. The result of this SHOULD be 30. So, the problem I'm facing is that divide and multiply should take advantage of + and - operation (even without brackets). I basically know how to do a calculator which have basic functions like result of 10+10*2 is 40 (put first number in variable, then second in another variable, and third in first variable again). In regard, I wrote a few algo but none of them worked. My solution to this would be to parse whole strng '10+10*2' and then split them apart to detect operations +, -, / and *. Then recalculate the process. But that seems a bit longer and I suspect a lot of "if" conditions plus who use a string while calculating?

We can discuss about any idea.
Thanks!

P.S. I'm familiar with a few languages so any solution can be made. I accept pseudo codes in various high-level languages. I'm just not familiar with algo (programming logic).

user3468932
  • 23
  • 3
  • Do you plan to add brackets later? Or simple solution with only +-*/ and two types of priority is enough? – libik Mar 27 '14 at 14:21
  • No need for brackets. Thats why I don't want to play with strings. Simple solution with +,-,*,/ with priority of * and / is what I want. – user3468932 Mar 27 '14 at 14:23
  • The most common algorithm for doing this is the Shunting Yard algorithm. In your case, you should be able to just keep track of a few more variables and not perform addition until you know that you can (because you have encountered another addition). – Teepeemm Mar 27 '14 at 14:39
  • http://stackoverflow.com/questions/9329406/evaluating-arithmetic-expressions-in-c/9329509#9329509 – Henrik Mar 27 '14 at 14:51

2 Answers2

0

The most easiest solution for your example is to cycle through your expression twice.

In first run, you only multiply/divide, you dont add or substract anything. In second run, there is no multiplying/dividing, therefore you can do it form left to right.

Pseudocode :

for (number : numbers) { //for each number in numbers in your expression
  if (next operator is */){
    number */= nextNumber();
    removeNextOperator();
    removeNextNumber();
    doNotMoveFromThisNumberInNextStep(); //like decrementing index variable in classic for-cycle
  }
}

now we have expression with only +-, which you say you know how to do it

I thought a bit and it can be done in one run! You only need to remember the sum you get from adding/substracting when you find */.

Pseudocode :

int sum = 0;
for (number : numbers) { //for each number in numbers in your expression
  if (next operator is */){
    number */= nextNumber();
    removeNextOperator();
    removeNextNumber();
    doNotMoveFromThisNumberInNextStep(); //like decrementing index variable in classic for-cycle
  } else { //next operator is +- or the last number
    sum +-= numberBefore() +- number;
  }
}
libik
  • 22,239
  • 9
  • 44
  • 87
  • This is what I though too. Thus working in such a way takes a lot of time (multiple scanning). It will be hard to optimize in case of huge operations. Thanks for answer! – user3468932 Mar 27 '14 at 15:28
  • @user3468932 - it is still linear time and it is still 1/2 slower than do it in one "run", which is very fast, considering you dont need any complex structures (like creating evalution trees for bracket-based expressions). – libik Mar 27 '14 at 15:58
  • @user3468932 - now I do it in one cycle, look to edited post. – libik Mar 27 '14 at 16:03
  • Wonderful, I'll use this type of algorithm. Thanks for your time. Answer accepted. – user3468932 Mar 27 '14 at 16:35
0

You need to implement operation priority and you have only two category [+-] [*/] (however the common algorithm is the same):

  1. Split expression to numbers and operations
  2. Take the highest priority operation here is * / from left to right
  3. Calculate it and
  4. Replace the operation and numbers with the result and do 2

And yes, a lot of languages supports eval(arithmetic expression)

Sergei Chicherin
  • 2,031
  • 1
  • 18
  • 24
  • To be honest, I'm not that much interested in eval function. I'll try to parse in way you say but @libik wrote similar answer, check the comment. – user3468932 Mar 27 '14 at 15:29