c - 后缀表达式求值 : how much stack memory is required?

Question

我觉得这是一个非常愚蠢的问题，但我找不到答案。

假设我们要计算一个后缀表达式，其中包含具有不同元数的各种运算符(例如 ADD、SUB 和其他可以采用 N 个操作数的运算符)。评估使用这些运算符构建的后缀表达式需要多少堆栈内存(根据元素数量)？

有没有办法确定所需的内存量？

编辑:看来这个问题有点模棱两可。我要问的是，这种操作需要的堆栈元素的最大数量是多少？它甚至可以计算出来还是可以无限多并且取决于表达式？

Answer 1

这取决于表达式。二进制表达式的经典递归解决方案类似于(在 C 代码中):

int maxstack(expression *exp) {
    if (IsLeaf(exp)) {
        return 0;
    } else {
        int left_stack = maxstack(exp->left);
        int right_stack = maxstack(exp->right);
        if (left_stack == right_stack)
            return left_stack + 1;
        else if (left_stack > right_stack)
            return left_stack;
        else
            return right_stack;
    }
}

将其扩展到三元/二元表达式相对简单