Modify the Shunting Yard Algorithm to include a wall operator |

1
votes

How would the standard Shunting Yard Algorithm be modified to include a 'wall' symbol, |, representing the end of the function parameters? That is, to support a modification of postfix notation (Reverse Polish Notation) which allows functions with arbitrary numbers of parameters.

A couple of examples of the modified postfix notation:

f(1,2)+9 ⟶ | 1 2 f 9 +
f(1,2,3)+9 ⟶ | 1 2 3 f 9 +

Please, I'm looking for the actual modifications, not just ideas on how to do it.

Shunting Yard Algorithm

  1. While there are tokens to be read:
  2. Read a token.
  3. If the token is a number, then push it to the output queue.
  4. If the token is a function token, then push it onto the stack.
  5. If the token is a function argument separator (e.g., a comma):
    • Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue. If no left parentheses are encountered, either the separator was misplaced or parentheses were mismatched.

  6. If the token is an operator, o1, then:

    • while there is an operator token o2, at the top of the operator stack and either

      • o1 is left-associative and its precedence is less than or equal to that of o2, or

      • o1 is right associative, and has precedence less than that of o2,

        -pop o2 off the operator stack, onto the output queue;

      • at the end of iteration push o1 onto the operator stack.
  7. If the token is a left parenthesis (i.e. "("), then push it onto the stack.
  8. If the token is a right parenthesis (i.e. ")"):
    • Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue.
    • Pop the left parenthesis from the stack, but not onto the output queue.
    • If the token at the top of the stack is a function token, pop it onto the output queue.
    • If the stack runs out without finding a left parenthesis, then there are mismatched parentheses.
  9. When there are no more tokens to read:
    • While there are still operator tokens in the stack:
      • If the operator token on the top of the stack is a parenthesis, then there are mismatched parentheses.
      • Pop the operator onto the output queue.
  10. Exit.
1
algorithmpostfix-notationshunting-yard
How do you know that f is a function? Eg., Suppose the input is | | a b c d Is it d(c(a,b)) or d(b(a), c)? – rici
Sorry, please assume f has been previously identified as a function. Further, there are no variables in the input infix expression, just numbers. – bitsmcgee77
Ok. I would usually do a function call by outputting function, the arguments, then the count of arguments and finally a call operator. But if you can tell that f is a function, I think that will work. – rici

1 Answers

0
votes

The solution:

In step 4, in addition to pushing the function to the stack, write the | symbol to the output postfix expression.

Of course, the algorithm that evaluates this modified postfix expression must itself be modified to account for the wall symbol.