Home Original page

Implementing a fixed size stack for an RPN Calculator

Diez B. Roggisch deets at nospam.web.de
Thu Sep 13 03:39:14 EDT 2007 
rami.mawas at gmail.com schrieb:
> On Sep 12, 2:55 pm, Marc 'BlackJack' Rintsch <bj_... at gmx.net> wrote:
>> On Wed, 12 Sep 2007 20:55:22 +0000, rami.ma... at gmail.com wrote:
>>> I have implemented an RPN calculator in python but now I would like to
>>> make the stack size fixed. how can I transform the user's RPN
>>> expression from a stack overflow to a computable expression.
>>> For instance, if my stack size is 2 then the some expression can't be
>>> computed but could be transformed as following:
>>> Non computable expression: 1 2 3 + +   --> stack size of 3 is needed
>>> Computable expression: 1 2 + 3 +         --> stack size of 2 is needed
>>> How can I define a formal way of transforming the non computable
>>> expression to computable one.
>>> My RPN only implements: + - x %
>> Why does this homework assignment limit the stack so severely!?  ;-)
>>
>> Ciao,
>>         Marc 'BlackJack' Rintsch
> 
> 
> The problem is not with the stack being severely small or not, it
> could be 1000 but it should be fixed and that's the limitation.

It can't be fixed. You can algebraic rewrite expressions of the form

(a + (b + (c + d))

because of the commutativity of the +-operation to

(a+b) + (c + d)

and this can be done automatically.

But for arbitrary expressions, you will _always_ need arbitrary stack-sizes.

Diez
More information about the Python-list mailing list