c# - 如何为包含带有可选参数的函数的表达式构建和评估后缀堆栈

Question

例如：

3 + 4 * max(2, avg(6, 8, 2, 4,...), 6, ...)

我的第一个想法是创建一个特殊的标记，它是参数的计数，并在遇到“）”时将其推入堆栈。但是我不确定当参数本身可能是带参数的函数时如何保持计数。

Answer 1

我通过稍微修改 Shutting-yard 算法并在任何前缀操作之后立即将特殊标记（称为 @）插入到输出堆栈中解决了这个问题。

例如：4 * max(2, avg(6, 8), 32) + 3 将生成一个输出堆栈： + 3 * Max 32 Avg 8 6 @ 2 @ 4

当从左到右评估这个堆栈时，函数 Avg 将知道当它似乎是第一个 @ 标记时停止弹出操作数，函数 max 也将知道。