polish stack

Discussion in 'Java' started by Mr. X., May 10, 2008.

  1. Mr. X.

    Mr. X. Guest

    Hello,
    I am looking for a Java source code for Polish Stack, please.
    A Polish Stack - A Stack algoritm, that is usefull for developing a tool for
    computing basic formulas, with priority.
    i.e a formula :
    2 + 3 x 5 = 17 (and not 25, because x is perior to +)
    The function that evaluate this can be done by some recrusive statements
    (which I don't preffer), or by polish-stack.

    If there is no source code :
    What is the concept of polish stack ?

    Thanks :)
    Mr. X., May 10, 2008
    #1
    1. Advertising

  2. Mr. X.

    Roedy Green Guest

    On Sat, 10 May 2008 14:46:26 +0300, "Mr. X."
    <no_spam_please@nospam_please.com> wrote, quoted or indirectly quoted
    someone who said :

    >What is the concept of polish stack ?


    Google for "postfix notation" . Read up on how FORTH works.
    --

    Roedy Green Canadian Mind Products
    The Java Glossary
    http://mindprod.com
    Roedy Green, May 10, 2008
    #2
    1. Advertising

  3. Mr. X. wrote:
    > Hello,
    > I am looking for a Java source code for Polish Stack, please.
    > A Polish Stack - A Stack algoritm, that is usefull for developing a tool for
    > computing basic formulas, with priority.
    > i.e a formula :
    > 2 + 3 x 5 = 17 (and not 25, because x is perior to +)
    > The function that evaluate this can be done by some recrusive statements
    > (which I don't preffer), or by polish-stack.


    It is generally inadvisable to ask for exact source code in forums--many
    people here would be willing to consult with you for the going rate of
    $X/hour (or other relevant currency).

    Google proves useful here:
    <http://en.wikipedia.org/wiki/Shunting_yard_algorithm> tells you what
    you need to do.

    > If there is no source code :
    > What is the concept of polish stack ?


    Polish or reverse-polish notation (the latter tends to be more commonly
    used) is better for computers to work with than infix notation, because
    it doesn't requires parenthesis to operate, and because computation is a
    simple stack-based algorithm. The "Polish Stack," I am inferring, is the
    stack of numbers generated in such an algorithm.

    --
    Beware of bugs in the above code; I have only proved it correct, not
    tried it. -- Donald E. Knuth
    Joshua Cranmer, May 10, 2008
    #3
  4. Mr. X.

    Jeff Higgins Guest

    Mr. X. wrote:
    > Hello,
    > I am looking for a Java source code for Polish Stack, please.
    > A Polish Stack - A Stack algoritm, that is usefull for developing a tool
    > for computing basic formulas, with priority.


    Settle for a reverse polish stack?
    <http://preview.tinyurl.com/648qo4>

    > i.e a formula :
    > 2 + 3 x 5 = 17 (and not 25, because x is perior to +)
    > The function that evaluate this can be done by some recrusive statements
    > (which I don't preffer), or by polish-stack.


    <https://javacc.dev.java.net/> or <http://www.ssw.uni-linz.ac.at/coco/>
    or <http://www.singularsys.com/jep/>

    >
    > If there is no source code :
    > What is the concept of polish stack ?


    <http://en.wikipedia.org/wiki/Stack_(data_structure)>
    Jeff Higgins, May 10, 2008
    #4
  5. Mr. X.

    Roedy Green Guest

    On Sat, 10 May 2008 14:46:26 +0300, "Mr. X."
    <no_spam_please@nospam_please.com> wrote, quoted or indirectly quoted
    someone who said :

    >2 + 3 x 5 = 17 (and not 25, because x is perior to +)

    ( 2 + 3 ) * 4 would be written in postfix as
    2 3 + 4 *


    imagine a stack at these various stages during execution

    -
    -------

    2

    ------

    3
    2

    -------

    5

    -------

    4
    5

    -------

    20


    So your + operator looks at the top two elements of the stack adds
    them and replaces the operands with the result.
    --

    Roedy Green Canadian Mind Products
    The Java Glossary
    http://mindprod.com
    Roedy Green, May 10, 2008
    #5
  6. Mr. X.

    Roedy Green Guest

    On 10 May 2008 13:32:58 GMT, "Kenneth P. Turvey"
    <> wrote, quoted or indirectly quoted
    someone who said :

    >Not just computers. I like my calculators to work this way. It really
    >is much easier once you get used to it.


    Quite right . Once you get used to it, postfix is so clear without 20
    layers of precedence rules, and you can store intermediate results so
    easily during a calculation for later use. Had we started out with
    postfix in school, infix notation would seem baroque.

    In a similar way, had you started out with metric in school, American
    measure would have seemed impossibly quaint.

    --

    Roedy Green Canadian Mind Products
    The Java Glossary
    http://mindprod.com
    Roedy Green, May 10, 2008
    #6
  7. Kenneth P. Turvey wrote:
    > On Sat, 10 May 2008 13:41:22 +0000, Roedy Green wrote:
    >> In a similar way, had you started out with metric in school, American
    >> measure would have seemed impossibly quaint.

    >
    > Still does..
    >
    > One thing that has always given me an itch though is our measurement of
    > time. In everything else the metric system switches to a nice decimal
    > system, but time.. no such thing.
    >
    > It is awfully convenient to have years and days line up correctly, but
    > months, hours and minutes?
    >
    > Our system of time seems antiquated. Certainly there are better units
    > for the measurement of the passage of time.


    Something in time could be changed, but other characteristics is
    given. A day is the time it takes the earth to rotate around itself.
    A year is the time it takes the earth to rotate around the sun. We
    can't tell the earth to male that 1000 days per year instead of those
    365.25 !

    Arne
    Arne Vajhøj, May 10, 2008
    #7
  8. Mr. X.

    Mr. X. Guest

    ....
    How can I translate from 2 + (3 x 5) to something in stack as :
    3,5,x,2,+ ?

    .... with O(N) at maximum, where N is the number of elements,
    with no recrusive algoritm ?

    Thanks :)
    Mr. X., May 10, 2008
    #8
  9. Mr. X.

    Arne Vajhøj Guest

    Mr. X. wrote:
    > ...
    > How can I translate from 2 + (3 x 5) to something in stack as :
    > 3,5,x,2,+ ?
    >
    > ... with O(N) at maximum, where N is the number of elements,
    > with no recrusive algoritm ?


    It should be:

    2 3 5 * +

    and the algorithm should be in most beginner books on
    algorithms.

    Arne
    Arne Vajhøj, May 10, 2008
    #9
  10. "Kenneth P. Turvey" <> wrote in message
    news:4825c868$0$25758$...
    > On Sat, 10 May 2008 13:41:22 +0000, Roedy Green wrote:
    >
    >
    >> In a similar way, had you started out with metric in school, American
    >> measure would have seemed impossibly quaint.

    >
    > Still does..
    >
    > One thing that has always given me an itch though is our measurement of
    > time. In everything else the metric system switches to a nice decimal
    > system, but time.. no such thing.
    >
    > It is awfully convenient to have years and days line up correctly, but
    > months, hours and minutes?
    >
    > Our system of time seems antiquated. Certainly there are better units
    > for the measurement of the passage of time.


    Calculating the number of milliseconds before or since Jan 01, 1970 GMT
    seems quite workable. Then you only need to convert to and from local clock
    time for input and display.
    Chronic Philharmonic, May 10, 2008
    #10
  11. "Kenneth P. Turvey" <> wrote in message
    news:4825a40a$0$30073$...
    > On Sat, 10 May 2008 12:08:56 +0000, Joshua Cranmer wrote:
    >
    >> Polish or reverse-polish notation (the latter tends to be more commonly
    >> used) is better for computers to work with than infix notation, because
    >> it doesn't requires parenthesis to operate, and because computation is a
    >> simple stack-based algorithm.

    > [Snip]
    >
    > Not just computers. I like my calculators to work this way. It really
    > is much easier once you get used to it.


    Yup. I never use the parenthesis on infix notation calculators because I
    never can seem to match the open-parens with the close-parens. Whenever I
    have serious mathematical calculation to do, I get out my trusty HP11, or my
    HP32S II.
    Chronic Philharmonic, May 10, 2008
    #11
  12. "Lew" <> wrote in message
    news:...
    > Kenneth P. Turvey wrote:
    >> On Sat, 10 May 2008 12:34:51 -0400, Arne Vajhøj wrote:
    >>
    >>> Something in time could be changed, but other characteristics is given.
    >>> A day is the time it takes the earth to rotate around itself. A year is
    >>> the time it takes the earth to rotate around the sun. We can't tell the
    >>> earth to male that 1000 days per year instead of those 365.25 !

    >>
    >> That's certainly true, but does it really make sense for us to have 24
    >> hour days, 60 minute hours and 60 minute seconds? Why not 10 hour days,
    >> 10 minute hours, and 10 second minutes or something similar? Do we
    >> really need every day to start at the same time anymore? It is certainly
    >> convenient, but is there another way to get that convenience without
    >> screwing up our units of measure? Couldn't days just be fractions of a
    >> year, which is what they really are anyway. I don't know. It just seems
    >> like people just decided to ignore time when they developed the metric
    >> system.

    >
    > Sixty is a better number base than ten anyway. We should use
    > sexagintesimal (exekontesimal?) arithmetic for everything.


    That's a lot of symbols to keep track of. Even our alphabet has only 26,
    give or take a few. While the Chinese alphabet has more discrete symbols,
    but they aren't exactly distinct in the same way as Western symbols are.
    Chronic Philharmonic, May 11, 2008
    #12
  13. Mr. X.

    Guest

    On May 10, 5:49 pm, "Kenneth P. Turvey" <>
    wrote:
    > That's certainly true, but does it really make sense for us to have 24
    > hour days, 60 minute hours and 60 minute seconds?  Why not 10 hour days,
    > 10 minute hours, and 10 second minutes or something similar?  
    >
    > Do we really need every day to start at the same time anymore?  It is
    > certainly convenient, but is there another way to get that convenience
    > without screwing up our units of measure?  Couldn't days just be
    > fractions of a year, which is what they really are anyway.  
    >
    > I don't know.  
    >
    > It just seems like people just decided to ignore time when they developed
    > the metric system.


    At the time of the French revolution, when the metric system was
    invented, France for a while (The last vestiges were abandoned in
    1805.) went to 10 hours per day, 100 minutes per hour and 100 seconds
    per minute. The resulting second, with 100,000 of them from noon to
    noon, was a little shorter than the conventional second (86,400
    seconds from noon to noon). There were also 12 metric months per year,
    3 weeks per month, 10 days per week.

    --Mike Amling
    , May 12, 2008
    #13
  14. Mr. X.

    Mr. X. Guest

    Please help me.
    At least how do you get to (the rest is obvious)
    > 2 3 5 * +

    .... and I didn't find something on the internet.

    I whould like whether you can lead me to some source, please.

    Thanks :eek:)
    Mr. X., May 18, 2008
    #14
  15. Mr. X.

    Mr. X. Guest

    Also,
    I need explain what is the representation of (for example) ;
    9+3+4*5-2 ?

    Thanks :)
    Mr. X., May 18, 2008
    #15
  16. Mr. X.

    Arne Vajhøj Guest

    Mr. X. wrote:
    > I need explain what is the representation of (for example) ;
    > 9+3+4*5-2 ?


    9 3 + 4 5 * + 2 -

    Arne
    Arne Vajhøj, May 18, 2008
    #16
  17. Mr. X.

    Arne Vajhøj Guest

    Mr. X. wrote:
    > Please help me.
    > At least how do you get to (the rest is obvious)
    >> 2 3 5 * +

    > ... and I didn't find something on the internet.
    >
    > I whould like whether you can lead me to some source, please.


    I think your Google is broken.

    Mine has 32000 hits on:

    convert infix postfix

    Arne
    Arne Vajhøj, May 18, 2008
    #17
  18. Mr. X.

    Mr. X. Guest

    Hi,

    I don't have book of polish-stack, and I won't buy any,
    If you don't want to answer - please, don't answer at all.
    I just want to know the concept in details !
    I have tried a lot searching google, but it seems that I found my own
    questions,
    or answers that are after the transform to 95+ ... (and not 9 + 5)

    1. How do I get it from 9+3+4*5-2 to any kind of : 9 3 + 4 5 * + 2 - ?
    --- > I suppose, the concept is to run from left to right arguments,
    put values to stack, and put operator to stack, but if current operator's
    priority is higher then previous,
    then wait it to be put at the next step.
    so for 9 + 3 + 4 * 5, the sequence is 9, 3, + (now 4 has * operator which
    its priority is higher, so I wait ...),
    ten 4,5,* ... (something like that ...).
    I didn't see any clue of that algorithm, so I suppose that's right (Is that
    true ?)
    2. Any free java code somewhere of that algorithm, it will be fine.

    Thanks :)
    Mr. X., May 18, 2008
    #18
  19. Mr. X.

    Mr. X. Guest

    ....
    Also, what I think (only guess) :
    there are two stacks :
    1 - stack of arguments (let call it : SA)
    2 - stack of operators (let call it : SO).

    We always push on stack.
    We pop from stack, only at end of formula, or when we reach an operator at
    the same priority or less then current priority.
    The 1st 2nd arguments are operated by the 1st argument.
    When pop from stack - we pop from the last argument of the stack (LIFO).

    9+3+4*5-2

    SA:9
    SO:<empty>

    SA:9
    SO:+

    SA:9,3
    SO:+

    (there is no another operand, so we keep pushing on stack).

    SA:9,3
    SO:+,+

    (now we can pop the lasts : 9,3 with +, and push the result again into
    stack)

    SA:12
    So:+

    SA:12,4
    SO:+

    (there is no next argument, so we're keep trying).

    SA:12,4
    SO:+,*

    SA:12,4,5
    SO:+,*

    SA:12,4,5,
    SO:+,*,-

    (now the priority is downed so we pop the last arguments : 4,5, with
    corresponding operator : *, and push back to stack).

    SA:12,20
    SO:+,-

    SA:32
    SO:-

    SA:32,2
    SO:-

    <end>
    SA:30
    SO:<empty>

    Stack is empty, so we pop the result on argument : SA.
    result = 30 !

    The same thing can be for brakes "(" with a higher priority no. (I can mark
    for each element it's priority, by some kind of method :
    when priority get higher, I increment the priority counter, when it getting
    lower I decrement the priority counter, and every time, and due that I know
    how can I handle the stack as I have described above.

    Is the above right thorey ?
    If the above is right, I think I'll mange...

    Thanks :)
    Mr. X., May 18, 2008
    #19
  20. Mr. X.

    Mr. X. Guest

    No, No !!!
    Mr. X., May 18, 2008
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. schapopa

    OuterHTML - loosing polish fonts

    schapopa, Jan 24, 2005, in forum: ASP .Net
    Replies:
    0
    Views:
    330
    schapopa
    Jan 24, 2005
  2. schapopa

    OuterHTML - loosing polish fonts

    schapopa, Jan 24, 2005, in forum: ASP .Net
    Replies:
    0
    Views:
    373
    schapopa
    Jan 24, 2005
  3. ron
    Replies:
    1
    Views:
    892
    Stewart Gordon
    Jul 2, 2003
  4. declan
    Replies:
    0
    Views:
    471
    declan
    Feb 25, 2004
  5. Replies:
    2
    Views:
    742
    Oliver Wong
    Feb 6, 2006
Loading...

Share This Page