Prefix Expressions

[HankReardon]

Hello Friends,

I am having trouble with a homework assignment and was wondering if you would please take a look at it for me.

I have to write a program that receives a prefix expression. Then it calculates and displays the result. It does this by using a stack to store values of sub-expressions as they are computed, and
another stack to store operators that have not yet been applied.

Does this mean that I have to have a stack for the results of the subexpressions and then a stack for each subexpression that has not been solved yet?

So I will have 1 stack of sub expressions before each is solved. Once the stack is made I can begin solving the subexpressions in the stack. I will solve the last one first and put the result in a new stack. I will solve the second to last one next and put the result on top of the same stack. I will do this to all sub expressions inside the stack. Once this is done I will begin working on all of the results in the second stack. Once the second stack is finished I will have the answer to the prefix expression.

Does this look correct?

Thank you,
Hank

S

[bguild]

You don't need to store subexpressions on a stack. You can do this with just a stack for values and a stack for (operator, arity) pairs. It would be nice to use simply a stack of operators, but you need some way to remember when each operator should be applied, so I imagine a class something like this:

final class PartiallyAppliedOperation {
    /** The operation to perform once all the arguments are in */
    public final Operator operator;
    /** The number of arguments still needed */
    private int arity;
    public PartiallyAppliedOperation(Operator op) {
        operator = op;
        arity = op.getArity();
    }
    public boolean needsArguments() { return arity > 0; }
    public void decrementArity() {
        if(arity <= 0) throw new IllegalStateException();
        else arity--;
    }
}

Now you can read your prefix expression and every time you find an operator you create a PartiallyAppliedOperation and push it onto the operator stack. Every time you find an operand you push it onto the value stack, then take the top PartiallyAppliedOperation of the operand stack and decrement its arity. When the arity of the top operation becomes zero you pop it off the stack and pop as many arguments as you need off the value stack, then perform the operation and push the result onto the value stack, decrementing the arity of the new top of the operation stack.

[HankReardon]

Thank you.