Remember that time when I didn’t know what I was doing? Remember that I used to do my “code” in C++? Remember how I wanted to figure out how to make a program that parsed mathematical input in infix notation, then raged about how I couldn’t for the life of me think of how to handle parentheses, yet somehow, just a while later, came up with a solution that worked?

Disregarding the fact that I still haven’t uploaded that program anywhere and that it’s on a laptop that may break any time soon and, indeed, that I don’t even know where it’s saved on said laptop, I have begun work on a Java version of that program, except the user will now be able to input his/her expression in a GUI.

The only difference between my shabbily cobbled-together C++ parser, this one actually uses a slightly less improvised method, namely the shunting-yard algorithm. So far, I have been able to make at least half of the program; it can turn a no-space string of numbers, operators and parentheses/brackets into an array of strings in reverse Polish notation.

It may not be the most efficient way of implementing it, but my class is pretty cool. It even has a private inner class and stuff for fetching the next token! Okay, perhaps that’s not really the greatest feat ever, but I still like how it turned out.

REMEMBER: IT’S STILL A HELL OF A LOT BETTER THAN THAT ABSOLUTE MESS I MADE LAST TIME I TRIED DOING SOMETHING LIKE THIS.

Anyway, here are some examples of outputs returned by the shunting-yard interpreter or whatever one should name it:

Input: "3+5*(2+3-(3*4/2+4))" Output: 3 5 2 3 3 4 2 / * 4 + - + * + Input: "20*33-(2+4-6*2)" Output: 20 33 * 2 4 6 2 * - + - Input: "3*4+2^3*5-3^2" Output: 3 4 * 2 3 ^ 5 * 3 2 ^ - + Input: "3+4*(1+2^2+3^3-(5*3^3)^2)" Output: 3 4 1 2 2 ^ 3 3 ^ 5 3 3 ^ * 2 ^ - + + * + Input: 2^(1+2+3^(1+2-2))-2^5 Output: 2 1 2 3 1 2 2 - + ^ + + ^ 2 5 ^ - Input: 2^(10/(5+10-5^1)*(3+4-(4-2)))/(3*4^5+2)*(3+5^3) Output: 2 10 5 10 5 1 ^ - + / 3 4 4 2 - - + * ^ 3 4 5 ^ * 2 + / 3 5 3 ^ + *

Let’s break this down:

- The user inputs, e.g., “3+5*(2+3-(3*4/2+4))” in some input field somewhere.
- The shunting-yard algorithm I wrote breaks this down into a simple array of numbers and operators.
- The array is output elementwise.

As an example, here’s how this algorithm works in the first case:

Input:"3+5*(2+3-(3*4/2+4))" 1. Read first input character. This is a number. Check if next index is also a number. It isn't. 2. Add this number to the output array. 3. Read the next input character. This is an operator. Check if there are other operators in the operator array. There aren't. 4. Add this operator to the operator array. 5. Read next input character. This is a number. Check if next index is also a number. It isn't. 6. Add this number to the output array. 7. Read the next input character. This is an operator. Check if there are other operators in the operator array. There are. Check if the operator has a higher precedence than the last operator in the operator array. It does. 8. Add this operator to the operator array. 9. Read the next input character. This is an opening bracket. Add it to the operator array. 10. ... Add "2" to the output array. 11. ... Add "+" to the operator array. 12. ... Add "3" to the output array. 13. ... Add "-" to the operator array. 14. ... Add "(" to the operator array. 15. ... Add "3" to the output array. 16. ... Add "*" to the operator array. 17. ... Add "4" to the output array. 18. ... Add "/" to the operator array. 19. ... The operator "+" has a lower precedence than the operator currently the last operator ("/"). Therefore, move "/" to the output array, then add "+" to the operator array as the new operator of highest precedence. 20. ... Add "4" to the output array. 21. ... The operator ")" is a closing bracket. Add all entries in the operator array from the top down to the output array until a closing bracket is encountered. 22. Remove both brackets. 23. ... The operator ")" is a closing bracket. Add all entried in the operator array from the top down to the output array until a closing bracket is encountered. 24. Remove both brackets. 25. END OF INPUT; add remaining operators in the operator array from the top down to the output array. 26. ALGORITHM END. Output: 3 5 2 3 3 4 2 / * 4 + - + * +

Then we can read the output and calculate the result as follows:

- Find the first operator.
- Take the two numbers before the operator and replace the two numbers and the operator by the result “[FIRST_NUMBER] [OPERATOR] [SECOND_NUMBER]”.

Example: 10 2 / = 10/2 = 5.

Using the above output, we get:

Output: 3 5 2 3 3 4 2 / * 4 + - + * + 1. First operator found: "/" 2. Operation: 4 2 / = 4 / 2 = 2 New array: 3 5 2 3 3 2 * 4 + - + * + 3. First operator found: "*" 4. Operation: 3 2 * = 3 * 2 = 6 New array: 3 5 2 3 6 4 + - + * + 5. First operator found: "+" 6. Operation: 6 4 + = 6 + 4 = 10 New array: 3 5 2 3 10 - + * + 7. First operator found: "-" 8. Operation: 3 10 - = 3 - 10 = -7 New array: 3 5 2 -7 + * + 9. First operator found: "+" 10. Operation: 2 -7 + = 2 + -7 = -5 New array: 3 5 -5 * + 11. First operator found: "*" 12. Operation: 5 -5 * = 5 * -5 = -25 New array: 3 -25 + 13. First operator found: "+" 14. Operation: 3 -25 + = 3 + -25 = -22 New array: -22 15. Array found to be empty; END OF COMPUTATION. FINAL RESULT: -22.

That’s pretty much how the shunting-yard algorithm works, and all I really need to do is figure out how to handle the last half of the algorithm. Well, actually, I have already done the algorithm itself; I just need to work with the output and display the answer to the input expression.

That said, this has been going on for way too long. I think it’s time to end this here. Hopefully all goes well. It sure has gone better than my last attempt.

And, yes, I did try doing this more than once in Java. In fact, I tried my old method before I found this. Seems like I need to use Google more and not refrain from looking for tips on the Internet like a wannabe-independent twonk.

Wait, I guess I ought to include some sources…

- Wikipedia article on the subject (can hardly be called a source, but w/e).
- A useful calculator I used for quick testing of the output. Helped with the debugging, especially. There is also a less useful calculator, which is less useful because it is more limited and less organized.
- Brilliant article on the shunting-yard algorithm (pun intended).