0

I'm trying to evaluate a string from left to right as an Integer with numbers between 0-9 and the four basic operators (like "5+8+(8/4)" should evaluate as 15 or "9+((3+4)*5)" as 44 or "4+2*6" as 36 since 4+2 is calculated first due to all operators having same precedence), but I'm having trouble implementing parentheses.

I've managed to get it working if I don't include parentheses. I do this by parsing through the string using a StringTokenizer in a while loop. Each token is stored in a variable, and if it contains a number it's added to a Stack, and if it contains an operator it's added to a Stack. Then, when there are two numbers in the Integer stack, I evaluate them based on the operator in the operator stack. It just goes through like this for the whole string until str.hasMoreTokens() is true, and the while loop breaks. So, something like 8-5+7*3+1/2-4 works perfectly, but I can't find a way to make parentheses work with any expressions

I've tried using String newStr = str.replaceFirst("[^(]*(", ""); to try to cut off everything and including the first ( then recursively evaluate what's left and so on, but I think this is way more complicated than it had to be and I couldn't get it working regardless. I've been thinking for hours, but I can't come up with a simpler way.

Thanks, I'm completely lost at this point, so any guidance/suggestions would be great.

Adam
  • 355
  • 1
  • 6
  • 12
  • Does 8-5+7*3+1/2-4 really work perfectly? Do you give multiplication and division higher precedence than addition and subtraction – Amir Afghani Feb 27 '13 at 05:32
  • @AmirAfghani Yea, it works fine. No, they all have the same precedence. It reads it straight from left to right, so 4+2*6 is 36. – Adam Feb 27 '13 at 05:34
  • Technically, thats wrong - is that OK? – Amir Afghani Feb 27 '13 at 05:34
  • I will suggest using dropincc to avoid reinventing the wheel. http://pfmiles.github.com/blog/growing-a-full-featured-calculator-in-15-minutes-using-dropincc-dot-java/ is a good reference. – Jintian DENG Feb 27 '13 at 05:35
  • What do you mean it's wrong? I just mean inputting that expression as a string is fine. I didn't list the output for that string. edit: If you mean that multiplication doesn't technically have the same precedence as addition, then yes that's okay. – Adam Feb 27 '13 at 05:35
  • Adam, it's wrong because of the rules of PEMDAS. – Amir Afghani Feb 27 '13 at 05:36
  • Ah, then yes, it's okay. Just consider +,-,*,/ to have the same precedence. – Adam Feb 27 '13 at 05:40

2 Answers2

2

If you wish to parse mathematical expressions in the infix notation, you need to implement the shunting yard algorithm. Not seeing your code, its hard to tell whats missing.

Amir Afghani
  • 37,814
  • 16
  • 84
  • 124
  • How so? He needs to use the shunting yard algorithm. I don't think he knew that, before I answered it. – Amir Afghani Feb 27 '13 at 05:46
  • That does seem to be similar to what I'm looking for. Do you know of an example of it used where precedence for each operator are the same? As is, it's really lengthy and, for me, hard to follow, and this should only take maybe ~100 lines of code. – Adam Feb 27 '13 at 05:49
  • +1 for the answer from me because I think it's a good answer. That's exactly what's missing and that's exactly the problem a beginner faces trying to implement expression evaluation himself. – ATrubka Feb 27 '13 at 05:54
0

If the other answer seems too complicated for your project I suggest you try integrating Groovy script engine in your code. It can do all that and much more with ease.

It also allows you to compile on the fly to java classes if you need it to work as fast as a java code instead of parsing expressions yourself.

http://groovy.codehaus.org/

ATrubka
  • 3,982
  • 5
  • 33
  • 52