This is an interesting problem. I don't understand the full details but I might have a bash at implementing this myself. Anyway this is what I have garnered, referencing this heavily:
http://en.wikipedia.org/wiki/Shunting_yard_algorithm[
^]
"My program uses two stacks to store the numbers and operators and then evaluate (trying to use the shunting yard idea)."
If I understand correctly, this is wrong (apologies if I misunderstand). The purpose of the shunting yard is to re-write a formula so that it appear in reverse Polish notation where
3 2 + adds 3 to 2 (in general
Operand2 Operand1 Operator where the operands themselves can be evaluated bits of the function). Your formula 8*8-9 --> 9 - 8 8 * I think. Reverse Polish notation is very confusing, I have to use Polish, then reverse it if you get my meaning.
The shunting algorithm has one stack and one queue. The operator stack is really "temporary", when the algorithm is finished it should be empty. Everything should end up in the output queue rather than just the values. If you follow the algorithm correctly you get a RPN formula in the output queue without any extra work. You shouldn't go through the output queue and operator stack at the end and work through the precedences. Even if you got this working (and I don't think it is possible as you described it) it would be slower than the proper algorithm.
The algorithm is detailed in the wikipedia page, but
simplistically:
- The Next term, if it is a number push it onto the output queue.
- If the next term (an operator) has a higher precedence than the one on the operator stack() or the op stack is empty, push it to the stack. Otherwise pop the operator stack into the output queue and push the term into the operator stack
- Repeat until there are no more terms: pop each item in the operator stack into the output queue
Obviously this doesn't deal with brackets (unlike the wiki page).
[edit: I have started to implement this alogrithm, I thought the ouptut was a stack, it isn't, it is a queue. I have corrected this.]