I looked at the wiki page for shunting yard since I had a problem handling chained unary minus operators in my shunting yard, but the wiki algorithm doesn't seem to handle it.
Wiki algorithm for reference:
/* This implementation does not implement composite functions,functions with variable number of arguments, and unary operators. */
while there are tokens to be read:
read a token.
if the token is a number, then:
push it to the output queue.
if the token is a function then:
push it onto the operator stack
if the token is an operator, then:
while ((there is a function at the top of the operator stack)
or (there is an operator at the top of the operator stack with greater precedence)
or (the operator at the top of the operator stack has equal precedence and is left associative))
and (the operator at the top of the operator stack is not a left bracket):
pop operators from the operator stack onto the output queue.
push it onto the operator stack.
if the token is a left bracket (i.e. "("), then:
push it onto the operator stack.
if the token is a right bracket (i.e. ")"), then:
while the operator at the top of the operator stack is not a left bracket:
pop the operator from the operator stack onto the output queue.
pop the left bracket from the stack.
/* if the stack runs out without finding a left bracket, then there are mismatched parentheses. */
if there are no more tokens to read:
while there are still operator tokens on the stack:
/* if the operator token on the top of the stack is a bracket, then there are mismatched parentheses. */
pop the operator from the operator stack onto the output queue.
exit.
Suppose I have the following expression ---1, I expect the rpn output to be 1---, however what actually happens is the following:
iteration 1: operator stack: [] output queue: []
token to be read is a - so we push onto operator stack
iteration 2: operator stack: [-] output queue: []
token to be read is a -. There is a - on operator stack and we should pop it into output queue. We then push the token onto operator stack.
iteration 3: operator stack: [-] output queue: [-]
ERROR - we should not have a - in the output queue yet. (Not going to continue algo since pointless)
