infix to postfix expression string for evalution.

Discussion in 'C++' started by KidLogik, Feb 2, 2004.

  1. KidLogik

    KidLogik Guest

    Hello!

    I am converting an infix expression string into a postfix so that I
    will be able to evaluate it easier ->

    (5*(((9+8)*(4*6))+7)) == 598+46**7+*

    I believe the rule is "Replace all occurances of two operands followed
    by an operator by their infix equivalent"

    This works fine like so ->

    (2*2) == (22*)

    but what happens if I need something bigger then 9?

    (10*2) == (102*) ->

    which would multiple the 0 and the 2 instead of 10*2...
    Am I making any sense? Please help me.

    Thanks.
     
    KidLogik, Feb 2, 2004
    #1
    1. Advertising

  2. "KidLogik" <> wrote in message
    news:...
    > Hello!
    >
    > I am converting an infix expression string into a postfix so that I
    > will be able to evaluate it easier ->
    >
    > (5*(((9+8)*(4*6))+7)) == 598+46**7+*
    >
    > I believe the rule is "Replace all occurances of two operands followed
    > by an operator by their infix equivalent"
    >
    > This works fine like so ->
    >
    > (2*2) == (22*)
    >
    > but what happens if I need something bigger then 9?
    >
    > (10*2) == (102*) ->
    >
    > which would multiple the 0 and the 2 instead of 10*2...
    > Am I making any sense? Please help me.
    >
    > Thanks.


    I think you need to add a space between the 10 and the 2.

    John
     
    John Harrison, Feb 2, 2004
    #2
    1. Advertising

  3. While it was 2/2/04 9:39 am throughout the UK, KidLogik sprinkled little
    black dots on a white screen, and they fell thus:

    > Hello!
    >
    > I am converting an infix expression string into a postfix so that I
    > will be able to evaluate it easier ->

    <snip>
    > but what happens if I need something bigger then 9?
    >
    > (10*2) == (102*) ->

    <snip>

    Surely you should be building the postfixed expression in a binary form?
    For example:

    struct RPNNode {
    enum { NUM, PLUS, MINUS, TIMES, DIVIDE } op;
    int value;
    };

    That way, you won't have any such problem.

    Stewart.

    --
    My e-mail is valid but not my primary mailbox, aside from its being the
    unfortunate victim of intensive mail-bombing at the moment. Please keep
    replies on the 'group where everyone may benefit.
     
    Stewart Gordon, Feb 2, 2004
    #3
  4. KidLogik

    David Rubin Guest

    KidLogik wrote:

    > I am converting an infix expression string into a postfix so that I
    > will be able to evaluate it easier ->


    > (5*(((9+8)*(4*6))+7)) == 598+46**7+*


    > I believe the rule is "Replace all occurances of two operands followed
    > by an operator by their infix equivalent"


    Firstly, there is more than one rule! When I wrote this program, I found
    that dealing with parentheses and operator precedence was not
    straightforward; it took a bit of fiddling around. In any case,
    generally speaking, you need to use a stack and a parser...

    [snip]
    > but what happens if I need something bigger then 9?


    > (10*2) == (102*) ->


    > which would multiple the 0 and the 2 instead of 10*2...


    The parser comes in handy for solving this problem. You can basically
    parse the input string as characters using the following loop:

    char *p = buf;
    while(*p != '\n'){
    if(isdigit((int)*p)){
    /* operands */
    }else
    if(strchr("+-*/%^()", *p) == 0){
    /* whitespace */
    p++;
    }else{
    /* operators */
    }
    }

    Note that my program does not evaluate the expression (which you seem to
    imply as your goal), but rather converts between two strings: infix to
    postfix.

    HTH,

    /david

    --
    Andre, a simple peasant, had only one thing on his mind as he crept
    along the East wall: 'Andre, creep... Andre, creep... Andre, creep.'
    -- unknown
     
    David Rubin, Feb 2, 2004
    #4
  5. David Rubin wrote:
    > KidLogik wrote:
    >
    >
    >>I am converting an infix expression string into a postfix so that I
    >>will be able to evaluate it easier ->

    >
    >
    >>(5*(((9+8)*(4*6))+7)) == 598+46**7+*

    >
    >
    >>I believe the rule is "Replace all occurances of two operands followed
    >>by an operator by their infix equivalent"

    >
    >
    > Firstly, there is more than one rule! When I wrote this program, I found
    > that dealing with parentheses and operator precedence was not
    > straightforward; it took a bit of fiddling around. In any case,
    > generally speaking, you need to use a stack and a parser...
    >
    > [snip]
    >
    >>but what happens if I need something bigger then 9?

    >
    >
    >>(10*2) == (102*) ->

    >
    >
    >>which would multiple the 0 and the 2 instead of 10*2...

    >
    >
    > The parser comes in handy for solving this problem. You can basically
    > parse the input string as characters using the following loop:
    >
    > char *p = buf;
    > while(*p != '\n'){
    > if(isdigit((int)*p)){
    > /* operands */
    > }else
    > if(strchr("+-*/%^()", *p) == 0){
    > /* whitespace */
    > p++;
    > }else{
    > /* operators */
    > }
    > }
    >
    > Note that my program does not evaluate the expression (which you seem to
    > imply as your goal), but rather converts between two strings: infix to
    > postfix.
    >
    > HTH,
    >
    > /david
    >


    If one throws the operators and numbers into a binary tree, then
    conversion is just a matter of how the tree is traversed. I wrote
    the program so long ago, I don't remember how I handled the parens.

    --
    Thomas Matthews

    C++ newsgroup welcome message:
    http://www.slack.net/~shiva/welcome.txt
    C++ Faq: http://www.parashift.com/c -faq-lite
    C Faq: http://www.eskimo.com/~scs/c-faq/top.html
    alt.comp.lang.learn.c-c++ faq:
    http://www.raos.demon.uk/acllc-c /faq.html
    Other sites:
    http://www.josuttis.com -- C++ STL Library book
     
    Thomas Matthews, Feb 2, 2004
    #5
  6. KidLogik

    David Rubin Guest

    Thomas Matthews wrote:

    [snip - infix to postfix]
    > > Firstly, there is more than one rule! When I wrote this program, I found
    > > that dealing with parentheses and operator precedence was not
    > > straightforward; it took a bit of fiddling around. In any case,
    > > generally speaking, you need to use a stack and a parser...


    [snip]
    > If one throws the operators and numbers into a binary tree, then
    > conversion is just a matter of how the tree is traversed. I wrote
    > the program so long ago, I don't remember how I handled the parens.


    I found the stack-based algorithm in the project notes from some random
    college intro CS course on the web. I usually just browse college course
    web pages when I'm looking for a short "keep your skills sharp" project.
    The stack algorithm explicitly described how to handle parens, but it
    was apparantly lacking a few details.

    /david

    --
    Andre, a simple peasant, had only one thing on his mind as he crept
    along the East wall: 'Andre, creep... Andre, creep... Andre, creep.'
    -- unknown
     
    David Rubin, Feb 3, 2004
    #6
    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. Robert M. Gary

    Expression evalution code

    Robert M. Gary, Feb 1, 2005, in forum: Java
    Replies:
    4
    Views:
    642
    Robert M. Gary
    Feb 2, 2005
  2. caramel

    convert infix to postfix

    caramel, Nov 18, 2005, in forum: C Programming
    Replies:
    19
    Views:
    1,428
    Barry
    Nov 19, 2005
  3. Replies:
    1
    Views:
    458
    mlimber
    Dec 28, 2006
  4. Xah Lee
    Replies:
    30
    Views:
    1,813
    Peter J. Holzer
    Jun 16, 2007
  5. Xah Lee
    Replies:
    30
    Views:
    1,267
    Peter J. Holzer
    Jun 16, 2007
Loading...

Share This Page