How to count number of arguments of a method while converting infix expression to reverse polish notation

Question

I have an expression like below. MIN(MAX(AVG(AVG(4,2),2,3),SUM(1,2))) I have implemented shunting yard algorithm to convert infix to reversed polish notation. I add the function MAX , MIN and AVG with two arguments. But suppose if I want to implement variable arguments then I must know how many arguments each function had in infix expression. Can someone tell me how could I modify the shunting yard algorithm to include no. of arguments of each function while converting infix to rpn ?

Answer 1

So if you have log max(1, 2, 3, 4, 5) you will do:

log => push log to stack
max => push max to stack
( => push ( to stack
1 => push 1 to stack
, => pop top of stack to output => pop 1 to output
2 => push 2 to stack
, => pop 2 to output
...
=> end result: 1 2 3 4 5 max log

The problem is that you don't know how many arguments belong to max and how many to log (the logarithm may or may not take the base as an argument as well).

Using the wikipedia description, it should be possible to count each function argument separator (a comma): if you have k function separators, then you have k + 1 arguments, so you could output a 1 2 3 4 5 max_5 log above. Be careful to have different counts in the case of nested functions:

max(1, 2, log(3, 4), 5) => 1 2 3 4 log_2 5 max_4
                               ---------
             max has 4 arguments after evaluating log_2(3, 4)

You'd have one count for the max token and another for the log function. You need to keep track of the count for the topmost function token in your stack, but also for all the other function tokens in your stack, as you might resume those counts eventually.

Answer 2

This is how I finally did. When the token is an open parenthesis , I add it to the output queue. Then, when converting or executing the RPN output, and I encounter a function call token, I pop items from the stack until I encounter an open parenthesis , discard it, and consider everything in between to be an argument to the function.

Probably not a neat solution but worked like a charm :)