如何在将中缀表达式转换为逆波兰表达式的过程中计算方法的参数数量

Question

我有一个以下的表达式： MIN(MAX(AVG(AVG(4,2),2,3),SUM(1,2))) 我已经实现了逆波兰表达式中缀转换的shunting yard算法。 我已经添加了带有两个参数的MAX，MIN和AVG函数。但是，如果我想要实现可变数量的参数，则必须知道每个函数在中缀表达式中有多少个参数。 有人能告诉我如何修改shunting yard算法来包括每个函数的参数数量而将中缀表达式转换为逆波兰表达式吗？

- Bankelaal

Answer 1

因此，如果您有log max(1, 2, 3, 4, 5)，则需要执行以下操作：

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

问题在于你不知道有多少参数属于max，有多少参数属于log（对数函数可能会带上底数作为参数，也可能不带）。使用wikipedia description，可以计算每个函数参数分隔符（逗号）的数量：如果你有k个函数分隔符，则你有k + 1个参数，因此你可以输出一个1 2 3 4 5 max_5 log。请注意，在嵌套函数的情况下要有不同的计数：

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)

你需要为max和log函数令牌分别计数。你需要跟踪栈中最顶层函数令牌的计数，同时也需要跟踪栈中所有其他函数令牌的计数，因为你可能会最终恢复这些计数。

- IVlad

Answer 2

这是我最终的做法。当令牌是一个左括号时，我将其添加到输出队列中。然后，在转换或执行逆波兰表达式输出时，如果遇到函数调用令牌，我将从堆栈中弹出项，直到遇到一个左括号为止，将其丢弃，并将括号内的所有内容视为函数的参数。可能不是一种漂亮的解决方案，但效果很好 :)

- Bankelaal

Answer 3

一种稍微更整洁的解决方案是创建另一个堆栈。在找到开括号时，在此堆栈上推入当前标记位置。然后，当找到闭括号时，弹出第一个值并使用当前标记位置之间的差异来查找括号之间的参数总数。如果运算符是一个函数，那么你可以使用这个值，否则就可以将其丢弃。

- Drgabble

Answer 4

我不确定我会将开括号推到输出栈中。这意味着您将在像3 *（4 + 5）这样的操作中向堆栈添加括号。 相反，我会将逻辑与函数关联起来：当您遇到MAX或MIN时，请将标记令牌（比如“|”）推送到堆栈中。现在，在评估时，您可以使用第一个“|”之前堆栈上的所有项目作为函数的参数。

- Clive Pottinger