I have implemented shunting yard algorithm in C++11 according to what is mentioned in wikipedia:
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.
else if the token is a function then:
push it onto the operator stack
else if the token is an operator then:
while ((there is a operator at the top of the operator stack)
and ((the operator at the top of the operator stack has greater precedence)
or (the operator at the top of the operator stack has equal precedence and the token is left associative))
and (the operator at the top of the operator stack is not a left parenthesis)):
pop operators from the operator stack onto the output queue.
push it onto the operator stack.
else if the token is a left parenthesis (i.e. "("), then:
push it onto the operator stack.
else if the token is a right parenthesis (i.e. ")"), then:
while the operator at the top of the operator stack is not a left parenthesis:
pop the operator from the operator stack onto the output queue.
/* If the stack runs out without finding a left parenthesis, then there are mismatched parentheses. */
if there is a left parenthesis at the top of the operator stack, then:
pop the operator from the operator stack and discard it
/* After while loop, if operator stack not null, pop everything to output queue */
if there are no more tokens to read then:
while there are still operator tokens on the stack:
/* If the operator token on the top of the stack is a parenthesis, then there are mismatched parentheses. */
pop the operator from the operator stack onto the output queue.
exit.
As you can see it's mentioned that this algorithm doesn't deal with unary operator, suppose I have one !
which is stronger than all other operator, what changes should I make to my algorithm if any?
Some Legal Examples of using !
operator:
!1
! 1
! (1)
!( 1 + 2)
Plus one small question, does this algorithm deal with wrong syntax like 1==2
(I supposed that yes it does)?