Implementing a fixed size stack for an RPN Calculator

[rami.mawas]

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 %

 

[Marc 'BlackJack' Rintsch]

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

 

[rami.mawas]

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.

 

[Dennis Lee Bieber]

Why does this homework assignment limit the stack so severely!? ;-)

Yeah... a two-place stack ain't a stack <G>

Even a late-70s HP-25 had a four-place stack (with automatic repeat
of the "top" element)

The whole "feature" of RPN (to me) was that one was not supposed to
really need to determine the computation order -- as is needed with
algebraic calculators that don't have multiple () capability).

This apparent assignment seems to be asking for a means of taking a
true, unlimited, RPN expression, converting it to algebraic (with
parens), then parsing the algebraic back into two-place RPN by
evaluating the parenthetical's first... But even THAT will fail -- a
two-place RPN cannot even resolve 1 2 * 3 4 * + (which requires a
three-place stack). The matching algebraic is (1 * 2) + (3 * 4) {or,
since * takes priority over +, a simple 1 * 2 + 3 * 4 -- from my college
days, "compiled" as

value-stack operator-stack
1 null
*
2 1 *
pending + is lower priority, do *
2 null
2 +
3 2 +
* is higher priority, stack it
3 2 * +
4 3 2 * +
end of expression, pop/execute
12 2 +
14 null

A three-place value stack, and a two place operator stack. Notice
how the operator stack actions would generate a variation of the RPN:

2 1 * 4 3 * +

Obviously, / and - would have operate "backwards" (subtracting
"first" from "second" -- but that's an implementation detail).

In the case of: 1 2 3 + + it would have to be translated to
algebraic: 1 + 2 + 3 and then parsed into RPN:

1 null
1 +
2 1 +
pending + is equal priority, execute stacked
3 null
3 +
3 3 +
end of expression, execute
6 null


Of course, the unrestricted RPN to algebraic requires an
unrestricted stack to parse, and then one needs at least a three place
stack -- assuming only TWO levels of operator precedence exist in the
grammar.


--
Wulfraed Dennis Lee Bieber KD6MOG
(e-mail address removed) (e-mail address removed)
HTTP://wlfraed.home.netcom.com/
(Bestiaria Support Staff: (e-mail address removed))
HTTP://www.bestiaria.com/

 

[Diez B. Roggisch]

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