Infix to postfix Q

This is a discussion on Infix to postfix Q within the C++ Programming forums, part of the General Programming Boards category; Hey everyone! I'm looking for an algoritem which converts an infix squence to postfix. My problem is that I don't ...

  1. #1
    Liberty4all
    Guest

    Infix to postfix Q

    Hey everyone!
    I'm looking for an algoritem which converts an infix squence to postfix. My problem is that I don't know what to do with the brackets in the squence. Here's what I have so far...

    counter=0
    init(stack)
    While not end of line
    read x
    if x is a number
    print x
    counter++
    else //x is an oprenad
    push(stack,x)
    if counter==2
    y=pop(stack)
    print y
    counter=0
    while not_empty(stack)
    y=pop(stack)
    print y

    I believe this would work if converted into code. How do I make it work if the expression contains brackets? i dont want the output to have any brackets in it

    I would appreciate any help you could offer, and no code is needed (just an algoritem).

    Thanks

  2. #2
    Liberty4all
    Guest

    Re:correction

    adding spaces....
    Code:
    counter=0
    init(stack)
    While not end of line
       read x
       if x is a number
           print x
           counter++
       else //x is an oprenad
           push(stack,x)
       if counter==2
           y=pop(stack)
           print y
           counter=0
    while not_empty(stack)
        y=pop(stack)
        print y
    You can suggest your own idea of course.....


    Code tagged by Hammer

  3. #3
    Liberty4all
    Guest

    sorry...

    Take 3.. it won't let me post spaces for some reason


    BEGIN
    counter=0
    init(stack)
    While not end of line
    {read x
    if x is a number
    {print x
    counter++}
    else //x is an oprenad
    {push(stack,x)}
    if counter==2
    {y=pop(stack)
    print y
    counter=0}
    }
    while not_empty(stack)
    {y=pop(stack)
    print y}
    END

    I hope it's clearer now....

    I can't be bothered to remove these posts, just read this before posting. Hammer

  4. #4
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Do you mean like RPN (reverse polish notation)?

    i.e.
    2 + (3*4) equals
    2 3 4 * +

    If that's what you mean, I can help you. My parser uses RPN internally to speed things up.

    AND:
    Remove your two extra posts and edit your first message using [code] at the beginning and [/code] at the end.
    Last edited by Sang-drax; 11-01-2002 at 10:12 AM.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  5. #5
    Evil Member
    Join Date
    Jan 2002
    Posts
    638
    Put you text in CODE tags to get the spaces right.

    You know when you came here there was something at the top that said somehting along the lines of "Posting code? Please dear god read this first so the moderators don't pitch a fit".

    Had you read it first....

    You would have learned the glory of CODE tags.

    Put this [CÖDE] before your code and this [/CÖDE] after it. (Use regular 'O's)

  6. #6
    Seeking motivation... endo's Avatar
    Join Date
    May 2002
    Posts
    537
    RPN == postfix
    Couldn't think of anything interesting, cool or funny - sorry.

  7. #7
    Liberty4all
    Guest
    Originally posted by Sang-drax
    Do you mean like RPN (reverse polish notation)?

    i.e.
    2 + (3*4) equals
    2 3 4 * +

    If that's what you mean, I can help you. My parser uses RPN internally to speed things up.

    AND:
    Remove your two extra posts and edit your first message using [code] at the beginning and [/code] at the end.
    Yeah, that is what I mean, I would really appreciate if u can help.

    I tried to edit/delete my posts but I get an "invalid username or pw" message. It's strange cause it doesn't give me any problems with signing in to post. I'm sorry for messing up, it won't happen again.

  8. #8
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Hmm, I'll try to explain the algorithm I use. It works perfectly.

    First, define every operator that is going to be used and assign each operator a predecence. Remember that ( and ) also are operators and they should have the highest predecence.

    You'll also need a Token class, a token can contain a number or an operator (and functions and identifiers for more advanced parsers). A token class may look like this:
    Code:
    struct Token()
    {
       enum {TypeOperator,TypeNumber,TypeExpression} Type;
       double num;
       char op;
    
       queue<Token*> expression;
    };
    The expression member is explained later.

    I'll use this string as an example: "2*(5+6)^2"

    The first task is to convert a string to a std::vector<Token>. I won't explain how this is done here, but it's not that hard using istream.

    When the token vector is ready, the vector will look like this:
    [ 2 * ( 5 + 6 ) ^ 2 ] size = 9
    It is entirally made up by Tokens of TypeNumber and TypeOperator.

    Now the real parsing begins, we will scan the vector for operator, processing the operator with the highest predecence first. Parenthesis is parsed using recursion.
    Pseudo-code:
    Code:
    queue<Token> MakeRPNExpression(vector<Token> tvector)
    {
    
    for predecence = highest to lowest
      for index = 0 to size(tvector)
        if tvector[index].Type == TypeOperator and
           get_predecence(tvector[index].op) == predecence
        {
            //Process this operator
            
            //Is it parenthesis?
            if  vector[index].op == ')'
            {
                //collect every token within the parenthesis
                //remeber to consider nested parenthesis!
                //call recursivly
                queue<Token> newtkns = MakeRPNExpression(subtokens);
                //erase the tokens in the parenthesis
                //insert a token with the queue
                Token inserttkn(newtkns);
                tvector.insert( curr_pos, inserttkn);
            }
    
            //Another binary operator
            else
            {
                //get operands
                Token left = offset-1;
                Token right = offset+1;
                
                queue<Token> new_expr;
                //push operands
                new_expr.push(left);
                new_expr.push(right);
                //push operator last
                new_expr.push(op);
    
                //Replace the operator and operands
                //with a single expression token using
                //container functions
            }
        }
    
       //If everything went OK, the vector
      //should now contain only one token
      //with the expression in it.
      return tvector[0].expression;
    }
    Very esoteric, I know, but I'll show how it works using my example vector.
    The vector now looks like this:
    {2} {*} {(} {5} {+} {6} {)} {^} {2}

    First, the parentheis is found, the tokens inside is converted resursivly to this: { {5} {6} {+} }, which is returned.

    After replacement, the vector looks like this:
    {2} {*} { {5} {6} {+} } {^} {2}
    Note that the nested {} counts as a single token.

    The next operator found is ^, the operands and operator are rearranged and after replacement and merging of the queues the vetor looks like this:
    {2} {*}

    The last operator found is *, the same procedure is followed and the final vector (only one token now) is:
    { {2} {5} {6} {+} {2} {^} {*} }
    And we're done.

    2*(5+6)^2 is
    2 5 6 + 2 ^ * in RPN

    I'll attach some real code from my parser, however I don't think it will help much. It is more generic, using a DataType class instead of number, and features binary and tertiary ooperators.
    This typedef is used:
    Code:
    typedef std::queue<Petter::Token> Expression;
    I think this is my longesy post in this forum, but also the hardest to understand, but I'm not a teacher, sorry.
    Attached Files Attached Files
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  9. #9
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    This algorithm works with nested () as well as complex expressions:

    3+(2+(3-5))*8+((23+6)*15)+5
    equals in RPN:
    3 2 3 5 - + 8 * + 23 6 + 15 * + 5 +
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Expression: Convert infix notation to postfix notation.
    By Nutshell in forum C Programming
    Replies: 7
    Last Post: 02-27-2010, 06:44 AM
  2. Infix, Postfix, Pseudo-Calculator using Stack ADT
    By sangken in forum C Programming
    Replies: 9
    Last Post: 09-08-2006, 08:17 AM
  3. Replies: 4
    Last Post: 03-12-2006, 01:17 PM
  4. Converting from infix to postfix
    By jcramer in forum C Programming
    Replies: 4
    Last Post: 03-27-2004, 08:23 PM
  5. Infix to Postfix
    By dat in forum C Programming
    Replies: 6
    Last Post: 06-16-2003, 08:46 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21