Search code examples
cstacktheorypostfix-notation

Postfix expression evaluation: how much stack memory is required?

I feel like this is a very dumb question but I could not find the answer.

Suppose that we want to evaluate a postfix expression which contains various operators with different arity (for example ADD, SUB, and other operators that can take N number of operands). How much stack memory (in terms of number of elements) is required to evaluate a postfix expression built with these operators?

Is there a way to determine the amount of memory that is required?

EDIT: It seems that the question is a bit ambiguous. What I am asking is, what is the maximum number of stack elements that I need for this kind of operation? Can it even be calculated or it could be infinitely many and depends on the expression?

Solution

  • It depends on the expression. The classical recursive solution for a binary expression is something like (in C code):

    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;
    }
}

    extending this to trinary/nary expressions is relatively straight-forward