1

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)?

  • 1
    It's been quite a while since I had to implement shunting yard, so just a guess. Can you handle `!x` as if it was `@ ! x` where `@` is a placeholder that's ignored by the operation? – bereal Aug 06 '20 at 10:58
  • you mean like the unary -x can be written as 0-x? @bereal –  Aug 06 '20 at 11:10
  • if that is what you mean then the answer is no ! is a little bit complicated here –  Aug 06 '20 at 11:17
  • Here: https://stackoverflow.com/questions/1593080/how-can-i-modify-my-shunting-yard-algorithm-so-it-accepts-unary-operators someone mentioned treating it as right associative even though it's left, is that right? –  Aug 06 '20 at 11:19

1 Answers1

0

Question 1:

In order to make your algorithm work you should parse the prefix operator ! before the infix operators, simply treating it as if it was an open parenthesis ( (then you need to tweak the stack virtual machine to allow this kind operator). I suggest moving the if check for the parenthesis before the infix operator (it doesn't change much but it's more readable). I will also say that if you want to achieve things like operator precedence, postfix operators and mixfix operators all together you should switch to a Pratt parser (which is much easier to work with).

Question 2:

The parser here doesn't deal with operations like 1 == 2, it only parses them. The stack based virtual machine deals with them and 1 == 2 is a completely fine comparison since it is supposed to return false. This if you plan to have boolean expressions as well as arithmetic expressions.

EDIT 1:

The "tweak" (which partially solves the issue): consider the operator as right associative and make its precedence higher than the other operators.

EDIT 2:

This (as pointed out in the comments by @dure) is just a tweak, since il will cause the parser to parse prefix and postfix operators without distinction and needs further care to avoid bugs.

Cristian
  • 654
  • 1
  • 13
  • 30
  • To sum up I was given two different solutions: 1) to give the operator an advantage and consider it as right associative (even though it's left) - kindly see the link in comments- 2) treating them as normal. which is right? –  Aug 06 '20 at 11:26
  • @daniel yes, the first answer given in the link you provided is correct, you should consider it as right associative and make its precedence higher than the other operators. However, this is more of a "tweak" than a solution. As I said, you should switch to a more advanced parser that lets you deal with everything by default. – Cristian Aug 06 '20 at 11:31
  • @Cristian the given answer is wrong, for example take a! and !a both will be treated the same even though one is correct and the other isn't –  Aug 08 '20 at 22:46
  • @dure Yes I know, but as I said this is more of a tweak to make it work, don't expect to have great results. If you want more control over operators and precedence I suggested a different type of algorithm. – Cristian Aug 10 '20 at 09:38